团体二分算法讲授及例题

算法头脑

团体二分，带有二分二字那么就肯定和二分脱不了干系。
团体二分算法常用来办理扣问区间的第                              k                          k               k小值的标题，思绪如下：
我们二分的对象是这道标题给定的值域，及最小值与最大值之间的区间，在标题给定的数组中，对团体的值域举行二分，我们将                              m                      i                      d                          mid               mid作为左右区间的中心值。
比如须要查询                              l                          l               l~                              r                          r               r区间内的第                              k                          k               k小值。
然后举行一下的判定。
1.当                              l                          l               l~                              r                          r               r区间内小于中值                              m                      i                      d                          mid               mid的值的数目小于当前的查询                              k                          k               k，那就分析当前的二分值小了，由于我们须要的是第                              k                          k               k大，但是如今的                              m                      i                      d                          mid               mid可以求到的第                              p                          p               p大在前                              k                          k               k大范围内，以是还需继承查，那么就得往大的查，就将区间左侧放到当前的                              m                      i                      d                          mid               mid                              +                          +               +                              1                          1               1（                              m                      i                      d                          mid               mid的值不正当，以是无需再查）
2.但                              l                          l               l~                              r                          r               r区间内小于中值                              m                      i                      d                          mid               mid的值的数目大于便是当前的查询                              k                          k               k，那么摆列到的区间就肯定包罗前                              k                          k               k大的数，以是当前区间可用，将区间右侧放到如今的                              m                      i                      d                          mid               mid处（                              m                      i                      d                          mid               mid的值是正当的，存在准确答案）
当终极的区间左右重适时，就得到终极答案了。
而如今是一个查询的情况，当我们遇到                              q                          q               q个查询时，我们就先把查询存起来，然后就可以将查询分为两类，就是上面的两类，左区间和右区间分别用一个数组存起来，然后分类讨论就行了，至于二分，就可以用归并排序的版子。
尚有一个告急的标题：怎么查找区间内比                              m                      i                      d                          mid               mid小的值的数目？
可以思量用树状数组存，在原数组上对树状数组举行初始化就可以了。
记得每次递归清空树状数组，而且原数组的值随着上面的两个条件分配到左右两个区间去！
然后就可以找到一道板子题：P3834 【模板】可恒久化线段树 2
就是扣问的板子，就不消对标题多做分析了。代码：

1. #include<bits/stdc++.h>
2. #define int long long
3. #define xx x&-x
4. using namespace std;
5. const int N=1e6+5;
6. int n,m;
7. struct node{
8.         int l,r,k,id,op;
9. }a[N],ql[N],qr[N];
10. int answer[N];
11. int bit[N];
12. int cnt;
13. void change(int x,int p){
14.         while(x<=cnt){
15.                 bit[x]+=p;
16.                 x+=xx;
17.         }
18. }
19. int query(int x){
20.         int res=0;
21.         while(x){
22.                 res+=bit[x];
23.                 x-=xx;
24.         }
25.         return res;
26. }
27. void f(int l,int r,int N,int M){
28.         if(N>=M)return;
29.         if(l==r){
30.                 for(int i=N;i<=M;i++){
31.                         if(a[i].op==2)answer[a[i].id]=r;
32.                 }
33.                 return;
34.         }
35.         int mid=l+r>>1;
36.         int t1=0,t2=0;
37.         for(int i=N;i<=M;i++){
38.                 if(a[i].op==1){
39.                         if(mid>=a[i].l){
40.                                 ql[++t1]=a[i];
41.                                 change(a[i].id,1);
42.                         }
43.                         else{
44.                                 qr[++t2]=a[i];
45.                         }
46.                 }
47.                 else{
48.                         int x=query(a[i].r)-query(a[i].l-1);
49.                         if(x>=a[i].k){
50.                                 ql[++t1]=a[i];
51.                         }
52.                         else{
53.                                 a[i].k-=x;//这里注意减掉当前的贡献，后面就不用算了
54.                                 qr[++t2]=a[i];
55.                         }
56.                 }
57.         }
58.         for(int i=1;i<=t1;i++){
59.                 a[i+N-1]=ql[i];
60.                 if(ql[i].op==1)change(ql[i].id,-1);
61.         }
62.         for(int i=1;i<=t2;i++){
63.                 a[i+N+t1-1]=qr[i];
64.         }
65.         f(l,mid,N,N+t1-1);
66.         f(mid+1,r,N+t1,M);
67. }
68. signed main(){
69.         ios::sync_with_stdio(0);
70.         cin>>n>>m;
71.         for(int i=1;i<=n;i++){
72.                 cin>>a[i].l;
73.                 a[i].id=i;
74.                 a[i].op=1;
75.         }
76.         cnt=n;
77.         for(int i=1;i<=m;i++){
78.                 cnt++;
79.                 cin>>a[cnt].l>>a[cnt].r>>a[cnt].k;
80.                 a[cnt].id=i;
81.                 a[cnt].op=2;
82.         }
83.         f(-1e9,1e9,1,cnt);
84.         for(int i=1;i<=m;i++)cout<<answer[i]<<'\n';
85. }

复制代码

然后尚有另一道标题：P1527 [国家集训队] 矩阵乘法
由于树状数组的利用类似前缀和，以是这道题就相称于改成二位前缀和。

1. #include<bits/stdc++.h>
2. #define int long long
3. using namespace std;
4. const int N=1e6+5;
5. const int M=1005;
6. int n,m,k;
7. int T;
8. struct node{
9.         int lx,ly,rx,ry,k,idi,idj,op,id;
10. }a[N],ql[N],qr[N];
11. int answer[N];
12. int bit[M][M];
13. int cnt;
14. //快读快写好习惯
15. int read(){
16.         int x=0,p=1;
17.         char c=getchar();
18.         while(c<'0'||c>'9'){if(c=='-')p=-1;c=getchar();}
19.         while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
20.         return x*p;
21. }
22. void print(int x){
23.         if(x<0){putchar('-');x=-x;}
24.         if(x<10){putchar(x+'0');return;}
25.         print(x/10);
26.         putchar(x%10+'0');
27. }
28. void change(int x,int y,int p){
29.         for(int i=x;i<=n;i+=i&-i)for(int j=y;j<=n;j+=j&-j)bit[i][j]+=p;
30. }
31. int query(int x,int y){
32.         int res=0;
33.         for(int i=x;i;i-=i&-i)for(int j=y;j;j-=j&-j)res+=bit[i][j];
34.         return res;
35. }
36. void f(int l,int r,int N,int M){
37.         if(N>=M)return;
38.         if(l==r){
39.                 for(int i=N;i<=M;i++)if(a[i].op==2)answer[a[i].id]=r;
40.                 return;
41.         }
42.         int mid=l+r>>1;
43.         int t1=0,t2=0;
44.         for(int i=N;i<=M;i++){
45.                 if(a[i].op==1){
46.                         if(mid>=a[i].lx){
47.                                 ql[++t1]=a[i];
48.                                 change(a[i].idi,a[i].idj,1);
49.                         }
50.                         else{
51.                                 qr[++t2]=a[i];
52.                         }
53.                 }
54.                 else{
55.                         int x=query(a[i].rx,a[i].ry)+query(a[i].lx-1,a[i].ly-1)-query(a[i].lx-1,a[i].ry)-query(a[i].rx,a[i].ly-1);
56.                         if(x>=a[i].k){
57.                                 ql[++t1]=a[i];
58.                         }
59.                         else{
60.                                 a[i].k-=x;
61.                                 qr[++t2]=a[i];
62.                         }
63.                 }
64.         }
65.         for(int i=1;i<=t1;i++){
66.                 a[i+N-1]=ql[i];
67.                 if(ql[i].op==1)change(ql[i].idi,ql[i].idj,-1);
68.         }
69.         for(int i=1;i<=t2;i++){
70.                 a[i+N+t1-1]=qr[i];
71.         }
72.         f(l,mid,N,N+t1-1);
73.         f(mid+1,r,N+t1,M);
74. }
75. signed main(){
76.         ios::sync_with_stdio(0);
77.         n=read(),m=read();
78.         int tot=0;
79.         for(int i=1;i<=n;i++){
80.                 for(int j=1;j<=n;j++){
81.                         a[++tot]=node{read(),0,0,0,0,i,j,1,0};
82.                 }
83.         }
84.         cnt=tot;
85.         for(int i=1;i<=m;i++){
86.                 cnt++;
87.                 a[cnt].lx=read(),a[cnt].ly=read(),a[cnt].rx=read(),a[cnt].ry=read(),a[cnt].k=read();
88.                 a[cnt].op=2;
89.                 a[cnt].id=i;
90.         }
91.         f(0,1e9,1,cnt);
92.         for(int i=1;i<=m;i++)print(answer[i]),putchar('\n');
93. }

复制代码