CDQ 分治

用户头像 发布于 1 天前 16 次阅读 OI

CDQ 分治

P3810 【模板】三维偏序 / 陌上花开

模板，没啥好说的

代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+5;
const int K=2e5+5;
int n,k,m,t;
int res[N];
struct Element {
    int a,b,c,cnt,res;
    bool operator!=(Element other) const {
        return a!=other.a||b!=other.b||c!=other.c;
    }
}e[N],ue[N];
struct BIT {
    int node[K];
    int lowbit(int x) {return x&-x;}
    void add(int pos,int val) {
        while(pos<=k) node[pos]+=val,pos+=lowbit(pos);
    }
    int ask(int pos) {
        int res=0;
        while(pos) res+=node[pos],pos-=lowbit(pos);
        return res;
    }
}bit;
bool cmpA(Element x,Element y) {
    if(x.a!=y.a) return x.a<y.a;
    if(x.b!=y.b) return x.b<y.b;
    return x.c<y.c;
}
bool cmpB(Element x,Element y) {
    if(x.b!=y.b) return x.b<y.b;
    return x.c<y.c;
}
void cdq(int l,int r) {
    if(l==r) return;
    int mid=(l+r)>>1;
    cdq(l,mid); cdq(mid+1,r);
    sort(ue+l,ue+mid+1,cmpB);
    sort(ue+mid+1,ue+r+1,cmpB);
    int i=l,j=mid+1;
    while(j<=r) {
        while(i<=mid&&ue[i].b<=ue[j].b)
            bit.add(ue[i].c,ue[i].cnt),i++;
        ue[j].res+=bit.ask(ue[j].c),j++;
    }
    for(int k=l;k<i;k++) bit.add(ue[k].c,-ue[k].cnt);
}
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>n>>k;
    for(int i=1;i<=n;i++) cin>>e[i].a>>e[i].b>>e[i].c;
    sort(e+1,e+n+1,cmpA);
    for(int i=1;i<=n;i++) {
        t++;
        if(e[i]!=e[i+1]) {
            ue[++m]={e[i].a,e[i].b,e[i].c,t,0};
            t=0;
        }
    }
    cdq(1,m);
    for(int i=1;i<=m;i++) res[ue[i].res+ue[i].cnt-1]+=ue[i].cnt;
    for(int i=0;i<n;i++) cout<<res[i]<<'\n';
    return 0;
}

P2163 [SHOI2007] 园丁的烦恼

甚至不需要使用 CDQ 分治，二位数点问题，算是下一题的弱化版本，直接一个树状数组就够了。

代码：

#include<bits/stdc++.h>
using namespace std;

const int N=5e5+5, M=3e6+5;
int n,m,cnt;
struct nd{
    int x,y,k,id;
}q[N*5];
int ans[N];

vector<int> v;

struct BIT{
    int tr[M];
    int lowbit(int x) {return x&-x;}
    void add(int p,int v){
        while(p<M) tr[p]+=v,p+=lowbit(p);
    }
    int ask(int p){
        int res=0;
        while(p) res+=tr[p],p-=lowbit(p);
        return res;
    }
}bit;

bool cmp(nd a,nd b){
    if(a.x!=b.x) return a.x<b.x;
    return a.k==0;
}

int id(int y){
    return lower_bound(v.begin(),v.end(),y)-v.begin()+1;
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        int x,y;
        cin>>x>>y;
        q[++cnt]={x,y,0,0};
        v.push_back(y);
    }
    for(int i=1;i<=m;i++){
        int a,b,c,d;
        cin>>a>>b>>c>>d;
        q[++cnt]={c,d,1,i};
        q[++cnt]={a-1,d,-1,i};
        q[++cnt]={c,b-1,-1,i};
        q[++cnt]={a-1,b-1,1,i};
        v.push_back(b-1);
        v.push_back(d);
    }
    sort(v.begin(),v.end());
    v.erase(unique(v.begin(),v.end()),v.end());
    for(int i=1;i<=cnt;i++) q[i].y=id(q[i].y);
    sort(q+1,q+1+cnt,cmp);
    for(int i=1;i<=cnt;i++){
        if(q[i].k==0) bit.add(q[i].y,1);
		else ans[q[i].id]+=q[i].k*bit.ask(q[i].y);
    }
    for(int i=1;i<=m;i++) cout<<ans[i]<<"\n";
    return 0;
}

P4390 [BalkanOI 2007] Mokia 摩基亚

上一题的升级版，在树状数组+二位前缀和的基础上增加了一个时间维度，想到使用 CDQ 分治来处理，在上一题的基础上稍加修改即可，思路上没有区别。

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
const int M=2e6+5;
int w,op,tot,qcnt;
int ans[N];
struct Node{
    int time,type,x,y,val,id;
    bool operator<(const Node &t) const{
        if(time!=t.time) return time<t.time;
        if(x!=t.x) return x<t.x;
        if(y!=t.y) return y<t.y;
        return type<t.type;
    }
}q[N],tmp[N];
struct BIT{
    int node[M];
    int lowbit(int x) {return x&-x;}
    void add(int pos,int val){
        while(pos<=w) node[pos]+=val,pos+=lowbit(pos);
    }
    int ask(int pos) {
        int res=0;
        while(pos) res+=node[pos],pos-=lowbit(pos);
        return res;
    }
    void clear(int pos){
        while(pos<=w){
            if(!node[pos]) break;
            node[pos]=0;
            pos+=lowbit(pos);
        }
    }
}bit;
bool cmpX(const Node &a,const Node &b){
    if(a.x!=b.x) return a.x<b.x;
    if(a.y!=b.y) return a.y<b.y;
    return a.type<b.type;
}
void cdq(int l,int r){
    if(l==r) return;
    int mid=(l+r)>>1;
    cdq(l,mid); cdq(mid+1,r);
    sort(q+l,q+mid+1,cmpX);
    sort(q+mid+1,q+r+1,cmpX);
    int i=l,j=mid+1;
    while(j<=r){
        while(i<=mid&&q[i].x<=q[j].x){
            if(q[i].type==1) bit.add(q[i].y,q[i].val);
            i++;
        }
        if(q[j].type==2) ans[q[j].id]+=q[j].val*bit.ask(q[j].y);
        j++;
    }
    for(int k=l;k<i;k++) 
        if(q[k].type==1) bit.clear(q[k].y);
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>op>>w;
    w++;
    
    int time=0;
    while(cin>>op&&op!=3){
        time++;
        if(op==1){
            int x,y,val;
            cin>>x>>y>>val;
            x++; y++;
            q[++tot]={time,1,x,y,val,0};
        }
        else{
            int x1,y1,x2,y2;
            cin>>x1>>y1>>x2>>y2;
            x1++; y1++; x2++; y2++;
            qcnt++;
            q[++tot]={time,2,x2,y2,1,qcnt};
            q[++tot]={time,2,x1-1,y2,-1,qcnt};
            q[++tot]={time,2,x2,y1-1,-1,qcnt};
            q[++tot]={time,2,x1-1,y1-1,1,qcnt};
        }
    }
    sort(q+1,q+tot+1);
    cdq(1,tot);
    for(int i=1;i<=qcnt;i++) cout<<ans[i]<<'\n';
    return 0;
}