题解 P4390 【[BOI2007]Mokia 摩基亚】

Nemlit

2019-01-19 17:18:32

Solution

upd:$(x1,y1)(x2,y2)$表示以$(x1,y1)$为左上端点 $(x2,y2)$为右下端点的矩形 本来以为是一道二位树状数组的模板,但是看数据范围之后就放弃了,边界既然到了2000000,那么我们只能使用其他办法来代替树状数组 ~~于是,CDQ分治就诞生了!~~ 此题我们可以把问题转化成[cdq分治模板](https://www.luogu.org/problemnew/show/P3810) 回忆一下二位树状数组是怎么求二维区间查询的:对于区间[x1,y1][x2,y2],我们把它转化成$ (1,1)(x1-1,y1-1)+(1,1)(x2,y2)-(1,1)(x1-1,y2)-(1,1)(x2,y1-1) $求即可,所以对于每一个询问操作,把他看成四个坐标,求出前缀和就能找到答案 把操作的时间看作一维(时间在前的才可能对后面的操作有影响),把x,y看作后两维,对于$(1,1)(x,y)$,那么问题就转化成了$timea<timeb xa<xb ya<yb$的数量,也就是三位偏序模板了 注意几点: 1、树状数组的下标不能为0(0的lowbit的值也是0),所以我们需要把每一个点横纵坐标加一,最后w也要记得+1 2、注意区分询问和加法,在操作树状数组时要区分 给出代码: ``` #include<bits/stdc++.h> using namespace std; #define il inline #define re register #define debug printf("Now is Line : %d\n",__LINE__) il int read() { re int x=0,f=1;re char c=getchar(); while(c<'0'||c>'9') {if(c=='-') f=-1;c=getchar();} while(c>='0'&&c<='9') x=x*10+c-48,c=getchar(); return x*f; } #define lb(x) (x)&-(x) #define maxn 200005 #define maxm 2000005 struct node { int tim,x,y,val,id; }e[maxn]; int cnt,a[maxm],w; il void add(int x,int v) { while(x<=w) { a[x]+=v; x+=lb(x); } } il int query(int x) { int ans=0; while(x) { ans+=a[x]; x-=lb(x); } return ans; } il bool cmp1(node a,node b) { return (a.x==b.x)?(a.y<b.y):(a.x<b.x); } il bool cmp(node a,node b) { return a.tim<b.tim; } il void CDQ(int l,int r) { if(l==r) return; int mid=(l+r)>>1; CDQ(l,mid),CDQ(mid+1,r); sort(e+l,e+mid+1,cmp1); sort(e+mid+1,e+r+1,cmp1); re int i=l,j=mid+1; for(;j<=r;++j) { while(e[i].x<=e[j].x&&i<=mid) { if(e[i].id==0) add(e[i].y,e[i].val); ++i; } if(e[j].id==1) e[j].val+=query(e[j].y); } for(j=l;j<i;++j) if(e[j].id==0) add(e[j].y,-e[j].val); } int main() { read(),w=read()+1; int opt=read(); while(opt!=3) { if(opt==1) { int x=read()+1,y=read()+1,val=read(); e[++cnt]=(node){cnt,x,y,val,0}; } else { int x1=read(),y1=read(),x2=read()+1,y2=read()+1; e[++cnt]=(node){cnt,x1,y1,0,1}; e[++cnt]=(node){cnt,x2,y2,0,1}; e[++cnt]=(node){cnt,x2,y1,0,1}; e[++cnt]=(node){cnt,x1,y2,0,1}; } opt=read(); } CDQ(1,cnt); sort(e+1,e+cnt+1,cmp); for(re int i=1;i<=cnt;++i) { if(e[i].id==1) { printf("%d\n",e[i].val+e[i+1].val-e[i+2].val-e[i+3].val); i+=3; } } return 0; } ```