题意
动态区间第k大
（n<=100000,m<=100000)
题解
整体二分的应用。
与静态相比差别不是很大。（和CDQ还有点像）所以直接上代码。
1 #include2 #include 3 #include 4 #include 5 #include 6 using namespace std; 7 const int N=300100; 8 struct query{ 9 int x,y,type,k,w; 10 }q[N],c1[N],c2[N]; 11 int n,m,ans[N],tr[N],mx,tot,cnt,a[N]; 12 int lowbit(int x){ 13 return x&-x; 14 } 15 void add(int x,int w){ 16 for(int i=x;i<=n;i+=lowbit(i)){ 17 tr[i]+=w; 18 } 19 } 20 int getsum(int x){ 21 int ans=0; 22 for(int i=x;i;i-=lowbit(i)){ 23 ans+=tr[i]; 24 } 25 return ans; 26 } 27 void solve(int l,int r,int L,int R){ 28 if(l>r)return; 29 if(L==R){ 30 for(int i=l;i<=r;i++){ 31 if(q[i].type==3)ans[q[i].w]=L; 32 } 33 return ; 34 } 35 int mid=(L+R)>>1; 36 int lnow=0;int rnow=0; 37 for(int i=l;i<=r;i++){ 38 if(q[i].type==3){ 39 int tmp=getsum(q[i].y)-getsum(q[i].x-1); 40 if(tmp>=q[i].k){ 41 c1[++lnow]=q[i]; 42 } 43 else{ 44 q[i].k-=tmp; 45 c2[++rnow]=q[i]; 46 } 47 } 48 else{ 49 if(q[i].type==1&&q[i].y<=mid)add(q[i].x,1); 50 if(q[i].type==2&&q[i].y<=mid)add(q[i].x,-1); 51 if(q[i].y<=mid)c1[++lnow]=q[i]; 52 else c2[++rnow]=q[i]; 53 } 54 } 55 for(int i=l;i<=r;i++){ 56 if(q[i].type==1&&q[i].y<=mid)add(q[i].x,-1); 57 if(q[i].type==2&&q[i].y<=mid)add(q[i].x,1); 58 } 59 for(int i=1;i<=lnow;i++){ 60 q[l+i-1]=c1[i]; 61 } 62 for(int i=1;i<=rnow;i++){ 63 q[l+lnow+i-1]=c2[i]; 64 } 65 solve(l,l+lnow-1,L,mid); 66 solve(l+lnow,r,mid+1,R); 67 } 68 int main(){ 69 while(~scanf("%d",&n)){ 70 mx=0;cnt=0;tot=0; 71 for(int i=1;i<=n;i++){ 72 scanf("%d",&a[i]); 73 q[++cnt].type=1;q[cnt].x=i;q[cnt].y=a[i]; 74 mx=max(mx,a[i]); 75 } 76 scanf("%d",&m); 77 for(int i=1;i<=m;i++){ 78 int k; 79 scanf("%d",&k); 80 if(k==1){ 81 int x,y; 82 scanf("%d%d",&x,&y); 83 q[++cnt].type=2;q[cnt].x=x;q[cnt].y=a[x]; 84 q[++cnt].type=1;q[cnt].x=x;q[cnt].y=y; 85 a[x]=y; 86 mx=max(mx,y); 87 } 88 else{ 89 int x,y,k; 90 scanf("%d%d%d",&x,&y,&k); 91 q[++cnt].type=3;q[cnt].x=x;q[cnt].y=y;q[cnt].k=k; 92 q[cnt].w=++tot; 93 } 94 } 95 solve(1,cnt,1,mx); 96 for(int i=1;i<=tot;i++){ 97 printf("%d\n",ans[i]); 98 } 99 }100 return 0;101 }