【BZOJ1176】Mokia

题目大意：给定一个 N*N 的矩形，有 Q 次操作，每个操作可以是矩形单点修改或查询子矩形的权值和。

题解：CDQ分治适合处理修改操作之间互不影响且支持离线的题目。

满足以上操作条件的显然可以树套树来做，不过代码量起飞，我也写不出来 qaq。。

学到了利用 cdq 分治来解决这种问题。发现操作之间存在一个时间维度，即：能够对当前查询操作产生贡献的一定是时间在该询问之前的修改操作。维护子矩形的权值和可以利用二维前缀和进行处理，即：维护 (1,1) 到 (n,m) 之间的权值和即可。因此，问题转化成了在给定时间维度的前提下，求满足 x1<x2 且 y1<y2 的所有 (x1,y1) 的点对应的点权和，即：一个三维偏序问题。

代码如下

#include <cstdio>

using namespace std;

const int maxn=2e6+10;

const int maxq=2e5+10;

int n,s,bit[maxn],ans[maxq];

struct node{int x,y,val,opt,aid;}q[maxq],tmp[maxq];// opt: 0 -> modify 1 -> query

int cnt,tot;

void modify(int pos,int val){

	for(int i=pos;i<=n;i+=i&-i)bit[i]+=val;

}

int query(int pos){

	int ret=0;

	for(int i=pos;i;i-=i&-i)ret+=bit[i];

	return ret;

}

void cdq(int l,int r){

	if(l==r)return;

	int mid=l+r>>1;

	cdq(l,mid),cdq(mid+1,r);

	int x=l,y=mid+1;

	for(int i=l;i<=r;i++){

		if(y>r||(x<=mid&&q[x].x<=q[y].x)){

			tmp[i]=q[x];

			if(q[x].opt==0)modify(q[x].y,q[x].val);

			++x;

		}else{

			tmp[i]=q[y];

			if(q[y].opt==1)ans[q[y].aid]+=query(q[y].y)*q[y].val;

			++y;

		}

	}

	for(int i=l;i<=mid;i++)if(q[i].opt==0)modify(q[i].y,-q[i].val);

	for(int i=l;i<=r;i++)q[i]=tmp[i];

}

void add(int x,int y,int val,int opt){

	++tot,q[tot].x=x,q[tot].y=y,q[tot].val=val,q[tot].opt=opt;

	if(q[tot].opt==1)q[tot].aid=cnt;

}

void read_and_parse(){

	scanf("%d%d",&s,&n);

	while(1){

		int opt;scanf("%d",&opt);

		if(opt==3)break;

		if(opt==1){

			int x,y,a;

			scanf("%d%d%d",&x,&y,&a);

			add(x,y,a,0);

		}

		if(opt==2){

			int x1,x2,y1,y2;

			scanf("%d%d%d%d",&x1,&y1,&x2,&y2);

			++cnt,add(x2,y2,1,1),add(x2,y1-1,-1,1),add(x1-1,y2,-1,1),add(x1-1,y1-1,1,1);

		}

	}

}

void solve(){

	cdq(1,tot);

	for(int i=1;i<=cnt;i++)printf("%d\n",ans[i]);

}

int main(){

	read_and_parse();

	solve();

	return 0;

}

巴特西

【BZOJ1176】Mokia

最新文章

热门文章