CDQ分治与整体二分小结

#include<bits/stdc++.h>
using namespace std;
const int N=3e6+10;
typedef long long LL;
int n,m,qid;
LL ans[N];
struct query{
    int type,x,y,aid,w;  //操作类型，x坐标，y坐标，答案编号，对答案贡献 
    bool operator < (const query &rhs) const {
        return x==rhs.x ? type<rhs.type : x<rhs.x;  //x相等时要修改操作在前 
    }
}Q[N],tmp[N];

const int L=1e7+10; LL sum[L];
void update(int x,int v) {
    if (x) for (;x<L;x+=x&-x) sum[x]+=v;
}
LL query2(int x) {
    LL ret=0;
    if (x) for (;x;x-=x&-x) ret+=sum[x];
    return ret;
}
void Clear(int x) {
    if (x) for (;x<L && sum[x];x+=x&-x) sum[x]=0;
} 

void CDQ(int l,int r) {
    if (l>=r) return;
    int mid=l+r>>1; 
    CDQ(l,mid); CDQ(mid+1,r);  //先两边分治 
    int p=l,q=mid+1,o=l-1;  //归并排序合并两边并计算左边操作对右边询问影响 
    while (p<=mid && q<=r) {
        if (Q[p]<Q[q]) {
            if (Q[p].type==0) update(Q[p].y,1);  //只处理左边的修改操作 
            tmp[++o]=Q[p++];  //归并排序 
        } else {
            if (Q[q].type==1) ans[Q[q].aid]+=query2(Q[q].y)*Q[q].w;  //只处理右边的查询操作 
            tmp[++o]=Q[q++];  //归并排序 
        }
    }
    while (p<=mid) tmp[++o]=Q[p++];
    while (q<=r) {
        if (Q[q].type==1) ans[Q[q].aid]+=query2(Q[q].y)*Q[q].w;
        tmp[++o]=Q[q++];
    }
    for(int i=l;i<=mid;i++) if(Q[i].type==0) Clear(Q[i].y);  //清空树状数组 
    for (int i=l;i<=r;i++) Q[i]=tmp[i];  //记录归并排序后结果 
} 

int main()
{
    cin>>n>>m;
    for (int i=1;i<=n;i++) {
        int x,y; scanf("%d%d",&x,&y); x++; y++;
        Q[++qid]=(query){0,x,y,0,0};
    }    
    for (int i=1;i<=m;i++) {
        int x1,y1,x2,y2; scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
        x1++; y1++; x2++; y2++;
        Q[++qid]=(query){1,x2,y2,i,1};
        Q[++qid]=(query){1,x1-1,y1-1,i,1};
        Q[++qid]=(query){1,x1-1,y2,i,-1};
        Q[++qid]=(query){1,x2,y1-1,i,-1};
    }
    
    CDQ(1,qid);
    for (int i=1;i<=m;i++) printf("%lld
",ans[i]);
    return 0;
}