传送们：http://www.lydsy.com/JudgeOnline/problem.php?id=3196
题解：线段树+treap
#include<algorithm> #include<iostream> #include<cstring> #include<cmath> #include<cstdio> #define inf 100000000 #define N 200001 #define M 3000001 using namespace std; int n,m,sz,ans,a[N]; int ls[M],rs[M],rnd[M],v[M],s[M],w[M]; int root[N]; int read() { int x=0; char ch; bool bo=0; while (ch=getchar(),ch<'0'||ch>'9') if (ch=='-') bo=1; while (x=x*10+ch-'0',ch=getchar(),ch>='0'&&ch<='9'); if (bo) return -x; return x; } void updata(int k){s[k]=s[ls[k]]+s[rs[k]]+w[k];} void rturn(int &k){int t=ls[k]; ls[k]=rs[t]; rs[t]=k; s[t]=s[k]; updata(k); k=t;} void lturn(int &k){int t=rs[k]; rs[k]=ls[t]; ls[t]=k; s[t]=s[k]; updata(k); k=t;} void insert(int &k,int val) { if(!k){k=++sz; s[k]=w[k]=1; v[k]=val; rnd[k]=rand();return;} s[k]++; if (v[k]==val) w[k]++; else if (val<v[k]) {insert(ls[k],val); if (rnd[ls[k]]<rnd[k]) rturn(k);} else if (val>v[k]) {insert(rs[k],val); if (rnd[rs[k]]<rnd[k]) lturn(k);} } void build(int k,int l,int r,int pos,int val) { insert(root[k],val); if (l==r) return ; int mid=(l+r)>>1; if (pos<=mid) build(k*2,l,mid,pos,val); else build(k*2+1,mid+1,r,pos,val); } void del(int &k,int num) { if (v[k]==num) { if (w[k]>1){w[k]--; s[k]--; return;} if (ls[k]*rs[k]==0) k=ls[k]+rs[k]; else if (rnd[ls[k]]<rnd[rs[k]]){rturn(k); del(k,num);} else {lturn(k); del(k,num);} } else if (v[k]>num) {del(ls[k],num); s[k]--;} else{del(rs[k],num); s[k]--;} } void ask_rank(int k,int num) { if (!k) return; if (v[k]==num){ans+=s[ls[k]]; return;} else if (v[k]>num) ask_rank(ls[k],num); else if (v[k]<num) {ans+=s[ls[k]]+w[k]; ask_rank(rs[k],num);} } void query_rank(int k,int l,int r,int x,int y,int num) { if (l==x && y==r){ask_rank(root[k],num); return;} int mid=(l+r)>>1; if (y<=mid) query_rank(k*2,l,mid,x,y,num); else if (mid<x) query_rank(k*2+1,mid+1,r,x,y,num); else { query_rank(k*2,l,mid,x,mid,num); query_rank(k*2+1,mid+1,r,mid+1,y,num); } } void query_k(int x,int y,int num) { int l=0,r=inf,tmp; while (l<r) { //cout<<l<<" "<<r<<endl; int mid=(l+r)>>1; ans=1; query_rank(1,1,n,x,y,mid); //cout<<" ans "<<ans<<endl; if (ans>num) r=mid; else {l=mid+1; tmp=mid;} } printf("%d ",tmp); } void pre(int k,int pos) { if (!k) return; if (v[k]<pos) {ans=max(ans,v[k]); pre(rs[k],pos);} else pre(ls[k],pos); } void next(int k,int pos) { if (!k) return; if (v[k]>pos) {ans=min(ans,v[k]); next(ls[k],pos);} else next(rs[k],pos); } void query_pre(int k,int l,int r,int x,int y,int pos) { if (l==x && r==y){ pre(root[k],pos); return; } int mid=(l+r)>>1; if (y<=mid) query_pre(k*2,l,mid,x,y,pos); else if (mid<x) query_pre(k*2+1,mid+1,r,x,y,pos); else { query_pre(k*2,l,mid,x,mid,pos); query_pre(k*2+1,mid+1,r,mid+1,y,pos); } } void query_next(int k,int l,int r,int x,int y,int pos) { if (k!=0) //cout<<" "<<k<<" "<<l<<" "<<r<<" "<<x<<" "<<y<<" "<<pos<<endl; if (l==x && r==y){ next(root[k],pos); return; } int mid=(l+r)>>1; if (y<=mid) query_next(k*2,l,mid,x,y,pos); else if (mid<x) query_next(k*2+1,mid+1,r,x,y,pos); else { query_next(k*2,l,mid,x,mid,pos); query_next(k*2+1,mid+1,r,mid+1,y,pos); } } void change(int k,int l,int r,int pos,int now,int pre) { del(root[k],pre); insert(root[k],now); if (l==r) return; int mid=(l+r)>>1; if (pos<=mid) change(k*2,l,mid,pos,now,pre); else change(k*2+1,mid+1,r,pos,now,pre); } int main() { n=read(),m=read(); for (int i=1; i<=n; i++) a[i]=read(); for (int i=1; i<=n; i++) build(1,1,n,i,a[i]); int opt,l,r,k,pos; for (int i=1; i<=m; i++) { opt=read(); if (opt==1){l=read(),r=read(),k=read();ans=1; query_rank(1,1,n,l,r,k);} if (opt==2){l=read(),r=read(),k=read(); query_k(l,r,k);} if (opt==3){pos=read(),k=read();change(1,1,n,pos,k,a[pos]);a[pos]=k;} if (opt==4){l=read(),r=read(),k=read();ans=0; query_pre(1,1,n,l,r,k);} if (opt==5){l=read(),r=read(),k=read();ans=inf; query_next(1,1,n,l,r,k);} if (opt!=3 && opt!=2) printf("%d ",ans); } }