【算法】整体二分初探[通俗易懂]

Java架构师必看

发布于 2022-01-21 08:23:58

1840

发布于 2022-01-21 08:23:58

大家好，我是架构君，一个会写代码吟诗的架构师。今天说一说【算法】整体二分初探,希望能够帮助大家进步!!!

　　整体二分好喵喵~长得很像决策单调性的分治优化，它能够帮助你不用写各种树套主席树就能很轻易地求出第k小数233333（大雾

　　首先确定一个决策区间solve(l, r, L, R)表示编号在L~R的操作的数的权值和询问的答案在l~r这个区间，每次将答案二分，把L~R里的修改操作按被修改数的权值<=mid和>mid分成左右两边，如果<=mid，就把它下标所在位置在bit里+1，把L~R里的查询操作按bit上查询区间里的sum>=k和<k分成左右两边，如果<k，那么k就要减去bit上查询区间里的sum，然后就按丢到左右两边的操作分治就好了。

　　应该还是不难理解的，虽然将操作和询问分成左右两边修改了原顺序，但是会互相影响的操作之间一定是按原顺序进行的，因为修改的排名大的数对排名小的数无影响，先处理答案小的，所以处理答案大的时候k已经减去了答案小的时候的贡献，于是处理答案大的区间的时候实际也不受到答案小的区间的影响，这样就能做到一层O(N)，一共log(N)层，加上bit复杂度log(N)，总复杂度O(Nlog^2N)。

整体二分的具体流程：

void solve(int l, int r, int L, int R)
{
    if(l>r || L>R) return;
    if(l==r) 
    {
        for(int i=L;i<=R;i++) if(q[i].ty) ans[q[i].pos]=l; //如果q[i].ty==1是询问，就把答案丢进去 
        return;
    }
    int mid=(l+r)>>1, cnt1=0, cnt2=0; //二分答案 
    for(int i=L;i<=R;i++)
    if(q[i].ty)
    {
        int tmp=query(q[i].y)-query(q[i].x-1); //求bit上询问区间的sum
        if(tmp>=q[i].k) q1[++cnt1]=q[i]; //<=k就丢左边
        else q[i].k-=tmp, q2[++cnt2]=q[i]; //>k就更新k后丢右边 
    }
    else
    {
        if(q[i].x<=mid) add(q[i].pos, q[i].y), q1[++cnt1]=q[i]; //如果被修改数<=mid，就更新bit并丢到左边
        else q2[++cnt2]=q[i]; 
    }
    for(int i=1;i<=cnt1;i++) if(!q1[i].ty) add(q1[i].pos, -q1[i].y); //如果是修改，删去在bit上的值
    for(int i=1;i<=cnt1;i++) q[L+i-1]=q1[i]; //丢到左边~ 
    for(int i=1;i<=cnt2;i++) q[L+cnt1+i-1]=q2[i]; //丢到右边~ 
    solve(l, mid, L, L+cnt1-1); solve(mid+1, r, L+cnt1, R); //分治~ 
}

View Code

例题时间~

　　例1 POJ2104 K-th Number

　　就是个裸的求区间第k小...大模板

此代码由Java架构师必看网-架构君整理
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath>
using namespace std;
const int maxn=500010, inf=1e9;
struct poi{int x, y, k, pos, ty;}q[maxn], q1[maxn], q2[maxn];
int n, m, x, y, k, cnt, cnt1, cnt2;
int tree[maxn], ans[maxn], a[maxn];
inline void read(int &k)
{
    int f=1; k=0; char c=getchar();
    while(c<'0' || c>'9') c=='-' && (f=-1), c=getchar();
    while(c<='9' && c>='0') k=k*10+c-'0', c=getchar();
    k*=f;
}
inline void add(int x, int delta){for(;x<=n;x+=x&-x) tree[x]+=delta;}
inline int query(int x) {int sum=0; for(;x;x-=x&-x) sum+=tree[x]; return sum;}
void solve(int l, int r, int L, int R)
{
    if(l>r || L>R) return;
    if(l==r)
    {
        for(int i=L;i<=R;i++) if(q[i].ty) ans[q[i].pos]=l;
        return;
    }
    int mid=(l+r)>>1, cnt1=0, cnt2=0;
    for(int i=L;i<=R;i++)
    if(q[i].ty)
    {
        int tmp=query(q[i].y)-query(q[i].x-1);
        if(tmp>=q[i].k) q1[++cnt1]=q[i];
        else q[i].k-=tmp, q2[++cnt2]=q[i];
    }
    else
    {
        if(q[i].x<=mid) q1[++cnt1]=q[i], add(q[i].pos, q[i].y);
        else q2[++cnt2]=q[i];
    }
    for(int i=1;i<=cnt1;i++) if(!q1[i].ty) add(q1[i].pos, -q1[i].y);
    for(int i=1;i<=cnt1;i++) q[L+i-1]=q1[i];
    for(int i=1;i<=cnt2;i++) q[L+cnt1+i-1]=q2[i];
    solve(l, mid, L, L+cnt1-1); solve(mid+1, r, L+cnt1, R);
}
int main()
{
    read(n); read(m);
    for(int i=1;i<=n;i++) read(x), q[++cnt]=(poi){x, 1, 0, i, 0};
    for(int i=1;i<=m;i++) read(x), read(y), read(k), q[++cnt]=(poi){x, y, k, i, 1};
    solve(-inf, inf, 1, cnt);
    for(int i=1;i<=m;i++) printf("%d\n", ans[i]);
}

View Code

　　例2 bzoj1901: Zju2112 Dynamic Rankings

　　就多了一个修改，那常数就比BIT套主席树优越啦，复杂度又一样，跑的就飞快~

#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath>
using namespace std;
const int maxn=500010, inf=1e9;
struct poi{int x, y, k, pos, ty;}q[maxn], q1[maxn], q2[maxn];
int n, m, x, y, k, cnt, cnt1, cnt2, tot;
int tree[maxn], ans[maxn], a[maxn];
char s[2];    
inline void read(int &k)
{
    int f=1; k=0; char c=getchar();
    while(c<'0' || c>'9') c=='-' && (f=-1), c=getchar();
    while(c<='9' && c>='0') k=k*10+c-'0', c=getchar();
    k*=f;
}
inline void add(int x, int delta){for(;x<=n;x+=x&-x) tree[x]+=delta;}
inline int query(int x) {int sum=0; for(;x;x-=x&-x) sum+=tree[x]; return sum;}
void solve(int l, int r, int L, int R)
{
    if(l>r || L>R) return;
    if(l==r)
    {
        for(int i=L;i<=R;i++) if(q[i].ty) ans[q[i].pos]=l;
        return;
    }
    int mid=(l+r)>>1, cnt1=0, cnt2=0;
    for(int i=L;i<=R;i++)
    if(q[i].ty)
    {
        int tmp=query(q[i].y)-query(q[i].x-1);
        if(tmp>=q[i].k) q1[++cnt1]=q[i];
        else q[i].k-=tmp, q2[++cnt2]=q[i];
    }
    else
    {
        if(q[i].x<=mid) add(q[i].pos, q[i].y), q1[++cnt1]=q[i];
        else q2[++cnt2]=q[i];
    }
    for(int i=1;i<=cnt1;i++) if(!q1[i].ty) add(q1[i].pos, -q1[i].y);
    for(int i=1;i<=cnt1;i++) q[L+i-1]=q1[i];
    for(int i=1;i<=cnt2;i++) q[L+cnt1+i-1]=q2[i];
    solve(l, mid, L, L+cnt1-1); solve(mid+1, r, L+cnt1, R);
}
int main()
{
    read(n); read(m);
    for(int i=1;i<=n;i++) read(a[i]), q[++cnt]=(poi){a[i], 1, 0, i, 0};
    for(int i=1;i<=m;i++) 
    {
        scanf("%s", s+1);
        if(s[1]=='Q') read(x), read(y), read(k), q[++cnt]=(poi){x, y, k, ++tot, 1};
        else read(x), read(y), q[++cnt]=(poi){a[x], -1, 0, x, 0}, q[++cnt]=(poi){a[x]=y, 1, 0, x, 0};
    }
    solve(-inf, inf, 1, cnt);
    for(int i=1;i<=tot;i++) printf("%d\n", ans[i]);
}

View Code

　　例3 bzoj3110: Zjoi2013K大数查询

　　这次要插入一个区间的数，那么如果插入的数<=mid就用线段树给那一段区间全部+1就好了...

　　第k大就n-c+1求第k小最后输出n-ans+1就好了...

此代码由Java架构师必看网-架构君整理
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#define int long long
using namespace std;
const int maxn=50010, inf=2147483647;
struct poi{int x, y, k, pos, ty;}q[maxn], q1[maxn], q2[maxn];
struct tjm{int sum, delta;}tree[maxn<<2];
int n, m, ty, x, y, z, cnt, cnt1, cnt2, tot, N;
int ans[maxn];
inline void read(int &k)
{
    int f=1; k=0; char c=getchar();
    while(c<'0' || c>'9') c=='-' && (f=-1), c=getchar();
    while(c<='9' && c>='0') k=k*10+c-'0', c=getchar();
    k*=f;
}
inline void up(int x){tree[x].sum=tree[x<<1].sum+tree[x<<1|1].sum;}
inline void down(int x, int l, int r)
{
    int mid=(l+r)>>1;
    tree[x<<1].delta+=tree[x].delta; tree[x<<1|1].delta+=tree[x].delta;
    tree[x<<1].sum+=tree[x].delta*(mid-l+1); tree[x<<1|1].sum+=tree[x].delta*(r-mid);
    tree[x].delta=0;
}
void update(int x, int l, int r, int cl, int cr, int delta)
{
    if(cl<=l && r<=cr) {tree[x].delta+=delta; tree[x].sum+=delta*(r-l+1); return;}
    down(x, l, r);
    int mid=(l+r)>>1;
    if(cl<=mid) update(x<<1, l, mid, cl, cr, delta);
    if(cr>mid) update(x<<1|1, mid+1, r, cl, cr, delta);
    up(x);
}
int query(int x, int l, int r, int cl, int cr)
{
    if(cl<=l && r<=cr) return tree[x].sum;
    down(x, l, r);
    int mid=(l+r)>>1, ans=0;
    if(cl<=mid) ans=query(x<<1, l, mid, cl, cr);
    if(cr>mid) ans+=query(x<<1|1, mid+1, r, cl, cr);
    return ans;
}
void solve(int l, int r, int L, int R)
{
    if(l>r || L>R) return;
    if(l==r)
    {
        for(int i=L;i<=R;i++) if(q[i].ty) ans[q[i].pos]=n-l+1;
        return;
    }
    int mid=(l+r)>>1, cnt1=0, cnt2=0;
    for(int i=L;i<=R;i++)
    if(q[i].ty)
    {
        int tmp=query(1, 1, n, q[i].x, q[i].y);
        if(tmp>=q[i].k) q1[++cnt1]=q[i];
        else q[i].k-=tmp, q2[++cnt2]=q[i];
    }
    else
    {
        if(q[i].k<=mid) update(1, 1, n, q[i].x, q[i].y, 1), q1[++cnt1]=q[i];
        else q2[++cnt2]=q[i];
    }
    for(int i=1;i<=cnt1;i++) if(!q1[i].ty) update(1, 1, n, q1[i].x, q1[i].y, -1);
    for(int i=1;i<=cnt1;i++) q[L+i-1]=q1[i];
    for(int i=1;i<=cnt2;i++) q[L+cnt1+i-1]=q2[i];
    solve(l, mid, L, L+cnt1-1); solve(mid+1, r, L+cnt1, R);
}
#undef int
int main()
{
    read(n); read(m);
    for(int i=1;i<=m;i++) 
    {
        read(ty); read(x); read(y); read(z);
        if(ty==1) q[i]=(poi){x, y, n-z+1, i, 0};
        else q[i]=(poi){x, y, z, ++tot, 1};
    }
    solve(1, n, 1, m);
    for(int i=1;i<=tot;i++) printf("%lld\n", ans[i]);
}

View Code

例4 bzoj2738: 矩阵乘法

　　就是把例1改成二维树状数组即可...

#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
using namespace std;
const int maxn=500010, inf=1e9;
struct poi{int x1, yy1, x2, y2, k, pos;}q[maxn], q1[maxn], q2[maxn];
int n, m, x1, yy1, x2, y2, cnt, x, k, mx;
int tree[510][510], ans[maxn];
inline void read(int &k)
{
    int f=1; k=0; char c=getchar();
    while(c<'0' || c>'9') c=='-' && (f=-1), c=getchar();
    while(c<='9' && c>='0') k=k*10+c-'0', c=getchar();
    k*=f;
}
inline void add2(int x, int y, int delta) {for(;y<=n;y+=y&-y) tree[x][y]+=delta;}
inline void add1(int x, int y, int delta) {for(;x<=n;x+=x&-x) add2(x, y, delta);}
inline int query2(int x, int y) {int sum=0; for(;y;y-=y&-y) sum+=tree[x][y]; return sum;}
inline int query1(int x, int y) {int sum=0; for(;x;x-=x&-x) sum+=query2(x, y); return sum;}
inline int query(int x1, int yy1, int x2, int y2) 
{return query1(x2, y2)-query1(x1-1, y2)-query1(x2, yy1-1)+query1(x1-1, yy1-1);}
void solve(int l, int r, int L, int R)
{
    if(l>r || L>R) return;
    if(l==r)
    {
        for(int i=L;i<=R;i++) if(q[i].pos) ans[q[i].pos]=l;
        return;
    }
    int mid=(l+r)>>1, cnt1=0, cnt2=0;
    for(int i=L;i<=R;i++)
    if(q[i].pos)
    {
        int tmp=query(q[i].x1, q[i].yy1, q[i].x2, q[i].y2);
        if(tmp>=q[i].k) q1[++cnt1]=q[i];
        else q[i].k-=tmp, q2[++cnt2]=q[i];
    }
    else
    {
        if(q[i].k<=mid) add1(q[i].x1, q[i].yy1, 1), q1[++cnt1]=q[i];
        else q2[++cnt2]=q[i];
    }
    for(int i=1;i<=cnt1;i++) if(!q1[i].pos) add1(q1[i].x1, q1[i].yy1, -1);
    for(int i=1;i<=cnt1;i++) q[L+i-1]=q1[i];
    for(int i=1;i<=cnt2;i++) q[L+cnt1+i-1]=q2[i];
    solve(l, mid, L, L+cnt1-1); solve(mid+1, r, L+cnt1, R);
}
inline int max(int a, int b){return a>b?a:b;}
int main()
{
    read(n); read(m);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++) read(x), q[++cnt]=(poi){i, j, 0, 0, x, 0}, mx=max(mx, x);
    for(int i=1;i<=m;i++)
    {
        read(x1); read(yy1); read(x2); read(y2); read(k);
        q[++cnt]=(poi){x1, yy1, x2, y2, k, i};       
    }
    solve(0, mx+1, 1, cnt);
    for(int i=1;i<=m;i++) printf("%d\n", ans[i]);
}

View Code

持续更新中~

　　资料：http://blog.csdn.net/lwt36/article/details/50669972

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

编程算法

登录后参与评论

0 条评论

热度

【算法】整体二分初探[通俗易懂]

【算法】整体二分初探[通俗易懂]

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐