@[瞬间。。](/user/238311)
呼叫老师
by WsW_ @ 2023-08-31 20:25:11
现在 $\mathtt{WA}\;2\sim 7$
```cpp
#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+3;
struct node{
int t;
int ls,rs;
}tree[maxn<<5];
int tl,size;
int root[maxn];
int n,m;
int a[maxn],l,r;
int copy(int p){
tree[++tl]=tree[p];
return tl;
}
int insert(int now,int a,int t,int left,int righ){
int p=copy(now);
// tree[p].t=max(tree[p].t,t);
// else tree[p].t=t;
int mid=left+righ>>1;
if(left==righ){
tree[p].t=t;
return p;
}
if(a<=mid){
tree[p].ls=insert(tree[now].ls,a,t,left,mid);
// tree[p].t=min(tree[tree[p].rs].t,t);
}
else{
tree[p].rs=insert(tree[now].rs,a,t,mid+1,righ);
// tree[p].t=min(tree[tree[p].ls].t,t);
}
// if(now==0)tree[p].t=t;
// else
tree[p].t=min(tree[tree[p].rs].t,tree[tree[p].ls].t);
return p;
}
int find(int t,int p,int left,int righ){
// if(righ==6)printf("%d\n",tree[tree[p].ls].t);
// printf("%d~%d %d\n",left,righ,tree[p].t);
if(left==righ)return left;
int mid=left+righ>>1;
if(tree[tree[p].ls].t<t)return find(t,tree[p].ls,left,mid);
else return find(t,tree[p].rs,mid+1,righ);
}
int main(){
// freopen("P4137_1.in","r",stdin);
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i){
scanf("%d",&a[i]);
// root[i]=insert(root[i-1],a[i],i,0,maxn);
size=max(size,min(a[i],n)+1);
}
// tree[0].t=1e9;
for(int i=1;i<=n;++i){
if(a[i]<=n){
root[i]=insert(root[i-1],a[i],i,0,size);
}
}
while(m--){
scanf("%d%d",&l,&r);
printf("%d\n",find(l,root[r],0,size));
}
return 0;
}
```
by WsW_ @ 2023-08-31 21:04:44
已 $\mathtt{AC}$，终.
by WsW_ @ 2023-08-31 21:43:40