M_sea

「总结」CDQ分治&整体二分
咕了太久了啊...CDQ分治引入:二维偏序概念二维偏序问题是指:给出$n$个元素,每个元素有$a$、$b$两个属性...
扫描右侧二维码阅读全文
08
2019/02

「总结」CDQ分治&整体二分

咕了太久了啊...

CDQ分治

引入:二维偏序

概念

二维偏序问题是指:给出$n$个元素,每个元素有$a$、$b$两个属性。

设$f(i)$表示满足$a_j<a_i$且$b_j<b_i$的$j$的数量。

对于$d\in[0,n]$,求满足$f(i)=d$的$i$的数量。

求解

首先按$a$排个序,这样子$j>i$一定不会对$i$产生影响。

于是可以上树状数组来维护$b$。

经典问题:三维偏序

概念

三维偏序问题是指:给出$n$个元素,每个元素有$a$、$b$、$c$三个属性。

设$f(i)$表示满足$a_j<a_i$且$b_j<b_i$且$c_j<c_i$的$j$的数量。

对于$d\in[0,n]$,求满足$f(i)=d$的$i$的数量。

求解

我们先按$a$排个序,然后$b$用归并排序处理,$c$用树状数组处理。

具体实现还是见代码?

代码

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int MAXN=100000+10;
const int MAXK=200000+10;

struct node {
    int x,y,z,w,ans;
    bool operator <(const node& rhs) const {
        if (x!=rhs.x) return x<rhs.x;
        if (y!=rhs.y) return y<rhs.y;
        return z<rhs.z;
    }
    bool operator ==(const node& rhs) const {
        return x==rhs.x&&y==rhs.y&&z==rhs.z;
    }
} a[MAXN];

int n,k;

inline int cmp(node A,node B) {
    if (A.y!=B.y) return A.y<B.y;
    return A.z<B.z;
}

int c[MAXK];
inline int lowbit(int x) { return x&-x; }
inline void add(int x,int y) { while (x<=k) c[x]+=y,x+=lowbit(x); }
inline int sum(int x) { int rt=0; while (x) rt+=c[x],x-=lowbit(x); return rt; }

inline 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+mid+1,cmp); sort(a+mid+1,a+R+1,cmp);
    int i=L;
    for (re int j=mid+1;j<=R;++j) {
        while (i<=mid&&a[i].y<=a[j].y) {
            add(a[i].z,a[i].w);
            ++i;
        }
        a[j].ans+=sum(a[j].z);
    }
    for (re int j=L;j<i;++j) add(a[j].z,-a[j].w); //还原树状数组
}

int ans[MAXN];

int main() {
    n=read(),k=read();
    for (re int i=1;i<=n;++i) a[i].x=read(),a[i].y=read(),a[i].z=read();
    sort(a+1,a+n+1); int tmp=0;
    for (re int i=1;i<=n;++i) {
        if (a[i]==a[i-1]) ++a[tmp].w;
        else a[++tmp]=a[i],a[tmp].w=1;
    }
    int N=n,n=tmp;
    CDQ(1,n);
    for (re int i=1;i<=n;++i) ans[a[i].ans+a[i].w]+=a[i].w;
    for (re int i=1;i<=N;++i) printf("%d\n",ans[i]);
    return 0;
}

进阶:[BOI2007]Mokia

分析

时间、$x$、$y$,三个维度,对应经典的三维偏序问题。

把询问拆成四个即可。

代码

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
typedef int mainint;
#define int long long
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int MAXN=200000+10;
const int MAXW=2000000+10;

struct query {
    int type,id,x,y,k,ans; //0修改,1查询
    int operator <(const query& rhs) const {
        return id<rhs.id;
    }
} q[MAXN],t[MAXN];

int W;
int c[MAXW];
#define lowbit(x) (x&-x)
inline void add(int x,int y) { while (x<=W) c[x]+=y,x+=lowbit(x); }
inline int sum(int x) { int rt=0; while (x) rt+=c[x],x^=lowbit(x); return rt; }
inline void clear(int x) { while (x<=W) c[x]=0,x+=lowbit(x); }

int ans[MAXN];

inline void CDQ(int L,int R) {
    if (L==R) return;
    int mid=(L+R)>>1;
    CDQ(L,mid),CDQ(mid+1,R);
    int i=L,j=mid+1,k=L;
    while (i<=mid&&j<=R) {
        if (q[i].x<=q[j].x) {
            if (!q[i].type) add(q[i].y,q[i].k);
            t[k++]=q[i++];
        } else {
            if (q[j].type) q[j].ans+=sum(q[j].y);
            t[k++]=q[j++];
        }
    }
    while (i<=mid) {
        if (!q[i].type) add(q[i].y,q[i].k);
        t[k++]=q[i++];
    }
    while (j<=R) {
        if (q[j].type) q[j].ans+=sum(q[j].y);
        t[k++]=q[j++];
    }
    for (re int p=L;p<=mid;++p)
        if (!q[p].type) clear(q[p].y);
    for (re int p=L;p<=R;++p) q[p]=t[p];
}

mainint main() {
    int op=read(),tot=0; W=read();
    while (1) {
        op=read(); if (op==3) break;
        if (op==1) {
            int x=read(),y=read(),k=read();
            q[++tot]=(query){0,tot,x,y,k,0};
        }
        else if (op==2) {
            int lx=read(),ly=read(),rx=read(),ry=read();
            q[++tot]=(query){1,tot,rx,ry,0,0};
            q[++tot]=(query){1,tot,rx,ly-1,0,0};
            q[++tot]=(query){1,tot,lx-1,ry,0,0};
            q[++tot]=(query){1,tot,lx-1,ly-1,0,0};
        }
    }
    CDQ(1,tot); sort(q+1,q+tot+1);
    for (re int i=1;i<=tot;++i) {
        if (q[i].type) {
            printf("%lld\n",q[i].ans-q[i+1].ans-q[i+2].ans+q[i+3].ans);
            i+=3;
        }
    }
    return 0;
}

神仙操作:[HNOI2010]城市建设

题解

整体二分

考虑清楚只有一个询问怎么二分,然后拓展成多个操作即可。

主过程solve(lval,rval,l,r),表示答案在$[lval,rval]$中,与操作$[l,r]$有关。

经典问题:区间第$\mathrm{K}$大

求解

你甚至可以用整体二分氵掉主席树板子

考虑只有一个询问怎么二分。

二分答案$mid$,求有几个数比$mid$小,假如有$c$个。

如果$c>k$,那么答案比$mid$小;否则,将$k$减去$c$,然后在比$mid$大的数中二分。

这样子就可以拓展到多个询问。

当$lval=rval$时,直接记一下答案就好了。

初始值的处理可以看成一个单点加的操作。

细节见代码。

代码

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

//这里省略了读入输出优化

const int MAXN=200010;

int n,m;
int a[MAXN];
struct query { int x,y,k,id; };
query q[MAXN<<1],lq[MAXN<<1],rq[MAXN<<1];
int ans[MAXN<<1];

int c[MAXN];
#define lowbit(x) (x&-x)
inline void add(int x,int y) { while (x<=n) c[x]+=y,x+=lowbit(x); }
inline int sum(int x) { int rt=0; while (x) rt+=c[x],x^=lowbit(x); return rt; }

inline void solve(int lval,int rval,int l,int r) {
    if (l>r) return; //序列为空
    if (lval==rval) { //边界
        for (re int i=l;i<=r;++i)
            if (q[i].id) ans[q[i].id]=lval;
        return;
    }
    int mid=(lval+rval)>>1,lt=0,rt=0;
    for (re int i=l;i<=r;++i) {
        if (!q[i].id) { //加
            if (q[i].y<=mid) add(q[i].x,1),lq[++lt]=q[i];
            else rq[++rt]=q[i];
        } else { //查询
            int cnt=sum(q[i].y)-sum(q[i].x-1);
            if (cnt>=q[i].k) lq[++lt]=q[i];
            else q[i].k-=cnt,rq[++rt]=q[i];
        }
    }
    for (re int i=r;i>=l;--i) //还原树状数组
        if (!q[i].id&&q[i].y<=mid) add(q[i].x,-1);
    for (re int i=1;i<=lt;++i) q[l+i-1]=lq[i];
    for (re int i=1;i<=rt;++i) q[l+lt+i-1]=rq[i];
    solve(lval,mid,l,l+lt-1); solve(mid+1,rval,l+lt,r);
}

int main() {
    read(n),read(m); int t=0;
    for (re int i=1;i<=n;++i)
        read(a[i]),q[++t]=(query){i,a[i],0,0};
    for (re int i=1,x,y,k;i<=m;++i) {
        read(x),read(y),read(k);
        q[++t]=(query){x,y,k,i};
    }
    solve(-1e9,1e9,1,t);
    for (re int i=1;i<=m;++i) print(ans[i]),putc('\n');
    return 0;
}

进阶:Dynamic Rankings

分析

带了修改的区间第$\text{K}$大。

把修改操作拆成减和加,就和上面一样了。

代码

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int MAXN=300000+10;

struct query { int x,y,k,id; } q[MAXN],lq[MAXN],rq[MAXN];
int n,m,t;
int a[MAXN],ans[MAXN];

int c[MAXN];
#define lowbit(x) (x&-x)
inline void add(int x,int y) { while (x<=n) c[x]+=y,x+=lowbit(x); }
inline int sum(int x) { int y=0; while (x) y+=c[x],x^=lowbit(x); return y; }

inline void solve(int lval,int rval,int st,int ed) {
    if (st>ed) return;
    if (lval==rval) {
        for (re int i=st;i<=ed;++i)
            if (q[i].id) ans[q[i].id]=lval;
        return;
    }
    int mid=(lval+rval)>>1,lt=0,rt=0;
    for (re int i=st;i<=ed;++i) {
        if (!q[i].id) { //修改
            if (q[i].y<=mid) add(q[i].x,q[i].k),lq[++lt]=q[i];
            else rq[++rt]=q[i];
        } else { //查询
            int cnt=sum(q[i].y)-sum(q[i].x-1);
            if (cnt>=q[i].k) lq[++lt]=q[i];
            else q[i].k-=cnt,rq[++rt]=q[i];
        }
    }
    for (re int i=ed;i>=st;--i)
        if (!q[i].id&&q[i].y<=mid) add(q[i].x,-q[i].k);
    for (re int i=1;i<=lt;++i) q[st+i-1]=lq[i];
    for (re int i=1;i<=rt;++i) q[st+lt+i-1]=rq[i];
    solve(lval,mid,st,st+lt-1); solve(mid+1,rval,st+lt,ed);
}

int main() {
    n=read(),m=read(); int Q=0;
    for (re int i=1;i<=n;++i)
        a[i]=read(),q[++t]=(query){i,a[i],1,0};
    for (re int i=1;i<=m;++i) {
        char op[2]; scanf("%s",op);
        if (op[0]=='Q') {
            int l=read(),r=read(),k=read();
            q[++t]=(query){l,r,k,++Q};
        } else {
            int x=read(),y=read();
            q[++t]=(query){x,a[x],-1,0};
            q[++t]=(query){x,y,1,0};
            a[x]=y;
        }
    }
    solve(0,1e9,1,t);
    for (re int i=1;i<=Q;++i) printf("%d\n",ans[i]);
    return 0;
}

更进一步:[Poi2011]Meteors

分析

二分哪一次流星雨后收集够了。

用一个区间修改、单点查询的树状数组来维护。

代码

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int MAXN=600010;

int n,m,k;
struct query { int type,l,r,w,id; }; //type:0是任务,1是l<=r的流星雨,2是l>r的流星雨
query q[MAXN],lq[MAXN],rq[MAXN];
vector<int> s[MAXN];
int p[MAXN];
int ans[MAXN];

int c[MAXN];
#define lowbit(x) (x&-x)
inline void add(int x,int y) { while (x<=m) c[x]+=y,x+=lowbit(x); }
inline int sum(int x) { int y=0; while (x) y+=c[x],x^=lowbit(x); return y; }

inline void solve(int lval,int rval,int st,int ed) {
    if (st>ed) return;
    if (lval==rval) {
        for (re int i=st;i<=ed;++i)
            if (!q[i].type) ans[q[i].id]=lval;
        return;
    }
    int mid=(lval+rval)>>1,lt=0,rt=0;
    for (re int i=st;i<=ed;++i) {
        if (!q[i].type) { //查询
            int ss=0;
            for (re int j=0;j<s[q[i].id].size();++j) {
                ss+=sum(s[q[i].id][j]);
                if (ss>=q[i].w) break; //小小的优化一下
            }
            if (ss>=q[i].w) lq[++lt]=q[i];
            else q[i].w-=ss,rq[++rt]=q[i];
        } else { //修改
            if (q[i].id<=mid) {
                if (q[i].type==1)
                    add(q[i].l,q[i].w),add(q[i].r+1,-q[i].w);
                else
                    add(1,q[i].w),add(q[i].r+1,-q[i].w),add(q[i].l,q[i].w);
                lq[++lt]=q[i];
            }
            else rq[++rt]=q[i];
        }
    }
    for (re int i=st;i<=ed;++i)
        if (q[i].id<=mid&&q[i].type) {
            if (q[i].type==1)
                add(q[i].l,-q[i].w),add(q[i].r+1,q[i].w);
            else
                add(1,-q[i].w),add(q[i].r+1,q[i].w),add(q[i].l,-q[i].w);
        }
    for (re int i=1;i<=lt;++i) q[st+i-1]=lq[i];
    for (re int i=1;i<=rt;++i) q[st+lt+i-1]=rq[i];
    solve(lval,mid,st,st+lt-1); solve(mid+1,rval,st+lt,ed);
}

int main() {
    n=read(),m=read();
    for (re int i=1;i<=m;++i) s[read()].push_back(i);
    for (re int i=1;i<=n;++i) p[i]=read();
    k=read();
    for (re int i=1;i<=k;++i) {
        q[i].l=read(),q[i].r=read(),q[i].w=read(),q[i].id=i;
        if (q[i].l<=q[i].r) q[i].type=1;
        else q[i].type=2;
    }
    for (re int i=1;i<=n;++i)
        q[k+i].type=0,q[k+i].w=p[i],q[k+i].id=i;
    solve(1,k+1,1,k+n);
    for (re int i=1;i<=n;++i) {
        if (ans[i]!=k+1) printf("%d\n",ans[i]);
        else puts("NIE");
    }
    return 0;
}

$$\Huge\texttt{--The End--}$$

最后修改:2019 年 02 月 10 日 06 : 18 PM

2 条评论

  1. xgzc

    Orz

    1. M_sea
      @xgzc

      您不是早会了吗qwq

发表评论