BZOJ 1176: [Balkan2007]Mokia CDQ分治

第一道CDQ分治….

》谈一类分治算法的应用:

算法分析

W≤1000W很大，开二维树状数组O(W2)的空间显然吃不消，考虑使用动态空间的线段树，最多可能达到操作次数*(log2W)2个节点，，也相当大了．考虑使用分治思想来解决问题：

Tot个事件，Tot≤170000．类似例题一，我们定义Solve(l,r)表示对于每一个Query操作的事件i，将l..i-1的Add操作的所有属于i的矩形范围内的数值累加进来．目标是Solve(1,n)．

假设计算Solve(L,R)，递归Solve(L,Mid)，Solve(Mid+1,r)后，对L..Mid的所有Add操作的数值累加到Mid+1..R的所有匹配的Query操作的矩形中．

后面这个问题等价于：平面中有p个点，q个矩形，每个点有一个权值，求每个矩形内的点的权值之和．这个问题只需要对所有的点以及矩形的左右边界进行排序，用一维树状数组或线段树在O((p+q)log2W)的时间复杂度即可维护得出．

因此问题的总的时间复杂度为O(Tot*log2Tot*log2W)，不会高于二维线段树的O(Tot*log2W*log2W)的时间复杂度．

1176: [Balkan2007]MokiaTime Limit:30 SecMemory Limit:162 MBSubmit:1137Solved:476[Submit][Status][Discuss]Description

维护一个W*W的矩阵，初始值均为S.每次操作可以增加某格子的权值,或询问某子矩阵的总权值.修改操作数M<=160000,询问数Q<=10000,W<=2000000.

Input

第一行两个整数,S,W;其中S为矩阵初始值;W为矩阵大小接下来每行为一下三种输入之一(不包含引号):"1 x y a""2 x1 y1 x2 y2""3"输入1:你需要把(x,y)(第x行第y列)的格子权值增加a输入2:你需要求出以左上角为(x1,y1),右下角为(x2,y2)的矩阵内所有格子的权值和,并输出输入3:表示输入结束

Output

对于每个输入2,输出一行,即输入2的答案

Sample Input

0 41 2 3 32 1 1 3 31 2 2 22 2 2 3 43

Sample Output

HINT

保证答案不会超过int范围

Source[Submit][Status][Discuss]

#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>using namespace std;const int maxn=200200;int s,w;int n;struct Node{int x,y,kind,pos,num;bool operator<(const Node& node) const{return x<node.x;}void toString(){printf(" (%d,%d) k: %d p: %d num: %d\n",x,y,kind,pos,num);}}T[maxn],nT[maxn];bool cmp(Node a,Node b){return a.pos<b.pos;}/***********树状数组**************/int C;int Color[maxn*10],tree[maxn*10];inline int lowbit(int x){return x&(-x);}void Add(int p,int v){for(int i=p;i<=w;i+=lowbit(i)){if(Color[i]!=C) tree[i]=0;Color[i]=C;tree[i]+=v;}}int Sum(int p){int ret=0;for(int i=p;i;i-=lowbit(i)){if(Color[i]==C)ret+=tree[i];}return ret;}/****************CDQ*********************/void CDQ(int l,int r){if(l==r) return;int mid=(l+r)/2;int l1=l,l2=mid+1;for(int i=l;i<=r;i++){if(T[i].pos<=mid) nT[l1++]=T[i];else nT[l2++]=T[i];}memcpy(T+l,nT+l,sizeof(T[0])*(r-l+1));CDQ(l,mid);/// 左半部分对右半部分的影响int j=l; C++;for(int i=mid+1;i<=r;i++){for(;T[j].x<=T[i].x&&j<=mid;j++){if(T[j].kind==1){Add(T[j].y,T[j].num);}}if(T[i].kind==2){T[i].num+=Sum(T[i].y);}}CDQ(mid+1,r);/// Recoverl1=l,l2=mid+1;for(int i=l;i<=r;i++){if((T[l1]<T[l2]&&l1<=mid)||l2>r) nT[i]=T[l1++];else nT[i]=T[l2++];}memcpy(T+l,nT+l,sizeof(T[0])*(r-l+1));}int main(){scanf("%d%d",&s,&w);int k,x1,y1,x2,y2,S;while(scanf("%d",&k)&&k!=3){if(k==1){scanf("%d%d%d",&x1,&y1,&S);n++; T[n]=(Node){x1,y1,1,n,S};}else if(k==2){scanf("%d%d%d%d",&x1,&y1,&x2,&y2);/// Add 4 Noden++; T[n]=(Node){x1-1,y1-1,2,n,0};n++; T[n]=(Node){x1-1,y2,2,n,0};n++; T[n]=(Node){x2,y1-1,2,n,0};n++; T[n]=(Node){x2,y2,2,n,0};}}sort(T+1,T+1+n);CDQ(1,n);sort(T+1,T+1+n,cmp);for(int i=1;i<=n;i++){if(T[i].kind==2){int ans=0;ans+=T[i].num; i++;ans-=T[i].num; i++;ans-=T[i].num; i++;ans+=T[i].num;printf("%d\n",ans);}}return 0;}

自己选择的路，跪着也要把它走完。

相关文章：

你感兴趣的文章：

标签云：