题解 P4422 【[COCI2017-2018#1] Deda】

观察到年龄很小而车站编号很大，考虑以年龄为位置建线段树，每个位置存该年龄最早出现的车站，然后瞎递归一下找符合年龄区间里是否有符合条件的车站就可以了。 ```cpp #include<bits/stdc++.h> #define N 200000 #define reg register #define inl inline #define inf 1010580540 using namespace std; int n,Q,t[N*4+5],ans; void Modify(reg int rt,reg int l,reg int r,reg int pos,reg int x) { if(l==r) return t[rt]=x,void(); reg int mid=(l+r)>>1; if(pos<=mid) Modify(rt<<1,l,mid,pos,x); else Modify(rt<<1|1,mid+1,r,pos,x); t[rt]=min(t[rt<<1],t[rt<<1|1]); } int Find(reg int rt,reg int l,reg int r,reg int x) { if(t[rt]>x) return inf; if(l==r) return l; reg int mid=(l+r)>>1; if(t[rt<<1]<=x) return Find(rt<<1,l,mid,x); else return Find(rt<<1|1,mid+1,r,x); } void Query(reg int rt,reg int l,reg int r,reg int tl,reg int tr,reg int x) { if(tl<=l && r<=tr) return ans=Find(rt,l,r,x),void(); reg int mid=(l+r)>>1; if(tl<=mid) Query(rt<<1,l,mid,tl,tr,x); if(ans!=inf) return; if(tr>mid) Query(rt<<1|1,mid+1,r,tl,tr,x); } int main() { memset(t,60,sizeof(t)); scanf("%d %d",&n,&Q); while(Q--) { reg int x,y; reg char opt[5]; scanf("%s %d %d",opt+1,&x,&y); if(opt[1]=='M') Modify(1,1,n,y,x); else { ans=inf; Query(1,1,n,y,n,x); printf("%d\n",ans==inf?-1:ans); } } return 0; } ```