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;