Miku

思路：参照这位神仙

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
const int maxn = 1e5+50;
int h[maxn],maxx[maxn],fr[maxn],sh[maxn];
//原高度 1-I最大值，前缀，原来应该 
vector <int> vec[maxn];

//去掉i后的阶梯 

//这里的i都是原来取了的 
int t,tmp,cnt,nex,fla,pos;
int n,m;
int u,v,sum,flag;
int main(){
    scanf("%d",&t);
    while(t--){
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;++i){
            scanf("%d",&h[i]);
        }       
        if(n==1){
            for(int i=1;i<=m;++i)
            cout<<1<<endl;
            continue; 
        }
        for(int i=0;i<=n;++i){
            vec[i].clear();
        }
        tmp=-1;
        cnt=0;
        nex=-1;
        flag=0;
        maxx[0]=0;
        for(int i=1;i<=n;++i){
            if(h[i]>tmp){
                nex=-1;
                tmp=h[i];
                sh[cnt++]=tmp;
                pos=i;
                flag=0;
            }
            if(!flag) flag=1;
            else{
                if(h[i]>nex&&h[i]>sh[cnt-2]){
                     //cnt-2？见50 
                    //建立去掉上一个被取走的元素后的阶梯 
                    nex=h[i];
                    //对于pos下的下一个应处理元素nex 
                    vec[pos].push_back(nex);
                }
            }
            maxx[i]=tmp;
            fr[i]=cnt; 
            //fr到了i后的取了多少个 
        }
        while(m--){
            sum=0;
            scanf("%d%d",&u,&v);
            if(v>h[u]){
                if(v<=maxx[u-1]) sum=fr[n];
                //没有影响 
                else{
                    //原来不取u
                    //现在要了 
                    sum+=1+fr[u-1];
                    int id=upper_bound(sh,sh+cnt,v)-sh;
                    if(id!=cnt) sum+=cnt-id;
                    //再加上本应去部分事实上就是去了
                    //中间的本应取 
                }
            }else
                if(v<h[u]){
                    sum+=fr[u-1];
                    if(v>maxx[u-1]) sum++;
                    if(h[u]==maxx[u]){//这样的话u不能取了 
                    int id=upper_bound(vec[u].begin(),vec[u].end(),v)-vec[u].begin();
                    sum+=vec[u].size()-id;
                    //新增 
                    int idd=upper_bound(sh,sh+cnt,h[u])-sh;
                    //原来 
                    if(idd!=cnt) sum+=cnt-idd;
                    }else
                    //no effect 
                    sum=fr[n]; 
                }
                else
                sum=fr[n];
                cout<<sum<<endl; 
        }
    }
    return 0;
}