思路：
你只要把每个数为起点的上升子序列抽出来（能抽则抽），那么此时要求第几大都可以求出来。这个过程直接用单调栈维护。
不过也可以使用倍增,定义 f [ i ] [ j ] f[i][j] f[i][j]代表以第 i i i个数为起点的第 i + 2 j − 1 i+2^j-1 i+2j−1大的数是什么，结合单调栈可以直接求出来，在在线的情况下只能使用这种方法。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include <iostream>
#include <map>
#include <string>using namespace std;typedef long long ll;const int maxn = 1e5 + 7;int a[maxn];
vector<pair<int,int> >G[maxn];
int ans[maxn];
int stk[maxn];int main() {int T;scanf("%d",&T);while(T--) {int n,m;scanf("%d%d",&n,&m);for(int i = 1;i <= n;i++) {scanf("%d",&a[i]);G[i].clear();}for(int i = 1;i <= m;i++) {int x,y;scanf("%d%d",&x,&y);G[x].push_back({y,i});}int top = 0;for(int i = n;i >= 1;i--) { //递减while(top && a[stk[top]] <= a[i]) {top--;}stk[++top] = i;for(int j = 0;j < G[i].size();j++) {int y = G[i][j].first;int id = G[i][j].second;if(y > top) {ans[id] = -1;}else {ans[id] = stk[top - y + 1];}}}for(int i = 1;i <= m;i++) {printf("%d\n",ans[i]);}}return 0;
}
补上倍增的
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include <iostream>
#include <map>
#include <string>using namespace std;typedef long long ll;const int maxn = 1e5 + 7;int f[maxn][20],a[maxn],stk[maxn],p[20];
int n,m;void init() {p[0] = 1;for(int i = 1;i <= 18;i++) {p[i] = p[i - 1] * 2;for(int j = 1;j <= n;j++) {f[j][i] = f[f[j][i - 1]][i - 1];}}
}int main() {int T;scanf("%d",&T);while(T--) {memset(f,0,sizeof(f));scanf("%d%d",&n,&m);for(int i = 1;i <= n;i++) scanf("%d",&a[i]);int top = 0;for(int i = 1;i <= n;i++) { //递减单调队列while(top && a[stk[top]] < a[i]) {f[stk[top]][0] = i;top--;}stk[++top] = i;}init();while(m--) {int x,y;scanf("%d%d",&x,&y);if(y == 1) {printf("%d\n",x);continue;}y--;for(int i = 18;i >= 0;i--) {if(y >= p[i]) {y -= p[i];x = f[x][i];}}if(x == 0) {printf("-1\n");}else printf("%d\n",x);}}return 0;
}