首页 > 代码库 > BZOJ 1176 [Balkan2007]Mokia CDQ分治
BZOJ 1176 [Balkan2007]Mokia CDQ分治
题目大意:
维护一个W*W的矩阵,初始值均为S.每次操作可以增加某格子的权值,或询问某子矩阵的总权值.修改操作数M<=160000,询问数Q<=10000,W<=2000000.
POJ1195的加强版
没记错的话上午这题还没有中文题目描述的说0.0 好迅速
首先这题看到W就知道二维树状数组挂了 看到M就发现离散化了也搞不了 0.0
这题似乎是CDQ分治被发现之后第二个解决的题目。。。不过只有会员才知道的世界,今天反应过来刷刷。。。
修改和询问放在一起分治,一个询问拆分成4个,树状数组处理,每层分治处理左区间中修改对右区间的询问即可
此外题目描述有误,S不是初值,是操作的编号,我还纳闷怎么没加初值就AC了0.0 所以S恒为0,不用管了
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define M 2002002 using namespace std; struct abcd{ int x,y,num,pos,ans; abcd(){} abcd(int X,int Y,int Num); bool operator <(const abcd &y)const { return x < y.x; } }q[200200],nq[200200]; int num,w,n,ans; int c[M],tim[M],T; void update(int x,int y) { for(;x<=w;x+=x&-x) { if(tim[x]!=T) c[x]=0; tim[x]=T; c[x]+=y; } } int getans(int x) { int re=0; for(;x;x-=x&-x) if(tim[x]==T) re+=c[x]; return re; } bool cmp(const abcd &x,const abcd &y) { return x.pos < y.pos; } abcd :: abcd(int X,int Y,int Num) { x=X; y=Y; num=Num; pos=n; ans=0; } void CDQ(int l,int r) { int i,j,mid=l+r>>1; int l1=l,l2=mid+1; if(l==r) return ; for(i=l;i<=r;i++) { if(q[i].pos<=mid) nq[l1++]=q[i]; else nq[l2++]=q[i]; } memcpy( q+l , nq+l , sizeof(q[0])*(r-l+1) ); CDQ(l,mid); j=l;++T; for(i=mid+1;i<=r;i++) { for(;q[j].x<=q[i].x&&j<=mid;j++) if(q[j].num!=19980402) update(q[j].y,q[j].num); if(q[i].num==19980402) q[i].ans+=getans(q[i].y); } CDQ(mid+1,r); l1=l;l2=mid+1; for(i=l;i<=r;i++) { if(q[l1]<q[l2]&&l1<=mid||l2>r) nq[i]=q[l1++]; else nq[i]=q[l2++]; } memcpy( q+l , nq+l , sizeof(q[0])*(r-l+1) ); } int main() { int i,p,x,y,z,x1,y1,x2,y2; cin>>num>>w; while(scanf("%d",&p),p^3) { if(p==1) scanf("%d%d%d",&x,&y,&z),q[++n]=abcd(x,y,z); else { scanf("%d%d%d%d",&x1,&y1,&x2,&y2); q[++n]=abcd(x1-1,y1-1,19980402); q[++n]=abcd(x1-1,y2,19980402); q[++n]=abcd(x2,y1-1,19980402); q[++n]=abcd(x2,y2,19980402); } } sort(q+1,q+n+1); CDQ(1,n); sort(q+1,q+n+1,cmp); for(i=1;i<=n;i++) if(q[i].num==19980402) { ans=0; ans+=q[i++].ans; ans-=q[i++].ans; ans-=q[i++].ans; ans+=q[i ].ans; printf("%d\n",ans); } }
BZOJ 1176 [Balkan2007]Mokia CDQ分治
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。