理解整体二分[例题[Dynamic Rankings]]

理解整体二分[例题[Dynamic Rankings]]

[整体二分的概述]

大家应该知道怎么一组找静态区间第k大

二分答案出mid,如果比mid小的数的个数>k , mid变小,否则mid变大

当有很多组时,复杂度很不优秀,因此出现了整体二分

即将所有操作一起二分答案

刚刚理解整体二分时,立马想到了一幅图,与大家分享一下

想必大家看过吧

整体二分就是这么一个过程

很多询问与修改(不同颜色的球) 通过很多层筛选(递归二分) 最终到了自己颜色的那个区间(找到了答案)

而普通的二分可以理解为我们把球一个一个丢进去,等那个球找到了颜色再丢下一个,比把球一起倒进去慢了很多

进一步观察,我们可以抽象地把图理解为

[例题]

给定一个含有n个数的序列a[1],a[2],a[3]……a[n]，程序必须回答这样的询问：对于给定的i,j,k，在a[i],a[i+1],a[i+2]……a[j]中第k小的数是多少(1≤k≤j-i+1)，并且，你可以改变一些a[i]的值，改变后，程序还能针对改变后的a继续回答上面的问题。你需要编一个这样的程序，从输入文件中读入序列a，然后读入一系列的指令，包括询问指令和修改指令。

对于每一个询问指令，你必须输出正确的回答。

输入格式：

第一行有两个正整数n(1≤n≤10000)，m(1≤m≤10000)。分别表示序列的长度和指令的个数。

第二行有n个数，表示a[1],a[2]……a[n]，这些数都小于10^9。接下来的m行描述每条指令，每行的格式是下面两种格式中的一种。 Q i j k 或者 C i t

Q i j k （i,j,k是数字，1≤i≤j≤n, 1≤k≤j-i+1）表示询问指令，询问a[i]，a[i+1]……a[j]中第k小的数。C i t (1≤i≤n，0≤t≤10^9)表示把a[i]改变成为t。

输出格式：

对于每一次询问，你都需要输出他的答案，每一个输出占单独的一行。

输入样例#1：

5 3 3 2 1 4 7 Q 1 4 3 C 2 6 Q 2 5 3

输出样例#1：

3 6

[具体做法]

int mid=(l+r)>>1; for(int i=L;i<=R;i++){ if(q[i].op==1 && q[i].y<=mid) add(q[i].x,1); if(q[i].op==2 && q[i].y<=mid) add(q[i].x,-1); if(q[i].op==3) tmp[i]=quary(q[i].y)-quary(q[i].x-1);//这个区间比mid小的个数 }

我们这里要求对于每一个询问(op==3) 的区间中,小于mid的数有多少

所以op==1或2 且他们的值

在处理完tmp过后,要清空树状数组

for(int i=L;i<=R;i++){//清空树状数组 if(q[i].op==1 && q[i].y<=mid) add(q[i].x,-1); if(q[i].op==2 && q[i].y<=mid) add(q[i].x,1); }

接下来,就要把这些询问和修改分成两段

int cnt=0; for(int i=L;i<=R;i++){ if(q[i].op==3){ if(q[i].cur+tmp[i]>=q[i].k) mark[i]=1,cnt++;//放在左边 else q[i].cur+=tmp[i],mark[i]=0; } else{ if(q[i].y<=mid) mark[i]=1,cnt++; else mark[i]=0; } }

q[i].cur 表示已经有多少个数比这个Mid询问小

对于询问,只要q[i].cur+比它当前Mid小的个数>=要查询的K

那么放在左边

对于操作,只要值小于Mid也放在左边,于是分成了两部分

这两部分再重复操作,就一直分下去了

#include#define N 500005using namespace std;int n,m,a[N],ans[N],tot,sign;int tmp[N],c[N],mark[N];struct Query{int x,y,op,cur,k,id;}q[N],ret[N];int read(){ int cnt=0;char ch=0; while(!isdigit(ch))ch=getchar(); while(isdigit(ch))cnt=cnt*10+(ch-'0'),ch=getchar(); return cnt;}void add(int x,int val){ for(;x<=n;x+=x&-x) c[x]+=val;}int quary(int x){ int ans=0; for(;x;x-=x&-x) ans+=c[x]; return ans;}void Solve(int L,int R,int l,int r){//L,R为询问的区间,lr用来二分 if(L>R) return; if(l==r){ for(int i=L;i<=R;i++) ans[q[i].id]=l; return; } int mid=(l+r)>>1; for(int i=L;i<=R;i++){ if(q[i].op==1 && q[i].y<=mid) add(q[i].x,1); if(q[i].op==2 && q[i].y<=mid) add(q[i].x,-1); if(q[i].op==3) tmp[i]=quary(q[i].y)-quary(q[i].x-1);//这个区间比mid小的个数 } for(int i=L;i<=R;i++){//清空树状数组 if(q[i].op==1 && q[i].y<=mid) add(q[i].x,-1); if(q[i].op==2 && q[i].y<=mid) add(q[i].x,1); } int cnt=0; for(int i=L;i<=R;i++){ if(q[i].op==3){ if(q[i].cur+tmp[i]>=q[i].k) mark[i]=1,cnt++;//放在左边 else q[i].cur+=tmp[i],mark[i]=0; } else{ if(q[i].y<=mid) mark[i]=1,cnt++; else mark[i]=0; } } int l1=L,l2=L+cnt; for(int i=L;i<=R;i++){ if(mark[i]) ret[l1++]=q[i]; else ret[l2++]=q[i]; } for(int i=L;i<=R;i++) q[i]=ret[i]; Solve(L,l1-1,l,mid); Solve(l1,l2-1,mid+1,r);}int main(){ n=read(),m=read(); for(int i=1;i<=n;i++){ a[i]=read(); q[++tot].op=1,q[tot].x=i,q[tot].y=a[i]; } while(m--){ char ch[3]; scanf("%s",ch); if(ch[0]=='Q'){ int x=read(),y=read(),z=read(); q[++tot].op=3; q[tot].x=x,q[tot].y=y; q[tot].k=z,q[tot].id=++sign; } else{ int x=read(),y=read(); q[++tot].op=2,q[tot].x=x,q[tot].y=a[x]; q[++tot].op=1,q[tot].x=x,q[tot].y=y; a[x]=y; } } Solve(1,tot,0,1e9); for(int i=1;i<=sign;i++) printf("%d\n",ans[i]); return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。