BZOJ 1176: [Balkan2007]Mokia (CDQ分治)

2019-11-08 19:54:29

字体：大中小

来源：转载

供稿：网友

BZOJ 1176: [Balkan2007]Mokia

题意概述:

一个W∗W $W*W$ 的矩阵,每个格子的初始值为S $S$ . 有两种操作: 1. 0 x y v 表示将(x,y) $(x,y)$ 点权值增加v $v$ 2. 1 x1 y1 x2 y2 表示以(x1,y1) $(x1,y1)$ 为左上角,(x2,y2) $(x2,y2)$ 为右下角的子矩阵点权和

题目分析:

又来一道CDQ (๑•̀ㅂ•́)و✧

对于询问子矩阵,将其转化成类似二维前缀和的做法——拆分成四个左上角为(1,1) $(1,1)$ .

其他和 BZOJ 3262陌上花开差不多.

(吐槽一下,似乎数据里的S好像都是0)

代码:

//Continue#include<cstdio>#include<iostream>#include<algorithm>using namespace std;const int maxn=200000+10;const int maxw=2000000+10;struct Ask { int op,x,y,t,v,k,sum;//op:1 修改 v表示修改值,2 询问 v表示正负 Ask(){sum=0;} Ask(int op,int x,int y,int t,int v):op(op),x(x),y(y),t(t),v(v){sum=0;} bool Operator < (const Ask& rhs) const { return x<rhs.x||(x==rhs.x&&(y<rhs.y||(y==rhs.y&&op<rhs.op))); }}ask[maxn];#define lowbit(x) (x&-x)int bit[maxw],W;void add(int d,int v) { for(;d<=W;d+=lowbit(d)) bit[d]+=v;}int sum(int d,int ret=0) { for(;d;d-=lowbit(d)) ret+=bit[d]; return ret;}#define mid ((l+r)>>1)void solve(int l,int r) { if(l==r) return ; solve(l,mid); solve(mid+1,r); for(int i=l;i<=r;i++) ask[i].k=(i>mid); sort(ask+l,ask+r+1); //只有左区间的修改和右区间的询问是在当前需要完成的 for(int i=l;i<=r;i++) if(ask[i].op==ask[i].k) { if(ask[i].op) ask[i].sum+=sum(ask[i].y); else add(ask[i].y,ask[i].v); } for(int i=l;i<=r;i++) if(ask[i].op==ask[i].k) if(!ask[i].op) add(ask[i].y,-ask[i].v);}int cmp(const Ask& a,const Ask& b) { return a.t<b.t;}int main() { int S,p,a,b,c,d,tot=0; scanf("%d%d",&S,&W); while(scanf("%d",&p)==1&&p!=3) { if(--p==0) { scanf("%d%d%d",&a,&b,&c); ++tot,ask[tot]=Ask(p,a,b,tot,c); } else {//询问拆成四个二维前缀询问 scanf("%d%d%d%d",&a,&b,&c,&d); ++tot,ask[tot]=Ask(p,a-1,b-1,tot,1); ++tot,ask[tot]=Ask(p,a-1,d,tot,-1); ++tot,ask[tot]=Ask(p,c,b-1,tot,-1); ++tot,ask[tot]=Ask(p,c,d,tot,1); } } solve(1,tot); sort(ask+1,ask+tot+1,cmp); for(int i=1;i<=tot;i++) if(ask[i].op) { long long now=0; for(int j=0;j<4;j++) now+=1ll*ask[i].v*(ask[i].sum+1ll*ask[i].x*ask[i].y*S),++i;--i; PRintf("%lld/n",now); } return 0;}

上一篇：程序员必读书籍及导读指南

下一篇：冒泡的一种实现方法，欢迎指出不足指出。

学习交流

索泰发布一款GTX 1070 Mini迷你版本:小机

索泰发布一款GTX 1070 Mini迷你版本:小机箱大爱...

热门图片

猜你喜欢的新闻

猜你喜欢的关注