其实不用线段树
但是细节多
还得离线两次
所以干脆线段树吧
代码5分钟，bug两小时
#include<bits/stdc++.h> using namespace std; const int N=1e5+10; struct P{ int x,y; }; int A[N],B[N],n,m,Ans[N]; vector<P> V[N]; struct SegmentTree{ int p,l,r,m; #define l(x) Tree[x].l #define r(x) Tree[x].r #define m(x) Tree[x].m }Tree[N*4]; void build(int p,int l,int r){ l(p)=l,r(p)=r; if(l==r){ m(p)=0; return; } int mid=(l+r)/2; build(p*2,l,mid); build(p*2+1,mid+1,r); m(p)=max(m(p*2),m(p*2+1)); } void change(int p,int x,int val){ if(l(p)==r(p)){ m(p)=val; return; } int mid=(l(p)+r(p))/2; if(x<=mid)change(p*2,x,val); else change(p*2+1,x,val); m(p)=max(m(p*2),m(p*2+1)); } int find(int p,int x){ if(l(p)==r(p))return l(p); if(m(p*2)>x)return find(p*2,x); else return find(p*2+1,x); } void back(){ change(1,n+1,1<<30); for(int i=n;i>=1;--i){ B[i]=B[find(1,A[i])]+1; change(1,i,A[i]); } } int main(){ //freopen("1.txt","r",stdin); ios::sync_with_stdio(0); int T; cin>>T; while(T--){ memset(B,0,sizeof B); memset(Tree,0,sizeof Tree); for(int i=0;i<N;++i)V[i].clear(); cin>>n>>m; for(int i=1;i<=n;++i)cin>>A[i]; A[n+1]=1<<30; build(1,1,n+1); back(); int x,y; for(int i=1;i<=m;++i){ cin>>x>>y; V[x].push_back(P{y,i}); } int ma=0,now=0; for(int i=1;i<=n;++i){ change(1,i,0); for(int j=0;j<V[i].size();++j){ if(V[i][j].x>ma){ Ans[V[i][j].y]=now+1+B[find(1,V[i][j].x)]; }else{ Ans[V[i][j].y]=now+B[find(1,ma)]; } } if(A[i]>ma)ma=A[i],++now; } for(int i=1;i<=m;++i)printf("%d\n",Ans[i]); } }
