整体二分&CDQ分治

整体二分

概念

对于一个问题，若单个询问能用二分快速解决，那么对于离线的多个询问，可以考虑使用整体二分。整体二分二分的是答案。

HDU5412

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
#define sc(p) scanf("%d",&p)
#define pr(p) printf("%d\n",p)
const int N=500100;
const int oo=0x7FFFFFFF;
struct DATA
{
    int op,k,x,y,w;
}s[N],S1[N],S2[N];
int bit[N];
void add (int x,int d) { for (int i=x; i<N; i+=i&-i) bit[i]+=d; }
int sum (int x) { int sb=0; for (int i=x; i; i-=i&-i) sb+=bit[i]; return sb; }
int a[N],ans[N];
void solve (int l,int r,int L,int R)
{
    if (l>r) return ;
    if (L==R)
    {
        for (int i=l; i<=r; i++)
            if (s[i].op==3) ans[s[i].w]=L;
        return ;
    }
    int mid=(L+R)>>1,w1=0,w2=0;
    for (int i=l; i<=r; i++)
    {
        if (s[i].op==3)
        {
            int tmp=sum (s[i].y)-sum (s[i].x-1);
            if (tmp>=s[i].k) S1[++w1]=s[i];
            else s[i].k-=tmp,S2[++w2]=s[i];
        }
        else
        {
            if (s[i].y<=mid) add (s[i].x,s[i].op),S1[++w1]=s[i];
            else S2[++w2]=s[i];
        }
    }
    for (int i=l; i<=r; i++)
        if (s[i].op!=3&&s[i].y<=mid) add (s[i].x,-s[i].op);
    for (int i=1; i<=w1; i++) s[l+i-1]=S1[i];
    for (int i=1; i<=w2; i++) s[l+w1+i-1]=S2[i];
    solve (l,l+w1-1,L,mid);
    solve (l+w1,r  ,mid+1,R);
}
int main()
{
    int n;
    while(~scanf("%d",&n))
    {
        int q,cnt=0,tot=0,ma=0;
        for (int i=1; i<=n; i++)
        {
            sc(a[i]);
            s[++cnt].op=1,s[cnt].x=i,s[cnt].y=a[i];
            ma=max (ma,a[i]);
        }
        sc(q);
        for (int i=1; i<=q; i++)
        {
            int op,x,y; sc(op),sc(x),sc(y);
            if (op==1)
            {
                s[++cnt].op=-1; s[cnt].x=x,s[cnt].y=a[x];
                s[++cnt].op=1;  s[cnt].x=x,s[cnt].y=y;
                ma=max (ma,y); a[x]=y;
            }
            else
            {
                int k; sc(k);
                s[++cnt].op=3;  s[cnt].x=x,s[cnt].y=y,s[cnt].k=k,s[cnt].w=++tot;
            }
        }
        solve (1,cnt,1,ma);
        for (int i=1; i<=tot; i++) pr(ans[i]);
    }
    return 0;
}

Luogu3332

#include <bits/stdc++.h>
#define sc(p) scanf("%d",&p)
#define pr(p) printf("%d\n",p)
const int oo=2147483640;
const int N=5010000;
using namespace std;
int bit[N+10];
void add (int x,int d) { for (int i=x; i<=N; i+=i&-i) bit[i]+=d; }
int sum (int x) { int sb=0; for (int i=x; i; i-=i&-i) sb+=bit[i]; return sb; }//蜜汁区间修改查询
struct ASK { int id,ID,val,x,y; }p[N],tmp[N];
bool ly (ASK A,ASK B) { return (A.x!=B.x) ? (A.x<B.x) : (A.id<B.id); }
int ans[N];
void solve (int l,int r)
{
    if (l==r) return ;
    int mid=(l+r)>>1;
    for (int i=l; i<=r; i++)
    {
        if (p[i].ID==0&&p[i].id<=mid) add (p[i].y,p[i].val);
        if (p[i].ID> 0&&p[i].id> mid) ans[p[i].ID]+=sum (p[i].y)*p[i].val;
    }
    for (int i=l; i<=r; i++)
        if (p[i].ID==0&&p[i].id<=mid) add (p[i].y,-p[i].val);

    int w1=l,w2=mid+1;
    for (int i=l; i<=r; i++)
        if (p[i].id<=mid) tmp[w1++]=p[i];
        else              tmp[w2++]=p[i];
    for (int i=l; i<=r; i++) p[i]=tmp[i];

    solve (l,mid),solve (mid+1,r);
}
int main()
{
    int lgj; sc(lgj),sc(lgj); int num=0,q=0;
    while (521)
    {
        int op; sc(op); if (op==3) break;
        if (op==1) q++,p[q].id=q,p[q].ID=0,sc(p[q].x),sc(p[q].y),sc(p[q].val);
        else 
        {
            int x1,y1,x2,y2; sc(x1),sc(y1),sc(x2),sc(y2); num++;
            q++,p[q].id=q,p[q].ID=num,p[q].x=x1-1,p[q].y=y1-1,p[q].val=1;
            q++,p[q].id=q,p[q].ID=num,p[q].x=x2  ,p[q].y=y2  ,p[q].val=1;
            q++,p[q].id=q,p[q].ID=num,p[q].x=x1-1,p[q].y=y2  ,p[q].val=-1;
            q++,p[q].id=q,p[q].ID=num,p[q].x=x2  ,p[q].y=y1-1,p[q].val=-1;
        }
    }
    sort (p+1,p+q+1,ly);
    solve (1,q);
    for (int i=1; i<=num; i++) pr(ans[i]);
    return 0;
}

栗

HDU5412：首先将修改改为删除与插入。
$l,r$表示的是要操作的区间，即编号在$l,r$之间的操作。
$L,R$表示的是答案的范围。
枚举操作（包括询问），若为修改，判断修改的数在左区间$\left[ L,mid \right]$或右区间$\left[ mid+1,R \right]$。
若为左区间，则在树状数组中将修改的位置+1，并放入S1，否则放入S2。

if (s[i].y<=mid) add (s[i].x,s[i].op),S1[++w1]=s[i];
else                                  S2[++w2]=s[i];

这样保证了询问时得到的结果（询问区间内数的个数）中的数全部在区间$\left[ L,mid \right]$中。

int tmp=sum (s[i].y)-sum (s[i].x-1);
if (tmp>=s[i].k) S1[++w1]=s[i];
else s[i].k-=tmp,S2[++w2]=s[i];

由此可以判断答案在$\left[ L,mid \right]$中或$\left[ mid+1,R \right]$中，并放入相应数组。
由于每层都要清空树状数组，但memset又很慢，故应一个一个还原修改。
最后将S1、S2合并到s。

CDQ分治

概念

对于离线的带有修改与询问的问题，若修改较难处理，且修改对询问的贡献能计算并合并，可以考虑使用CDQ分治。

Luogu3810

#include <bits/stdc++.h>
#define pr(p) printf("%d\n",p)
const int oo=2139063143;
const int N=1010000;
const int mod=1000000007;
using namespace std;
typedef long long LL;
inline void sc (int &x)
{
    x=0; static int p; p=1; static char c; c=getchar();
    while (!isdigit(c)) { if (c=='-') p=-1; c=getchar(); }
    while ( isdigit(c)) { x=(x<<1)+(x<<3)+(c-48); c=getchar(); }
    x*=p;
}
struct LY { int x,y,z,id; }a[N];
int n,k;
bool ly1 (LY A,LY B) { return (A.x==B.x)?((A.y==B.y)?(A.z< B.z):(A.y< B.y)):(A.x< B.x); }
bool ly2 (LY A,LY B) { return (A.y==B.y)?((A.z==B.z)?(A.x< B.x):(A.z< B.z)):(A.y< B.y); }
bool ly3 (LY A,LY B) { return A.id< B.id; }
int same[N],ans[N];
int bit[N];
void add (int w,int d) { for (; w<=k; w+=w&-w) bit[w]+=d; }
int sum (int w) { int an=0; for (; w; w-=w&-w) an+=bit[w]; return an; }
void cdq (int l,int r)
{
    if (l==r) return ;
    int mid=(l+r)>>1;
    cdq (l,mid),cdq (mid+1,r);
    sort (a+l,a+r+1,ly2);//也可以在cdq的最后归并排序

    for (int i=l; i<=r; i++)
        if (a[i].x<=mid) add (a[i].z,1);
        else ans[a[i].id]+=sum (a[i].z);//小于等于都可以，所以不用-1

    for (int i=l; i<=r; i++)
        if (a[i].x<=mid) add (a[i].z,-1);
}
int d[N];
int main()
{
    //freopen (".in","r",stdin);
    //freopen (".out","w",stdout);
    sc(n),sc(k);
    for (int i=1; i<=n; i++)
        sc(a[i].x),sc(a[i].y),sc(a[i].z),a[i].id=i;
    sort (a+1,a+n+1,ly1);
    for (int i=1; i<=n; )
    {
        int j=i+1;
        while (j<=n&&a[i].x==a[j].x&&a[i].y==a[j].y&&a[i].z==a[j].z) ++j;
        while (i< j) same[a[i++].id]=a[j-1].id;
        //相同属性的用最后一个（因为最大），保证答案是·所有·小于等于该元素的，避免漏算
    }
    for (int i=1; i<=n; i++)
        a[i].x=i;
    cdq (1,n);
    for (int i=1; i<=n; i++)
        ++d[ans[same[a[i].id]]];
    for (int i=0; i< n; i++)
        pr(d[i]);
    return 0;
}

Luogu3157

#include <bits/stdc++.h>
#define pr(p) printf("%lld\n",p)
const int oo=2139063143;
const int N=200010;
const int mod=1000000007;
using namespace std;
typedef long long LL;
inline void sc (int &x)
{
    x=0; static int p; p=1; static char c; c=getchar();
    while (!isdigit(c)) { if (c=='-') p=-1; c=getchar(); }
    while ( isdigit(c)) { x=(x<<1)+(x<<3)+(c-48); c=getchar(); }
    x*=p;
}
int n,m;
int bit[N],sbit=0;
void add (int w,int d) { sbit+=d; for (; w<=n; w+=w&-w) bit[w]+=d; }
int sum (int w) { int ans=0; for (; w; w-=w&-w) ans+=bit[w]; return ans; }
struct LY { int x,y,z; }p[N];
bool ly1 (LY A,LY B) { return A.x< B.x; }
bool ly2 (LY A,LY B) { return A.y> B.y; }
LL ans[N];
void cdq (int l,int r)
{
    if (l==r) return ;
    int mid=(l+r)>>1;
    cdq (l,mid),cdq (mid+1,r);
    sort (p+l,p+r+1,ly2);

    for (int i=l; i<=r; i++)
        if (p[i].x<=mid) add (p[i].z,1);
        else ans[p[i].x]+=1LL*sum (p[i].z-1);

    for (int i=l; i<=r; i++)
        if (p[i].x<=mid) add (p[i].z,-1);

    for (int i=r; i>=l; i--)
        if (p[i].x<=mid) add (p[i].z,1);
        else ans[p[i].x]+=1LL*(sbit-sum (p[i].z));

    for (int i=l; i<=r; i++)
        if (p[i].x<=mid) add (p[i].z,-1);
}
int w[N],a[N],del[N];
bool vis[N];
int main()
{
    //freopen (".in","r",stdin);
    //freopen (".out","w",stdout);
    sc(n),sc(m);
    for (int i=1; i<=n; i++)
        sc(a[i]),w[a[i]]=i;
    for (int i=1; i<=m; i++)
        sc(del[i]),vis[del[i]]=1;
    del[0]=m;
    for (int i=1; i<=n; i++)
        if (!vis[i]) del[++del[0]]=i;
    for (int i=n; i>=1; i--)
        p[i].x=n-i+1,p[i].y=w[del[i]],p[i].z=del[i];

    sort (p+1,p+n+1,ly1);
    cdq (1,n);

    for (int i=1; i<=n; i++)
        ans[i]+=ans[i-1];
    for (int i=n; i>=n-m+1; i--)
        pr(ans[i]);
    return 0;
}

LG3157题解

考虑将问题转化为三维偏序。
首先将删除换成插入。没有全部删掉也没关系，帮它删掉（
然后每个数都得到了三个属性：时间、位置、值。
栗：
数据为：
6 6
5 1 6 2 4 3
5 3 6 4 1 2

pos      1 2 3 4 5 6  
time 1         2  
   1   2  
   1   2 4  
   1 6 2 4  
   1 6 2 4 3  
 5 1 6 2 4 3  

（假装成表格

于是，每加入一个数有两种情况使答案增加了：
1.时间比当前小、位置比当前大、值比当前小
1.时间比当前小、位置比当前小、值比当前大
三维偏序，可在同一个cdq里面解决。
最后记前缀和。

Luogu4027

#include <bits/stdc++.h>
#define pr(p) printf("%d\n",p)
const int oo=2139063143;
const int N=101000;
const int mod=1000000007;
using namespace std;
typedef long long LL;
typedef double db;
const db eps=1e-9;
inline void sc (int &x)
{
    x=0; static int p; p=1; static char c; c=getchar();
    while (!isdigit(c)) { if (c=='-') p=-1; c=getchar(); }
    while ( isdigit(c)) { x=(x<<1)+(x<<3)+(c-48); c=getchar(); }
    x*=p;
}
int n;
struct LY { db a,b,r,k,x,y; int id; }s[N],tmp[N];
bool ly (LY A,LY B) { return A.k> B.k; }
db getk (int A,int B)//尽量不要使用这种写法
{
    if (abs (s[A].x-s[B].x)< eps) return oo;
    return (s[A].y-s[B].y)/(s[A].x-s[B].x);
}
db f[N];
int q[N];
void cdq (int l,int r)
{
    if (l==r)
    {
        f[l]=max (f[l],f[l-1]);
        s[l].y=f[l]/(s[l].a*s[l].r+s[l].b);
        s[l].x=s[l].y*s[l].r;
        return ;
    }
    int mid=(l+r)>>1,wl=l-1,wr=mid;
    for (int i=l; i<=r; i++)
        (s[i].id<=mid)?tmp[++wl]=s[i]:tmp[++wr]=s[i];
    for (int i=l; i<=r; i++)
        s[i]=tmp[i];
    cdq (l,mid);
    int head=1,tail=0;
    for (int i=l; i<=mid; i++)
    {
        while (tail> 1&&getk (q[tail],q[tail-1])< getk (q[tail],i)+eps) --tail;
        q[++tail]=i;
    }
    for (int i=mid+1; i<=r; i++)
    {
        while (head< tail&&getk (q[head],q[head+1])+eps> s[i].k) ++head;
        int j=q[head];
        f[s[i].id]=max (f[s[i].id],s[j].x*s[i].a+s[j].y*s[i].b);
    }
    cdq (mid+1,r);

    wl=l,wr=mid+1;
    for (int i=l; i<=r; i++)
        tmp[i]=((s[wl].x< s[wr].x||wr> r||abs (s[wl].x-s[wr].x)< eps)&&wl<=mid)?s[wl++]:s[wr++];
    for (int i=l; i<=r; i++)
        s[i]=tmp[i];
}
int main()
{
    //freopen (".in","r",stdin);
    //freopen (".out","w",stdout);
    sc(n),scanf ("%lf",&f[0]);
    for (int i=1; i<=n; i++)
    {
        scanf ("%lf%lf%lf",&s[i].a,&s[i].b,&s[i].r);
        s[i].k=-s[i].a/s[i].b; s[i].id=i;
    }
    sort (s+1,s+n+1,ly);
    cdq (1,n);
    printf ("%.3lf\n",f[n]);

    return 0;
}

LG4027题解

https://www.luogu.org/problemnew/solution/P4027 %%%ysy20021208
此题需要斜率优化。
一般的斜率优化的横坐标是递增的，此题不递增（具体横纵坐标是啥看上面题解）。
于是可以cdq分治。
先处理出[l,mid]的答案，然后按照横坐标递增的顺序将左半边（已处理）的信息插入凸包。
右半边要保证按照斜率递增，就可以用凸包上的信息来更新右半边。
再处理出[mid+1,r]的答案。
通过归并排序的思想，最后可以按照横坐标归并成有序的再返回。

发现一个东东：cdq之前是按照初始排序的顺序，cdq之后是按照归并排序的顺序。
具体来说，进行cdq (1,n)之前一般有一次排序，记为顺序A；归并排序的顺序记为B。

cdq (l,r)
{
    cdq (l,mid);
    //[l,mid]:B,[mid+1,r]:A
    xxxxxxxx;
    cdq (mid+1,r);
    mergesort (l,r);
}

原创文章采用CC BY-NC-SA 4.0协议进行许可，转载请注明：“转载自：整体二分&CDQ分治”