整体二分

程序员文章站 2022-05-27 13:35:54

...

前置技能

1、二分答案

2、基础数据结构，如树状数组，线段树。

首先，二分答案求最大值的最小值大概长成下面这个样子：

int solve(int l, int r)
{
    while (l<r)
    {
        int mid=l+r>>1;
        if (check(mid)) l=mid+1; 
            else r=mid;
    }
    return l;
}

解决\(n\)次询问的时间复杂度就是\(O(n^2logn)\)

而整体二分就是用于在\(O(nlog^2n)\)的复杂度离线解决上述问题。

举一个例子，求静态区间K大。

考虑分治解决编号为\(L-R\)的操作询问的答案在\(l-r\)，每次讲答案二分（即\(mid=\frac{l+r}{2}\)）。

将\(L-R\)的修改操作按被修改数\(\leq mid\)和\(>mid\)分为\(1,2\)两部分，同时如果被修改数\(\leq mid\)，就在树状数组该位置上\(+1\)。

将\(L-R\)的询问操作按树状数组查询区间和\(\geq K\)个\(<K\)（即询问的\(K\)大）分为\(1,2\)两部分，\(<K\)的情况需要减去查询的区间和，然后分治\(1,2\)两部分即可。

一次分治的复杂度为\(O(nlogn)\)，\(logn\)次分治的复杂度即为\(O(nlog^2n)\)

具体如下（只有主*分，细节见例题代码）：

#define rep(i, l, r) for (int i=(l); i<=(r); ++i)
struct node{int l, r, k, id, type;}q[N], q1[N], q2[N];
//若type=1, 为第id个询问，询问[l,r]中k大
//若type=1，为第id个数，值为l
void solve(int l, int r, int L, int R)
{
    if(l==r) rep(i, L, R) if (q[i].type) ans[q[i].id]=l;
    int mid=l+r>>1, cnt1=0, cnt2=0;
    rep(i, L, R)
        if (q[i].type)
        {
            int k=query(q[i].r)-query(q[i].l-1);
            if (k>=q[i].k) q1[++cnt1]=q[i];
                else q2[++cnt2]=q[i], q[i].k-=k;
        }
        else
        {
            if (q[i].l<=mid) add(q[i].id, 1), q1[++cnt1]=q[i];
                else q2[++cnt2]=q[i];
        }
    //清空树状数组
    rep(i, 1, cnt1) q[L+i-1]=q1[i];
    rep(i, 1, cnt2) q[L+cnt1+i-1]=q2[i];
    solve(l, mid, L, L+cnt1-1);
    solve(mid+1, r, L+cnt1, R);
}

静态区间K大：K-th Number

#include<bits/stdc++.h>
#define rep(i, a, b) for (register int i=(a); i<=(b); ++i)
#define per(i, a, b) for (register int i=(a); i>=(b); --i)
using namespace std;
const int N=400005, inf=1e9;
struct node{int l, r, k, id, typ;}q[N], q1[N], q2[N];
int d[N], ans[N], n, m, cnt;

inline int read()
{
    int x=0,f=1;char ch=getchar();
    for (;ch<'0'||ch>'9';ch=getchar()) if (ch=='-') f=-1;
    for (;ch>='0'&&ch<='9';ch=getchar()) x=(x<<1)+(x<<3)+ch-'0';
    return x*f;
}

void add(int x, int t){for (; x<=n; x+=x&-x) d[x]+=t;}
int query(int x){int res=1; for (; x; x-=x&-x) res+=d[x]; return res;}

void solve(int l, int r, int L, int R)
{
    if (l>r || L>R) return;
    if (l==r) {rep(i, L, R) if (q[i].typ) ans[q[i].id]=l; return;}
    int mid=l+r>>1, cnt1=0, cnt2=0;
    rep(i, L, R) 
        if (q[i].typ)
        {
            int tmp=query(q[i].r)-query(q[i].l-1);
            if (tmp>=q[i].k) q1[++cnt1]=q[i]; 
                else q[i].k-=tmp, q2[++cnt2]=q[i];
        }
        else
        {
            if (q[i].l<=mid) add(q[i].id, 1), q1[++cnt1]=q[i];
                else q2[++cnt2]=q[i];
        }
    rep(i, 1, cnt1) if (!q1[i].typ) add(q1[i].id, -1);
    rep(i, 1, cnt1) q[L+i-1]=q1[i];
    rep(i, 1, cnt2) q[L+cnt1+i-1]=q2[i];
    solve(l, mid, L, L+cnt1-1); solve(mid+1, r, L+cnt1, R);
}

int main()
{
    n=read(); m=read();
    rep(i, 1, n) q[++cnt]=(node){read(), 0, 0, i, 0};
    rep(i, 1, m) q[++cnt]=(node){read(), read(), read(), i, 1};
    solve(-inf, inf, 1, cnt);
    rep(i, 1, m) printf("%d\n", ans[i]);
    return 0;
}

dalao：我会用主席树\(O(nlogn)\)在线解决该问题。

那整体二分是不是被吊锤了？看下面这题

题目传送门

即待修改的区间\(K\)大。

用整体二分与静态\(K\)大区别不大，只要注意修改时的处理即可。

细节见代码：

#include<bits/stdc++.h>
#define rep(i, a, b) for (register int i=(a); i<=(b); ++i)
#define per(i, a, b) for (register int i=(a); i>=(b); --i)
using namespace std;
const int N=500005, inf=1e9;
struct node{int l, r, k, id, typ;}q[N], q1[N], q2[N];
int d[N], ans[N], a[N], n, m, cnt, tot;

inline int read()
{
    int x=0,f=1;char ch=getchar();
    for (;ch<'0'||ch>'9';ch=getchar()) if (ch=='-') f=-1;
    for (;ch>='0'&&ch<='9';ch=getchar()) x=(x<<1)+(x<<3)+ch-'0';
    return x*f;
}

void add(int x, int t){for (; x<=n; x+=x&-x) d[x]+=t;}
int query(int x){int res=0; for (; x; x-=x&-x) res+=d[x]; return res;}

void solve(int l, int r, int L, int R)
{
    if (l>r || L>R) return;
    if (l==r) {rep(i, L, R) if (q[i].typ) ans[q[i].id]=l; return;}
    int mid=l+r>>1, cnt1=0, cnt2=0;
    rep(i, L, R) 
        if (q[i].typ)
        {
            int tmp=query(q[i].r)-query(q[i].l-1);
            if (tmp>=q[i].k) q1[++cnt1]=q[i]; 
                else q[i].k-=tmp, q2[++cnt2]=q[i];
        }
        else
        {
            if (q[i].l<=mid) add(q[i].id, q[i].r), q1[++cnt1]=q[i];
                else q2[++cnt2]=q[i];
        }
    rep(i, 1, cnt1) if (!q1[i].typ) add(q1[i].id, -q1[i].r);
    rep(i, 1, cnt1) q[L+i-1]=q1[i];
    rep(i, 1, cnt2) q[L+cnt1+i-1]=q2[i];
    solve(l, mid, L, L+cnt1-1); solve(mid+1, r, L+cnt1, R);
}

int main()
{
    n=read(); m=read();
    rep(i, 1, n) q[++cnt]=(node){a[i]=read(), 1, 0, i, 0};
    rep(i, 1, m) 
    {
        char opt[2]; scanf("%s", opt);
        if (opt[0]=='Q')
            q[++cnt]=(node){read(), read(), read(), ++tot, 1};
        else
        {
            int x=read(), y=read();
            q[++cnt]=(node){a[x], -1, 0, x, 0};
            q[++cnt]=(node){a[x]=y, 1, 0, x, 0};
        }
    }
    solve(-inf, inf, 1, cnt);
    rep(i, 1, tot) printf("%d\n", ans[i]);
    return 0;
}

dalao：我会树状数组套主席树的\(O(nlog^2n)\)在线算法。

~~但我不会啊QAQ~~

整体二分常数吊打树套树还好写QAQ

还是简单题传送门

把第一个例题的树状数组改为二维树状数组即可。

你不会二维树状数组？~~我也不会~~

#include<bits/stdc++.h>
#define rep(i, a, b) for (register int i=(a); i<=(b); ++i)
#define per(i, a, b) for (register int i=(a); i>=(b); --i)
using namespace std;
const int N=500005, inf=1e9;
struct node{int x1, y1, x2, y2, k, id;}q[N], q1[N], q2[N];
int d[505][505], ans[N], n, m, cnt;

inline int read()
{
    int x=0,f=1;char ch=getchar();
    for (;ch<'0'||ch>'9';ch=getchar()) if (ch=='-') f=-1;
    for (;ch>='0'&&ch<='9';ch=getchar()) x=(x<<1)+(x<<3)+ch-'0';
    return x*f;
}

void add1(int x, int y, int t){for (; y<=n; y+=y&-y) d[x][y]+=t;}
void add(int x, int y, int t){for (; x<=n; x+=x&-x) add1(x, y, t);}
int query2(int x, int y){int res=0; for (; y; y-=y&-y) res+=d[x][y]; return res;}
int query1(int x, int y){int res=0; for (; x; x-=x&-x) res+=query2(x, y); return res;}
int query(int x1, int y1, int x2, int y2)
{return query1(x2, y2)+query1(x1-1, y1-1)-query1(x1-1, y2)-query1(x2, y1-1);}


void solve(int l, int r, int L, int R)
{
    if (l>r || L>R) return;
    if (l==r) {rep(i, L, R) if (q[i].id) ans[q[i].id]=l; return;}
    int mid=l+r>>1, cnt1=0, cnt2=0;
    rep(i, L, R) 
        if (q[i].id)
        {
            int tmp=query(q[i].x1, q[i].y1, 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) add(q[i].x1, q[i].y1, 1), q1[++cnt1]=q[i];
                else q2[++cnt2]=q[i];
        }
    rep(i, 1, cnt1) if (!q1[i].id) add(q1[i].x1, q1[i].y1, -1);
    rep(i, 1, cnt1) q[L+i-1]=q1[i];
    rep(i, 1, cnt2) q[L+cnt1+i-1]=q2[i];
    solve(l, mid, L, L+cnt1-1); solve(mid+1, r, L+cnt1, R);
}

int main()
{
    n=read(); m=read();
    rep(i, 1, n) rep(j, 1, n)
        q[++cnt]=(node){i, j, 0, 0, read(), 0};
    rep(i, 1, m) 
        q[++cnt]=(node){read(), read(), read(), read(), read(), i};
    solve(0, inf, 1, cnt);
    rep(i, 1, m) printf("%d\n", ans[i]);
    return 0;
}

ZJOI2013 K大数查询

这题与前几题区别不大，只是有区间修改和区间查询，写一棵线段树就好了。

#include<bits/stdc++.h>
#define int long long
#define rep(i, a, b) for (register int i=(a); i<=(b); ++i)
#define per(i, a, b) for (register int i=(a); i>=(b); --i)
using namespace std;
const int N=500005;
struct node{int l, r, k, id, typ;}q[N], q1[N], q2[N];
int sum[N<<2], tag[N<<2], ans[N], n, m, tot;

inline int read()
{
    int x=0,f=1;char ch=getchar();
    for (;ch<'0'||ch>'9';ch=getchar()) if (ch=='-') f=-1;
    for (;ch>='0'&&ch<='9';ch=getchar()) x=(x<<1)+(x<<3)+ch-'0';
    return x*f;
}

void down(int rt, int l, int r)
{
    int mid=l+r>>1, ls=rt<<1, rs=rt<<1|1;
    tag[ls]+=tag[rt]; tag[rs]+=tag[rt];
    sum[ls]+=tag[rt]*(mid-l+1); sum[rs]+=tag[rt]*(r-mid);
    tag[rt]=0;
}

void add(int rt, int L, int R, int l, int r, int x)
{
    down(rt, l, r);
    if (l>=L && r<=R) {sum[rt]+=x*(r-l+1), tag[rt]+=x; return;}
    int mid=l+r>>1, ls=rt<<1, rs=rt<<1|1;
    if (mid>=L) add(ls, L, R, l, mid, x);
    if (mid<R) add(rs, L, R, mid+1, r, x);
    sum[rt]=sum[ls]+sum[rs];
}

int query(int rt, int L, int R, int l, int r)
{
    down(rt, l, r);
    if (l>=L && r<=R) return sum[rt];
    int mid=l+r>>1, ls=rt<<1, rs=rt<<1|1, res=0;
    if (mid>=L) res+=query(ls, L, R, l, mid);
    if (mid<R) res+=query(rs, L, R, mid+1, r);
    sum[rt]=sum[ls]+sum[rs]; 
    return res;
}

void solve(int L, int R, int l, int r)
{
    if (L>R || l>r) return;
    if (l==r){rep(i, L, R) if (q[i].typ) ans[q[i].id]=n-l+1; return;}
    int mid=l+r>>1, cnt1=0, cnt2=0;
    rep(i, L, R)
        if (q[i].typ) 
        {
            int tmp=query(1, q[i].l, q[i].r, 1, n);
            if (tmp>=q[i].k) q1[++cnt1]=q[i];
                else q[i].k-=tmp, q2[++cnt2]=q[i];
        }
        else
        {
            if (q[i].k<=mid) 
                add(1, q[i].l, q[i].r, 1, n, 1), q1[++cnt1]=q[i];
            else q2[++cnt2]=q[i];
        }
    rep(i, 1, cnt1) if (!q1[i].typ) 
        add(1, q1[i].l, q1[i].r, 1, n, -1);
    rep(i, 1, cnt1) q[L+i-1]=q1[i];
    rep(i, 1, cnt2) q[L+cnt1+i-1]=q2[i];
    solve(L, L+cnt1-1, l, mid); solve(L+cnt1, R, mid+1, r);
}

signed main()
{
    n=read(); m=read();
    rep(i, 1, m) 
    {
        int opt=read();
        if (opt==1) q[i]=(node){read(), read(), n-read()+1, i, 0};
        if (opt==2) q[i]=(node){read(), read(), read(), ++tot, 1};
    }
    solve(1, m, 1, n);
    rep(i, 1, tot) printf("%lld\n", ans[i]);
    return 0;
}

POI2011 MET-Meteors

套路都差不多啦\(QAQ\)，看看网上题解吧，颓不动了。。。

#include<bits/stdc++.h>
#define rep(i, a, b) for (register int i=(a); i<=(b); ++i)
#define per(i, a, b) for (register int i=(a); i>=(b); --i)
using namespace std;
const int N=600005, inf=1e9;
struct node{int l, r; long long k; int id, typ;}q[N], q1[N], q2[N];
int ans[N], a[N], p[N], n, m, K, cnt, tot;
long long d[N];

vector<int> G[N];

inline int read()
{
    int x=0,f=1;char ch=getchar();
    for (;ch<'0'||ch>'9';ch=getchar()) if (ch=='-') f=-1;
    for (;ch>='0'&&ch<='9';ch=getchar()) x=(x<<1)+(x<<3)+ch-'0';
    return x*f;
}

void add(int x, int t){for (; x<=m; x+=x&-x) d[x]+=t;}
long long query(int x){long long res=0; for (; x; x-=x&-x) res+=d[x]; return res;}

void solve(int l, int r, int L, int R)
{
    if (l>r || L>R) return;
    if (l==r) {rep(i, L, R) if (q[i].typ==1) ans[q[i].id]=l; return;}
    int mid=l+r>>1, cnt1=0, cnt2=0;
    rep(i, L, R)
    {
        if (q[i].typ==1)
        {
            long long tmp=0;
            for (int j: G[q[i].id]) 
            {
                tmp+=query(j);
                if (tmp>=q[i].k) break;
            }
            if (tmp>=q[i].k) q1[++cnt1]=q[i]; 
                else q[i].k-=tmp, q2[++cnt2]=q[i];
        }
        else
        {
            if (q[i].id<=mid)
            {
                if (q[i].typ==2)
                    add(q[i].l, q[i].k), add(q[i].r+1, -q[i].k);
                if (q[i].typ==3)
                    add(1, q[i].k), add(q[i].r+1, -q[i].k), add(q[i].l, q[i].k);
                q1[++cnt1]=q[i];
            }
            else q2[++cnt2]=q[i];
        }
    }
    rep(i, L, R) if (q[i].id<=mid) 
    {
        if (q[i].typ==2)
            add(q[i].l, -q[i].k), add(q[i].r+1, q[i].k);
        if (q[i].typ==3)
            add(1, -q[i].k), add(q[i].r+1, q[i].k), add(q[i].l, -q[i].k);
    }
    rep(i, 1, cnt1) q[L+i-1]=q1[i];
    rep(i, 1, cnt2) q[L+cnt1+i-1]=q2[i];
    solve(l, mid, L, L+cnt1-1); solve(mid+1, r, L+cnt1, R);
}

int main()
{
    n=read(); m=read();
    rep(i, 1, m) G[read()].push_back(i);
    rep(i, 1, n) p[i]=read();
    K=read();
    rep(i, 1, K)
    {
        int l=read(), r=read(), k=read();
        q[++cnt]=(node){l, r, k, i, r>=l?2:3};
    }
    rep(i, 1, n) q[++cnt]=(node){0, 0, p[i], i, 1};
    solve(1, K+1, 1, cnt);
    for (int i=1; i<=n; i++) 
        if (ans[i]^K+1) printf("%d\n", ans[i]); else puts("NIE");
    return 0;
}

写在最后

整体二分可以用于离线解决\(1e5\)级别个二分查询，通常会与树状数组或线段树共同使用，写起来还是比较套路的吧。

上一篇：整体二分

下一篇： centos7 安装clamav 进行病毒扫描查杀

整体二分

前置技能

写在最后

Python二分查找详解

JS代码实现页面打印的整体、局部

Java实现二分查找算法

做优化要关注排名，更要关注网站整体流量

SolidWorks如何整体缩放零件？

基础算法——查找(二分法)(python)

深入理解PHP几个算法:PHP冒泡、PHP二分法、PHP求素数、PHP乘法表

php二分查找二种实现示例

一份实用的seo整体优化方案

网站整体与页面关键词分布