?id=3196
分析： 带区间查询和名次询问，线段树套treap
操作1： 查询k在区间内的排名。 求出k-1的名次+1就是k的名次
操作2：查询区间内排名为k的值。 二分枚举权值，调用操作1
操作3：修改某一位值上的数值。 在树上先删除，再插入
操作4.查询k在区间内的前驱(前驱定义为小于x，且最大的数) 操作5.查询k在区间内的后继(后继定义为大于x，且最小的数) 在treap树上遍历
MAXN=50010;const int N=3000000;const int inf=1e8;;int n,q;int a[MAXN];struct node{node* ch[2];int v,size,r;int w;};node s[N];node*ptr=s;node* null=ptr;struct Treap{node* root;void push_up(node* &rt){rt->size=rt->ch[0]->size+rt->ch[1]->size+rt->w;}void newnode(node* &rt,int x){rt=++ptr;rt->v=x;rt->r=rand();rt->size=rt->w=1;rt->ch[0]=rt->ch[1]=null;}void init(){root=null;}void rotate(node* &rt,int d){node* k=rt->ch[d^1];rt->ch[d^1]=k->ch[d];k->ch[d]=rt;push_up(rt);push_up(k);rt=k;}void insert(node* &rt,int x){if(rt==null){newnode(rt,x);return ;}int d=x<=rt->v?0:1;if(rt->v==x){rt->w++;}else{insert(rt->ch[d],x);if(rt->ch[d]->r > rt->r) rotate(rt,d^1);}push_up(rt);}void remove(node* &rt,int x){if(rt==null) return ;int d=rt->v <x ?1:0;if(rt->v==x){if(rt->w>=2){rt->w–;}else{if(rt->ch[0]!=null&&rt->ch[1]!=null){int d2=rt->ch[0]->r > rt->ch[1]->r ?1:0;rotate(rt,d2);remove(rt->ch[d2],x);}else{if(rt->ch[0]==null) rt=rt->ch[1];else rt=rt->ch[0];}}}else{remove(rt->ch[d],x);}if(rt!=null) push_up(rt);}void modify(node* &rt,int x,int v){remove(rt,x);insert(rt,v);}int findk(node* rt,int k){//名次为k的值if(rt==null) return -1;int s=rt->ch[0]->size;if(s+1==k) return rt->v;if(k<=s) return findk(rt->ch[0],k);else return findk(rt->ch[1],k-s-1);}int rank(node* rt,int x){//权值为x的名次int s=0;while(rt!=null){if(rt->v==x) return rt->ch[0]->size+s;int d=rt->v>x ?0:1;if(d==0) rt=rt->ch[0];else{s+=rt->ch[0]->size+rt->w;rt=rt->ch[1];}}return s;}int before(node *rt,int x){if(rt==null) return 0;int res=0;if(rt->v< x){res=max(res,rt->v);res=max(res,before(rt->ch[1],x));}else res=max(res,before(rt->ch[0],x));return res;}int after(node* rt,int x){if(rt==null) return inf;int res=inf;if(rt->v>x){res=min(res,rt->v);res=min(res,after(rt->ch[0],x));}else res=min(res,after(rt->ch[1],x));return res;}void view(node* rt){if(rt==null) return ;view(rt->ch[0]);cout<<rt->v<<” “;view(rt->ch[1]);}};Treap seg[N];void init(){ptr=s;for(int i=1;i<N;++i){seg[i].init();}}void build(int p,int v,int l,int r,int rt){seg[rt].insert(seg[rt].root,v);if(l==r) return ;int m=(l+r)>>1;if(p<=m) build(p,v,lson);else build(p,v,rson);}void update(int p,int x,int v,int l,int r,int rt){seg[rt].modify(seg[rt].root,x,v);if(l==r) return ;int m=(l+r)>>1;if(p<=m) update(p,x,v,lson);else update(p,x,v,rson);}int query1(int L,int R,int v,int l,int r,int rt){if(L<=l&&r<=R){return seg[rt].rank(seg[rt].root,v);}int m=(l+r)>>1;int res=0;if(L<=m) res+=query1(L,R,v,lson);if(m<R) res+=query1(L,R,v,rson);return res;}int query2(int L,int R,int k){int l=0,r=inf,mid;int ans;while(l<=r){mid=(l+r)>>1;int tmp=query1(L,R,mid,1,n,1);if(tmp+1<=k) {l=mid+1;ans=mid;}else r=mid-1;}return ans;}int query4(int L,int R,int k,int l,int r,int rt){if(L<=l&&r<=R){return seg[rt].before(seg[rt].root,k);}int m=(l+r)>>1;int res=0;if(L<=m) res=max(res,query4(L,R,k,lson));if(m<R) res=max(res,query4(L,R,k,rson));return res;}int query5(int L,int R,int k,int l,int r,int rt){if(L<=l&&r<=R){return seg[rt].after(seg[rt].root,k);}int m=(l+r)>>1;int res=inf;if(L<=m) res=min(res,query5(L,R,k,lson));if(m<R) res=min(res,query5(L,R,k,rson));return res;}void view(int l,int r,int rt){seg[rt].view(seg[rt].root);cout<<“————-“<<endl;if(l==r) return ;int m=(l+r)>>1;view(lson);view(rson);}int main(){l,r,k,pos,op;while(scanf(“%d%d”,&n,&q)==2){init();for(int i=1;i<=n;++i) {scanf(“%d”,&a[i]);build(i,a[i],1,n,1);}while(q–){scanf(“%d”,&op);if(op==1){scanf(“%d%d%d”,&l,&r,&k);printf(“%d\n”,query1(l,r,k,1,n,1)+1);}if(op==2){scanf(“%d%d%d”,&l,&r,&k);printf(“%d\n”,query2(l,r,k));}if(op==3){scanf(“%d%d”,&pos,&k);int x=a[pos];update(pos,x,k,1,n,1);a[pos]=k;}if(op==4){scanf(“%d%d%d”,&l,&r,&k);printf(“%d\n”,query4(l,r,k,1,n,1));}if(op==5){scanf(“%d%d%d”,&l,&r,&k);printf(“%d\n”,query5(l,r,k,1,n,1));}}}return 0;}
，我想，这就是旅行的真义吧。
