[关闭]
@xiaoziyao 2021-07-15T13:44:53.000000Z 字数 10349 阅读 1052

整体二分学习笔记

分治 学习笔记

更好的阅读体验

简介

整体二分是将多次二分用一次二分来实现的算法，使用整体二分的条件：

  1. 询问的答案具有可二分性
  2. 修改对判定答案的贡献互相独立，修改之间互不影响结果
  3. 修改如果对判定答案有贡献，那么贡献为一确定的与判定标准无关的值
  4. 贡献满足交换律、结合律，具有可加性
  5. 题目允许离线算法
    （by 徐浩然《浅谈数据结构题的几个非经典解法》）

其实我们简单点看，就是题目可以离线，可以二分（即答案有单调性），且修改产生的贡献之间可以相互叠加（这是我口胡的）
再引用一段吧：

询问的答案可二分且修改对判定标准的贡献相对独立，且贡献的值与判定标准无关。因此如果我们已经计算过某一些修改对询问的贡献，那么这个贡献永远不会改变，我们没有必要当判定标准改变时再次计算这部分修改的贡献，只要记录下当前的总贡献，再进一步二分时，直接加上新的贡献即可。
（by 徐浩然《浅谈数据结构题的几个非经典解法》）

提一下整体二分的时间复杂度吧（主要是怕忘了），对于大部分的整体二分，时间复杂度为：，为操作次数，为值域，为数字个数。带的原因是整体二分将左右两个子区间的操作分开需要遍历一遍询问，带的原因是整体二分递归下去最多层（因为大部分的整体二分是二分值域），带的原因是树状数组需要带（这一段可以不用先理解，看了几道题目后再来看都没有关系）。

接下来，我们用几道例题来了解与掌握整体二分：

例题1：SP3946 MKTHNUM - K-th Number

题意：个数，个询问求静态区间第小，数据范围：

分析：
虽然这道题可以用主席树和树套树过，但是为了练习整体二分，我们需要用整体二分通过这道题。

我们先考虑二分的做法：对于每个询问，先将所有的数加入树状数组中（加入前记得清零），然后二分值域，设当前二分到了区间，且，那么就是小于等于的数的个数。如果，那么，即区间向左缩小；如果，那么，即区间向右缩小，最后的时候，就是区间第小。
然而，分析一下复杂度，到了，这个时间复杂度显然是不可以接受的，我们可以考虑将所有询问一次二分实现。

整体二分具体怎么做呢（其实有点像分治）？我们维护一个操作序列，包含所有的修改和查询操作，很容易知道一共有个操作。

  1. struct qst{
  2.     int x,y,z,o;
  3. }q[maxn],lq[maxn],rq[maxn];

注：其中为操作的类型，表示该操作为修改，将位置上的数增加，z是纯粹摆着看的；表示该操作为查询，且查询编号为，你需要给出区间第小的数的值。
数组和数组可以暂时不管。

之后，我们定义一个函数，表示当前分治到区间，当前包含的操作在操作序列里的位置是[l,r]（这里的位置[l,r]为什么是连续的且包含当前所有的操作暂时不用去想，后面窝会给一个解释的）：

  1. void divide(int L,int R,int l,int r)

如果操作区间为空，那么直接返回：

  1. if(l>r)
  2.     return ;

先考虑L==R的情况，此时这个操作区间内的所有询问操作的答案一定是L（二分的性质），即：

  1. if(L==R){
  2.     for(int i=l;i<=r;i++)
  3.         if(q[i].o!=0)
  4.             ans[q[i].o]=L;
  5.     return ;
  6. }

否则，我们把当前区间分为[L,mid]和[mid+1,R]，并将当前的所有操作分类，即：对于修改操作，右区间小于等于mid的保存在lq数组里，分到左区间进行分治；其他的保存在rq数组里，分到右区间进行分治。对于查询操作，答案在左区间的保存在lq数组里，分到左区间进行分治；其他的保存在rq数组里，分到右区间进行分治。
有两个问题：
1. 如何知道哪些操作的答案在左区间，哪些操作的答案在右区间。
2. 这个操作区间看上去是不可以打乱顺序的，如何解决顺序被打乱的影响。（因为这个区间有时间顺序，如果时间顺序乱了，显然答案会有改变）
有一个玄学的操作可以解决这两个问题，不仅可以让我们知道答案在哪个区间，而且可以消除时间顺序被打乱的影响：对于所有分到右区间的查询操作[l',r',k]，将在这个操作之前的所有分到左区间的修改操作保存到树状数组里。那么我们可以发现query(r')-query(l'-1)就是这些分到左区间的修改操作对这个询问的所有贡献，我们用now来表示。因此，如果k\leqslant now，则答案在左区间内，否则在右区间内。对于在右区间的答案，我们将k减去now，这样就可以消除在这个操作之前分到左区间的所有修改操作对这个查询的影响。
这样，我们就可以肆无忌惮地把这两个区间提取出来，改变这些操作在原操作序列的顺序了！（这就解决了之前为什么所有操作都在一个区间内的问题）
给一下这一个部分的代码：

  1. int lcnt=0,rcnt=0,mid=(L+R)>>1;
  2. for(int i=l;i<=r;i++){
  3.     if(q[i].o==0){
  4.         if(q[i].y<=mid){
  5.             update(q[i].x,1);
  6.             lq[++lcnt]=q[i];
  7.         }
  8.         else rq[++rcnt]=q[i];
  9.     }
  10.     else{
  11.         int now=query(q[i].y)-query(q[i].x-1);
  12.         if(q[i].z<=now)
  13.             lq[++lcnt]=q[i];
  14.         else{
  15.             rq[++rcnt]=q[i];
  16.             rq[rcnt].z-=now;
  17.         }
  18.     }
  19. }

然后，我们把树状数组清空，并把lq数组与rq数组保存到操作序列q里面：

  1. for(int i=l;i<=r;i++)
  2.     if(q[i].o==0&&q[i].y<=mid)
  3.         update(q[i].x,-1);
  4. for(int i=1;i<=lcnt;i++)
  5.     q[i+l-1]=lq[i];
  6. for(int i=1;i<=rcnt;i++)
  7.     q[i+l+lcnt-1]=rq[i];

最后，我们像线段树或者cdq分治一样，向下递归，即：

  1. divide(L,mid,l,l+lcnt-1);
  2. divide(mid+1,R,l+lcnt,r);

完整代码：

  1. #include<stdio.h>
  2. #define lowbit(x) x&-x
  3. #define inf 1000000000
  4. const int maxn=400005;
  5. int i,j,k,m,n;
  6. int t[maxn],ans[maxn];
  7. struct qst{
  8.     int x,y,z,o;
  9. }q[maxn],lq[maxn],rq[maxn];
  10. void update(int x,int v){
  11.     for(int i=x;i<maxn;i+=lowbit(i))
  12.         t[i]+=v;
  13. }
  14. int query(int x){
  15.     int res=0;
  16.     for(int i=x;i;i-=lowbit(i))
  17.         res+=t[i];
  18.     return res;
  19. }
  20. void divide(int L,int R,int l,int r){
  21.     if(l>r)
  22.         return ;
  23.     if(L==R){
  24.         for(int i=l;i<=r;i++)
  25.             if(q[i].o!=0)
  26.                 ans[q[i].o]=L;
  27.         return ;
  28.     }
  29.     int lcnt=0,rcnt=0,mid=(L+R)>>1;
  30.     for(int i=l;i<=r;i++){
  31.         if(q[i].o==0){
  32.             if(q[i].y<=mid){
  33.                 update(q[i].x,1);
  34.                 lq[++lcnt]=q[i];
  35.             }
  36.             else rq[++rcnt]=q[i];
  37.         }
  38.         else{
  39.             int now=query(q[i].y)-query(q[i].x-1);
  40.             if(q[i].z<=now)
  41.                 lq[++lcnt]=q[i];
  42.             else{
  43.                 rq[++rcnt]=q[i];
  44.                 rq[rcnt].z-=now;
  45.             }
  46.         }
  47.     }
  48.     for(int i=l;i<=r;i++)
  49.         if(q[i].o==0&&q[i].y<=mid)
  50.             update(q[i].x,-1);
  51.     for(int i=1;i<=lcnt;i++)
  52.         q[i+l-1]=lq[i];
  53.     for(int i=1;i<=rcnt;i++)
  54.         q[i+l+lcnt-1]=rq[i];
  55.     divide(L,mid,l,l+lcnt-1);
  56.     divide(mid+1,R,l+lcnt,r);
  57. }
  58. int main(){
  59.     scanf("%d%d",&n,&m);
  60.     for(i=1;i<=n;i++){
  61.         int x;
  62.         scanf("%d",&x);
  63.         q[i].o=0,q[i].x=i,q[i].y=x,q[i].z=0;
  64.     }
  65.     for(i=1;i<=m;i++){
  66.         int x,y,z;
  67.         scanf("%d%d%d",&x,&y,&z);
  68.         q[n+i].o=i,q[n+i].x=x,q[n+i].y=y,q[n+i].z=z;
  69.     }
  70.     divide(-inf,inf,1,n+m);
  71.     for(i=1;i<=m;i++)
  72.         printf("%d\n",ans[i]);
  73.     return 0;
  74. }

例题2：P2617 Dynamic Rankings

题意：n个数，m个询问求动态区间第k小（单点修改，区间查询），数据范围：1\leqslant n,m\leqslant 10^5,1\leqslant N\leqslant 10^9。

分析：
这道题其实和上一道差不多（甚至divide函数几乎一模一样的），但是我们还是要对这道题进行分析。
除了修改之外，其他的操作我们可以直接复制过来（因为一模一样）。然后，我们开始考虑修改。
修改是单点赋值，但是如果你如果用单点赋值当成操作的话你显然抵消不了之前的修改（或赋值）操作，因此我们可以把赋值拆成减去原来的值和加上现在的值，因此可以用一个数组a来模拟数组的修改，然后把赋值a_x=y变成两个修改[x,a[x],-1]和[x,y,1]。（注：修改[a,b,c]指在a的位置，b的值加上c）
然后我们就可以愉快的复制粘贴写代码了！

完整代码：

  1. #include<stdio.h>
  2. #define lowbit(x) x&-x
  3. #define inf 1000000000
  4. const int maxn=400005;
  5. int i,j,k,m,n,cnt,qs;
  6. int t[maxn],ans[maxn],a[maxn];
  7. char c;
  8. struct qst{
  9.     int x,y,z,o;
  10. }q[maxn],lq[maxn],rq[maxn];
  11. void update(int x,int v){
  12.     for(int i=x;i<maxn;i+=lowbit(i))
  13.         t[i]+=v;
  14. }
  15. int query(int x){
  16.     int res=0;
  17.     for(int i=x;i;i-=lowbit(i))
  18.         res+=t[i];
  19.     return res;
  20. }
  21. void divide(int L,int R,int l,int r){
  22.     if(l>r)
  23.         return ;
  24.     if(L==R){
  25.         for(int i=l;i<=r;i++)
  26.             if(q[i].o!=0)
  27.                 ans[q[i].o]=L;
  28.         return ;
  29.     }
  30.     int lcnt=0,rcnt=0,mid=(L+R)>>1;
  31.     for(int i=l;i<=r;i++){
  32.         if(q[i].o==0){
  33.             if(q[i].y<=mid){
  34.                 update(q[i].x,q[i].z);
  35.                 lq[++lcnt]=q[i];
  36.             }
  37.             else rq[++rcnt]=q[i];
  38.         }
  39.         else{
  40.             int now=query(q[i].y)-query(q[i].x-1);
  41.             if(q[i].z<=now)
  42.                 lq[++lcnt]=q[i];
  43.             else{
  44.                 rq[++rcnt]=q[i];
  45.                 rq[rcnt].z-=now;
  46.             }
  47.         }
  48.     }
  49.     for(int i=l;i<=r;i++)
  50.         if(q[i].o==0&&q[i].y<=mid)
  51.             update(q[i].x,-q[i].z);
  52.     for(int i=1;i<=lcnt;i++)
  53.         q[i+l-1]=lq[i];
  54.     for(int i=1;i<=rcnt;i++)
  55.         q[i+l+lcnt-1]=rq[i];
  56.     divide(L,mid,l,l+lcnt-1);
  57.     divide(mid+1,R,l+lcnt,r);
  58. }
  59. int main(){
  60.     scanf("%d%d",&n,&m);
  61.     for(i=1;i<=n;i++){
  62.         int x;
  63.         scanf("%d",&x);
  64.         q[++cnt].o=0,q[cnt].x=i,q[cnt].y=x,q[cnt].z=1;
  65.         a[i]=x;
  66.     }
  67.     for(i=1;i<=m;i++){
  68.         int x,y,z;
  69.         for(c=getchar();c!='C'&&c!='Q';c=getchar());
  70.         scanf("%d%d",&x,&y); 
  71.         if(c=='C'){
  72.             q[++cnt].o=0,q[cnt].x=x,q[cnt].y=a[x],q[cnt].z=-1;
  73.             q[++cnt].o=0,q[cnt].x=x,q[cnt].y=y,q[cnt].z=1;
  74.             a[x]=y;
  75.         }
  76.         if(c=='Q'){
  77.             scanf("%d",&z);
  78.             qs++;
  79.             q[++cnt].o=qs,q[cnt].x=x,q[cnt].y=y,q[cnt].z=z;
  80.         }
  81.     }
  82.     divide(-inf,inf,1,cnt);
  83.     for(i=1;i<=qs;i++)
  84.         printf("%d\n",ans[i]);
  85.     return 0;
  86. }

例题3：P3527 [POI2011]MET-Meteors

吐槽一下，你谷评测姬好玄学啊，原来是评测姬波动把窝卡死了？？！（据说交一会儿c++交一会儿c++11交一会儿c++14交一会儿c++17有助于卡常？），交了亿遍才过QAQ（感觉评测姬在针对我/kk，快读反而变慢了）

放亿张图（没有发现这些链接都不一样吗/kel）

题意：有n个国家，还有一个分为m个点的环，每个点上都有一个所属的国家，有k次事件，第i次时间会将区间[l_i,r_i]中的所有国家（可重）增加a_i的点权，求对于所有国家i，最早在哪个时刻点权之和可以达到某一个相应的值p_i。数据范围：1\leqslant n,m,k\leqslant 3\cdot 10^5,1\leqslant a_i,p_i\leqslant 10^9

分析：
我们开始正式讲解这道题，很容易想出来这道题的二分做法（然鹅我没有码出来QAQ）：对于每个国家，我们二分答案，并将所有小于等于这个时间的事件用差分的方式全部加入树状数组内，然后我们遍历一遍这个国家占据的所有点，每个点单点查询它能获得的点权，如果这个点权之和小于要求的值，那么向右走，否则向左走。
但是我们算一算这个复杂度：O(nk\log k\log m)（枚举国家需要O(n)，二分答案为O(\log k)，添加到树状数组最劣是O(k)，树状数组的查询是O(\log m)的）

然后我们怎么把它变为整体二分呢？我们还是二分答案，除了分类之外，divide的代码是几乎一样的（所以整体二分是有个板子的），然后我们讨论一下如何分类：
很显然，修改操作是几乎和上一道题一样的，但是有一个地方需要考虑一下：因为修改操作是区间修改，查询操作是单点查询（后面会说）我们可以考虑使用树状数组差分，可以O(\log m)来解决问题。在对查询操作分类的时候，我们需要遍历这个国家占据的所有点，这些点可以用树状数组单点查询获得它的点权和，因此所有占据点的点权和就是这个国家的点权和，然后就可以进行几乎一样的分类辣！

有三个需要注意的地方：
1. 有可能存在区间[l_i,r_i]且l_i>r_i，此时应该改一下修改操作，具体见我的modfify函数。
2. 我们需要把修改放在查询的前面。
3. 记得在修改的最后放一个边界，即覆盖整个区间，且增加的点权为inf。

代码：

  1. #include<stdio.h>
  2. #include<vector>
  3. #include<string.h>
  4. #define lowbit(x) x&-x
  5. #define inf 1000000000
  6. using namespace std;
  7. const int maxn=600005;
  8. int i,j,k,m,n,cnt;
  9. int p[maxn],t[maxn],ans[maxn];
  10. vector<int>v[maxn];
  11. struct opt{
  12.     int x,y,z,o,id;
  13. }q[maxn],lq[maxn],rq[maxn];
  14. void update(int x,int v){
  15.     for(int i=x;i<=m;i+=lowbit(i))
  16.         t[i]+=v;
  17. }
  18. int query(int x){
  19.     int res=0;
  20.     for(int i=x;i;i-=lowbit(i))
  21.         res+=t[i];
  22.     return res;
  23. }
  24. void modify(int x,int y,int z){
  25.     update(x,z),update(y+1,-z);
  26.     if(x>y)
  27.         update(1,z);
  28. }   
  29. void divide(int L,int R,int l,int r){
  30.     if(l>r)
  31.         return ;
  32.     if(L==R){
  33.         for(int i=l;i<=r;i++)
  34.             if(q[i].o!=0)
  35.                 ans[q[i].id]=L;
  36.         return ;
  37.     }
  38.     int lcnt=0,rcnt=0,mid=(L+R)>>1;
  39.     for(int i=l;i<=r;i++){
  40.         if(q[i].o==0){
  41.             if(q[i].id<=mid){
  42.                 modify(q[i].x,q[i].y,q[i].z);
  43.                 lq[++lcnt]=q[i];
  44.             }
  45.             else rq[++rcnt]=q[i];
  46.         }
  47.         else{
  48.             int now=0;
  49.             for(int j=0;j<v[q[i].id].size();j++){
  50.                 now+=query(v[q[i].id][j]);
  51.                 if(now>=q[i].z)
  52.                     break;
  53.             }
  54.             if(q[i].z<=now)
  55.                 lq[++lcnt]=q[i];
  56.             else{
  57.                 rq[++rcnt]=q[i];
  58.                 rq[rcnt].z-=now;
  59.             }
  60.         }
  61.     }
  62.     for(int i=l;i<=r;i++)
  63.         if(q[i].o==0&&q[i].id<=mid)
  64.             modify(q[i].x,q[i].y,-q[i].z);
  65.     for(int i=1;i<=lcnt;i++)
  66.         q[i+l-1]=lq[i];
  67.     for(int i=1;i<=rcnt;i++)
  68.         q[i+l+lcnt-1]=rq[i];
  69.     divide(L,mid,l,l+lcnt-1);
  70.     divide(mid+1,R,l+lcnt,r);
  71. }
  72. int main(){
  73.     scanf("%d%d",&n,&m);
  74.     for(i=1;i<=m;i++){
  75.         int x;
  76.         scanf("%d",&x);
  77.         v[x].push_back(i);
  78.     }
  79.     for(i=1;i<=n;i++)
  80.         scanf("%d",&p[i]);
  81.     scanf("%d",&k);
  82.     for(i=1;i<=k;i++)
  83.         cnt++,scanf("%d%d%d",&q[cnt].x,&q[cnt].y,&q[cnt].z),q[cnt].o=0,q[cnt].id=i;
  84.     q[++cnt].x=1,q[cnt].y=m,q[cnt].z=inf,q[cnt].o=0,q[cnt].id=k+1;
  85.     for(i=1;i<=n;i++)
  86.         q[++cnt].x=i,q[cnt].y=0,q[cnt].z=p[i],q[cnt].o=1,q[cnt].id=i;
  87.     divide(1,k+1,1,cnt);
  88.     for(i=1;i<=n;i++){
  89.         if(ans[i]==k+1)
  90.             puts("NIE");
  91.         else printf("%d\n",ans[i]);
  92.     }
  93.     return 0;
  94. }

例题4：P1527 [国家集训队]矩阵乘法

看到这是国集的题，好怕怕/jk/fad

题意：给定一个n\times n的矩阵，每次求一个子矩阵的k小数。

代码：
1.极限卡常的60pts代码：

  1. #include<stdio.h>
  2. #include<algorithm>
  3. #define lowbit(x) x&-x
  4. #define inf 1000000000
  5. using namespace std;
  6. const int maxn=505,maxm=400005;
  7. int i,j,k,m,n,cnt,tot,nums;
  8. int t[maxn][maxn],rec[maxn*maxn],ans[maxm];
  9. struct opt{
  10.     int a,b,c,d,k,o,id;
  11. }q[maxm],lq[maxm],rq[maxm];
  12. struct data{
  13.     int x,y,v;
  14. }num[maxn*maxn];
  15. inline int cmp(data a,data b){
  16.     return a.v<b.v;
  17. }
  18. inline void read(int &x){
  19.     char c=getchar();
  20.     x=0;
  21.     for(;c<'0'||c>'9';c=getchar());
  22.     for(;c>='0'&&c<='9';c=getchar())
  23.         x=x*10+c-48;
  24. }
  25. void update(int x,int y,int v){
  26.     for(int i=x;i<=n;i+=lowbit(i))
  27.         for(int j=y;j<=n;j+=lowbit(j))
  28.             t[i][j]+=v;
  29. }
  30. int query(int x,int y){
  31.     int res=0;
  32.     if(x==0||y==0)
  33.         return res;
  34.     for(int i=x;i;i-=lowbit(i))
  35.         for(int j=y;j;j-=lowbit(j))
  36.             res+=t[i][j];
  37.     return res;
  38. }
  39. int calc(int a,int b,int c,int d){
  40.     return query(c,d)-query(a-1,d)-query(c,b-1)+query(a-1,b-1);
  41. }
  42. void divide(int L,int R,int l,int r){
  43.     if(l>r)
  44.         return ;
  45.     if(L==R){
  46.         for(int i=l;i<=r;i++)
  47.             if(q[i].o)
  48.                 ans[q[i].id]=L;
  49.         return ;
  50.     }
  51.     int lcnt=0,rcnt=0,mid=(L+R)>>1;
  52.     for(int i=l;i<=r;i++){
  53.         if(q[i].o==0){
  54.             if(q[i].k<=mid){
  55.                 update(q[i].a,q[i].b,1);
  56.                 lq[++lcnt]=q[i];
  57.             }
  58.             else rq[++rcnt]=q[i];
  59.         }
  60.         else{
  61.             int now=calc(q[i].a,q[i].b,q[i].c,q[i].d);
  62.             if(q[i].k<=now)
  63.                 lq[++lcnt]=q[i];
  64.             else{
  65.                 rq[++rcnt]=q[i];
  66.                 rq[rcnt].k-=now;
  67.             }
  68.         }
  69.     }
  70.     for(int i=l;i<=r;i++)
  71.         if(q[i].o==0&&q[i].k<=mid)
  72.             update(q[i].a,q[i].b,-1);
  73.     for(int i=1;i<=lcnt;i++)
  74.         q[i+l-1]=lq[i];
  75.     for(int i=1;i<=rcnt;i++)
  76.         q[i+l+lcnt-1]=rq[i];
  77.     divide(L,mid,l,l+lcnt-1);
  78.     divide(mid+1,r,l+lcnt,r);
  79. }
  80. void newopt(int a,int b,int c,int d,int k,int o,int id){
  81.     cnt++,q[cnt].a=a,q[cnt].b=b,q[cnt].c=c,q[cnt].d=d,q[cnt].k=k,q[cnt].o=o,q[cnt].id=id;
  82. }
  83. int main(){
  84.     read(n),read(m);
  85.     for(i=1;i<=n;i++)
  86.         for(j=1;j<=n;j++)
  87.             nums++,read(num[nums].v),num[nums].x=i,num[nums].y=j;
  88.     sort(num+1,num+1+nums,cmp);
  89.     for(i=1;i<=nums;i++){
  90.         if(i==1||num[i].v!=num[i-1].v)
  91.             tot++,rec[tot]=num[i].v;
  92.         newopt(num[i].x,num[i].y,0,0,tot,0,0);
  93.     }
  94.     for(i=1;i<=m;i++){
  95.         int a,b,c,d,k;
  96.         read(a),read(b),read(c),read(d),read(k);
  97.         newopt(a,b,c,d,k,1,i);
  98.     }
  99.     divide(1,tot,1,cnt);
  100.     for(i=1;i<=m;i++)
  101.         printf("%d\n",rec[ans[i]]);
  102.     return 0;
  103. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注