BZOJ1176 [Balkan2007]Mokia cdq分治

BZOJ1176 [Balkan2007]Mokia cdq分治

复习一下cdq分治，寒假过去忘的差不多了。

cdq分治有时候可以用来代替复杂的数据结构，比如说树套树，并且具有更好的时间复杂度和空间复杂度。

cdq分治一般用来处理多维偏序问题，一般是三维，一般题目中都会明显地指出两个维度，另一个维度则是时间维度。

比如这个题目就是一个很好的例子。

题目连接：.php?id=1176

两个明显的维度就是两个坐标，还有一个时间维度，因为前面的操作会影响后面的查询，而查询之后的更新则不会对前面产生影响。

一般输入的序列就是保证时间这一维度是有序的。我们要处理的是剩下两个维度，一个维度在cdq分治过程中排好序，另一个则是用树状数组或其他数据结构维护。

在这个题中cdq分治的过程，对于操作2可能不是那么好处理。我们可以把它拆成四个操作，利用容斥原理得到答案，类似于二维前缀和。

在做这个题的时候我又思考了半天，为什么一边只管更新影响，一边只管查询，因为剩下的都会在之前或之后做

具体看代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+5;
const int M=2e6+5;
struct node{int t,x,y,w,id;node(){}node(int t,int x,int y,int w,int id):t(t),x(x),y(y),w(w),id(id){};bool operator<(const node n1)const{return x&(x==n1.x&&y<n1.y)||(x==n1.x&&y==n1.y&&t<n1.t);}
}p[N],tmp[N];
int tr[M],hd,aid,ans[N];
inline int lowbit(int x){return x&(-x);}
void update(int x,int d){for(;x<M;x+=lowbit(x))tr[x]+=d;
}
int sum(int x){int res=0;for(;x;x-=lowbit(x))res+=tr[x];return res;
}
void clear(int x){for(;x<M;x+=lowbit(x))tr[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 s=l,t=mid+1,o=0;while(s<=mid&&t<=r){if(p[s]<p[t]){if(p[s].t==1){update(p[s].y,p[s].w);}tmp[o++]=p[s++];}else{if(p[t].t==2)ans[p[t].id]+=p[t].w*sum(p[t].y);tmp[o++]=p[t++];}}while(s<=mid){tmp[o++]=p[s++];}while(t<=r){if(p[t].t==2)ans[p[t].id]+=p[t].w*sum(p[t].y);tmp[o++]=p[t++];}for(int i=0;i<o;i++){p[l+i]=tmp[i];if(tr[tmp[i].y]){clear(tmp[i].y);}}
}
template<class T>
void read(T &ans){ //positive integerchar ch=' ';ans=0;while(ch<'0' || ch>'9')ch=getchar();while(ch<='9' && ch>='0'){ans=ans*10+ch-'0';ch=getchar();}
}
void out(int x){if(x>9)out(x/10);putchar(x%10+'0');
}
int main(){int n,m,x,a,b,c,d;read(n),read(m);while(1){read(x);if(x==1){read(a),read(b),read(c);a++,b++;p[++hd]=node(1,a,b,c,0);}else if(x==2){read(a),read(b),read(c),read(d);a++,b++,c++,d++;p[++hd]=node(2,a-1,b-1,1,aid);p[++hd]=node(2,c,b-1,-1,aid);p[++hd]=node(2,a-1,d,-1,aid);p[++hd]=node(2,c,d,1,aid++);}elsebreak;}cdq(1,hd);for(int i=0;i<aid;i++){out(ans[i]);putchar('n');}return 0;
}