ICPC NEAU Programming Contest 2020 D 旅游（单调栈）

思路：
你只要把每个数为起点的上升子序列抽出来（能抽则抽），那么此时要求第几大都可以求出来。这个过程直接用单调栈维护。

不过也可以使用倍增,定义$f[i][j]$f[i][j]代表以第$i$i个数为起点的第$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;
}