题意:
一个长度为N的整数序列,编号0 - N - 1。进行Q次查询,查询编号i至j的所有数中,第K大的数是多少。
分析:
仅仅就是一道整体二分的入门题而已,没听说过整体二分?
其实就是一个分治的函数,但是呢,我所理解的,这是一个只分不治的过程。为什么?因为我们把数值域和操作域经过若干次划分划到最后,当数值域固定到一个值时,如果存在对应的操作域(此时应该是询问域)的结果就已经是这个值了,所以并不需要合并(治)。
上面这段话可能被我复杂化了?那我们简单说。(以下是求区间第k小的步骤)
这样的题一般都是给出一个序列,询问区间第k大/小。我们把这个序列看做添加一个数 a[i] 在位置 i 的操作。询问也是操作。
然后就是一个递归函数,不断二分数值的范围(数值域),每次将属于 [ l,mid ] 这个范围的添加操作以原位置在树状数组中加1,直接划到左部(操作域),将 [ mid+1,r ] 直接划到右部(不碰树状数组),对于询问呢,假如在树状数组中查询到的,位于这个区间内的1的个数小于k,证明这个区间内,左部添加的数(不大于mid的)小于k个,所以这个询问的答案一定在右部添加的数中(也就是一定比mid要大),因此,假如这个区间内的数在左部有x个,我们需要在右部求出这个区间的第k-x小的数即可,即将次询问的k减去x,划分到右部,反之,若我们在树状数组上查出来的数大于等于k,证明答案会在左部被求出,直接划分到左部即可!
我们无意间就维护了两个单调性,一个是加入顺序的单调性,另一个是数值的单调性,这二者的有机结合,恰好就是整体二分的优势,可以让其解决很多比较复杂,多处有二分性的题目。
上面的解释可能大家看了都会很迷茫,但是研究代码会让你更明白。
代码:
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cmath> 5 #include<algorithm> 6 using namespace std; 7 const int inf=0x3f3f3f3f,MAXN=200050; 8 struct node{ 9 int x,y,z,id,type; 10 }a[MAXN],al[MAXN],ar[MAXN]; 11 int n,m,ans[MAXN]; 12 struct bit{ 13 int a[MAXN]; 14 void add(int x,int y) 15 {for(;x<=n;x+=x&(-x)) a[x]+=y;} 16 int query(int x){ 17 int ans=0;for(;x;x-=x&(-x)) ans+=a[x]; 18 return ans;} 19 }t; 20 void solve(int l,int r,int ql,int qr){ 21 if(ql>qr||l>r) return ;//l和r是数值域 22 if(l==r){//ql,lr是操作域 23 for(int i=ql;i<=qr;i++) 24 ans[a[i].id]=l;return ; 25 } int mid=(l+r)>>1,lal=0,lar=0; 26 for(int i=ql;i<=qr;i++) 27 if(a[i].type){ 28 if(a[i].y<=mid){ 29 t.add(a[i].x,a[i].z); 30 al[++lal]=a[i]; 31 } else ar[++lar]=a[i]; 32 } else{ int tmp; 33 tmp=t.query(a[i].y)-t.query(a[i].x-1); 34 if(tmp>=a[i].z) al[++lal]=a[i]; 35 else ar[++lar]=a[i],ar[lar].z-=tmp; 36 } for(int i=1;i<=lal;i++) 37 if(al[i].type==1) t.add(al[i].x,-al[i].z); 38 for(int i=1,j=ql;i<=lal;i++,j++) 39 a[j]=al[i]; 40 for(int i=1,j=ql+lal;i<=lar;i++,j++) 41 a[j]=ar[i];solve(l,mid,ql,ql+lal-1); 42 solve(mid+1,r,ql+lal,qr);return ; 43 } int main(){ 44 scanf("%d",&n); 45 for(int i=1;i<=n;i++) 46 scanf("%d",&a[i].y),a[i].x=i,a[i].y=-a[i].y, 47 a[i].z=1,a[i].type=1; 48 scanf("%d",&m); 49 for(int i=1,j=n+1;i<=m;i++,j++) 50 scanf("%d%d%d",&a[j].x,&a[j].y,&a[j].z),a[j].x++,a[j].y++, 51 a[j].id=i,a[j].type=0; 52 solve(-inf,inf,1,n+m); 53 for(int i=1;i<=m;i++) 54 printf("%d ",-ans[i]); return 0; 55 }