#分块，二分#zoj 2112 Dynamic Rankings

本文主要是介绍#分块，二分#zoj 2112 Dynamic Rankings，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目

支持修改的区间动态第k小

分析

树状数组套主席树（主席树不支持单点修改）太麻烦了，所以就用一种虽然时间略长但是比较简短的代码，当然运用到大段维护，小段朴素的方法，具体就是二分答案，其实理解上去还是比较简单的

代码

#include <cstdio>
#include <cmath>
#include <algorithm>
#define rr register
#define L(x) ((x-1)*bk+1)
#define R(x) (x*bk>n?n:x*bk)
#define max(a,b) ((a>b)?a:b)
int n,a[50001],b[50001],pos[50001];
inline int in(){//逐字符输入rr int ans=0; rr char c=getchar();while (c<48||c>57) c=getchar();while (c>47&&c<58) ans=ans*10+c-48,c=getchar();return ans;
}
inline void resort(int x,int bk){//分块的思想（大段维护），所以要排序rr int l=L(x),r=R(x);for (rr int i=l;i<=r;++i) b[i]=a[i];std::sort(b+l,b+1+r);
}
inline void print(int ans){//逐字符输出if (ans>9) print(ans/10);putchar(ans%10+48);
}
inline int answ(int l,int r,int v,int bk){rr int ans=0;if (pos[l]==pos[r]){//小段朴素for (rr int i=l;i<=r;++i) ans+=a[i]<=v;}else{for (rr int i=l;i<=R(pos[l]);++i) ans+=a[i]<=v;for (rr int i=pos[l]+1;i<pos[r];++i) ans+=std::upper_bound(b+L(i),b+1+R(i),v)-b-L(i);//大段维护for (rr int i=L(pos[r]);i<=r;++i) ans+=a[i]<=v;}return ans;
}
int main(){rr int t=in();while (t--){n=in(); rr int m=in(); rr int block=sqrt(n);rr int k=n/block,mx=0; if (n%block) k++;for (rr int i=1;i<=n;++i) a[i]=in(),mx=max(a[i],mx);//剪枝（不必要的就不要）for (rr int i=1;i<=n;++i) pos[i]=(i-1)/block+1;for (rr int i=1;i<=k;++i) resort(i,block);//初始分块while (m--){rr char c=getchar(); while (c!='Q'&&c!='C') c=getchar();  rr int x=in();if (c=='C') a[x]=in(),mx=max(a[x],mx),resort(pos[x],block);//修改else{rr int y=in(),k=in(); rr int l=1,r=mx;//二分答案while (l<r){rr int mid=(l+r)>>1;if (answ(x,y,mid,block)>=k) r=mid; else l=mid+1;}print(l); putchar('\n');}}}return 0;
}