标签：cstring style const one 静态 using 前缀和 color oid
CDQ分治不但能解决三维偏序问题，还能将某些问题的动态版本变成静态。
比如这题是单点修改，区间查询，这样我们就可以将输入的顺序当作时间轴，之后进行CDQ分治
按x轴排序后，对y进行树状数组加减，这道题就变成了x比他小，并且y也比他小的个数查询
这题还用到了简单的容斥原理，也就是二维前缀和的思想来求取矩形真正的内容
#include
#include
#include
#include
#include
#includeusing namespace std;
typedef long long ll;
const int N=2e6+10;
const int mod=1e9+7;
struct node{
int a,x,y,v,op,id;
}q[N];
ll tr[N],ans[N];
int lowbit(int x){
return x&-x;
}
void add(int x,int c){
int i;
for(i=x;ilowbit(i)){
tr[i]+=c;
}
}
ll sum(int x){
ll res=0;
int i;
for(i=x;i;i-=lowbit(i)){
res+=tr[i];
}
return res;
}
bool cmpb(node a,node b){
if(a.x==b.x)
return a.opb.op;
return a.xb.x;
}
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+1+r,cmpb);
int i;
for(i=l;i){
int id=q[i].id;
if(q[i].op==1&&q[i].amid)
add(q[i].y,q[i].v);
if(q[i].op==2&&q[i].a>=mid+1)
ans[id]+=sum(q[i].y);
if(q[i].op==3&&q[i].a>=mid+1)
ans[id]-=sum(q[i].y);
}
for(i=l;i){
if(q[i].op==1&&q[i].amid)
add(q[i].y,-q[i].v);
}
}
int main(){
int n,w;
cin>>n>>w;
int cnt=0;
int idx=0;
while(cin>>n&&n!=3){
if(n==1){
int x,y,c;
scanf("%d%d%d",&x,&y,&c);
cnt++;
q[cnt]=node{cnt,x,y,c,1};
}
if(n==2){
int x1,y1,x2,y2;
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
cnt++;
idx++;
q[cnt]=node{cnt,x2,y2,0,2,idx};
++cnt;
q[cnt]=node{cnt,x1-1,y1-1,0,2,idx};
++cnt;
q[cnt]=node{cnt,x2,y1-1,0,3,idx};
++cnt;
q[cnt]=node{cnt,x1-1,y2,0,3,idx};
}
}
cdq(1,cnt);
for(int i=1;i){
coutendl;
}
}
View Code
AcWing267 莫基亚（CDQ分治）
标签：cstring style const one 静态 using 前缀和 color oid
原文地址：https://www.cnblogs.com/ctyakwf/p/12751161.html