【 HDU - 4456 】Crowd (二维树状数组、cdq分治)

#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 80005
#define M 4000000
using namespace std;
int n,m,sum[M];
int p[N],qx[N],qy[N],z[N],h[M],cnt;
void add(int x,int y,int z){
	for(;x<=n;x+=x&(-x))
	for(int j=y;j<=n;j+=j&(-j))
		h[cnt++]=x*n+j;
}
void update(int x,int y,int z){
	for(;x<=n;x+=x&(-x))
	for(int j=y;j<=n;j+=j&(-j)){
		int pos=lower_bound(h, h+cnt, x*n+j)-h;
		sum[pos]+=z;
	}
}
int getsum(int x,int y){
	int ans=0;
	for(;x;x-=x&(-x))
	for(int j=y;j;j-=j&(-j)){
		int pos=lower_bound(h, h+cnt, x*n+j)-h;
		if(x*n+j==h[pos])ans+=sum[pos];
	}
	return ans;
}
int main() {
	while(scanf("%d",&n),n){
		n*=2;cnt=0;
		memset(sum,0,sizeof sum);
		scanf("%d",&m);
		for(int i=1,x,y;i<=m;i++){
			scanf("%d%d%d%d",&p[i],&x,&y,&z[i]);
			qx[i]=x-y+n/2,qy[i]=x+y;
			if(p[i]==1)add(qx[i],qy[i],z[i]);
		}
		sort(h,h+cnt);
		for(int i=1;i<=m;i++){
			if(p[i]==1)update(qx[i],qy[i],z[i]);
			else{
				int lx=max(1,qx[i]-z[i])-1,rx=min(qx[i]+z[i],n);
				int ly=max(1,qy[i]-z[i])-1,ry=min(qy[i]+z[i],n);
				printf("%d\n",getsum(rx,ry)-getsum(lx,ry)-getsum(rx,ly)+getsum(lx,ly));
			}
		}
	}	
	return 0;
}

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#define M 80005
#define N 20005
using namespace std;
struct Query{
	int p,x,y,z,i,t;
}q[M<<2],tq[M<<2];
bool cmp(Query a,Query b){
	if(a.x==b.x){
		if(a.y==b.y)return a.p<b.p;
		return a.y<b.y;
	}
	return a.x<b.x;
}
int sum[N],n2;
void add(int x,int v){
	for(;x<=n2;x+=x&(-x))sum[x]+=v;
}
int getsum(int x){
	int ans=0;
	for(;x;x-=x&(-x))ans+=sum[x];
	return ans;
}
int ans[M],cnt;
void solve(int l,int r){
	if(l==r)return;
	int mid=l+r>>1;
	for(int i=l;i<=r;i++)
		if(q[i].p==1&&q[i].t<=mid)
			add(q[i].y,q[i].z);
		else if(q[i].p==2&&q[i].t>mid)
			ans[q[i].i]+=q[i].z*getsum(q[i].y);
	for(int i=l;i<=r;i++)if(q[i].p==1&&q[i].t<=mid)
		add(q[i].y,-q[i].z);
	int l1=l-1,l2=mid;
	for(int i=l;i<=r;i++)
		if(q[i].t<=mid)tq[++l1]=q[i];
		else tq[++l2]=q[i];
	for(int i=l;i<=r;i++)q[i]=tq[i];
	solve(l,mid);solve(mid+1,r);
}
int n,m;
int main() {
	while(scanf("%d",&n),n){
		scanf("%d",&m);
		int t=0;cnt=0;n2=n*2;
		memset(ans,0,sizeof ans);
		for(int i=1,p,x,y,z;i<=m;i++){
			scanf("%d%d%d%d",&p,&x,&y,&z);
			if(p==1){
				cnt++;
				q[cnt]=(Query){p,x+y,x-y+n,z,0,cnt};
			}else{
				t++;
				int xx=x+y,yy=x-y+n;
				int x1=max(xx-z-1,1),y1=max(yy-z-1,1);
				int x2=min(xx+z,n2),y2=min(yy+z,n2);
				cnt++;
				q[cnt]=(Query){p,x1,y1,1,t,cnt};
				cnt++;
				q[cnt]=(Query){p,x2,y2,1,t,cnt};
				cnt++;
				q[cnt]=(Query){p,x2,y1,-1,t,cnt};
				cnt++;
				q[cnt]=(Query){p,x1,y2,-1,t,cnt};
			}
		}
		sort(q+1,q+1+cnt,cmp);
		solve(1,cnt);
		for(int i=1;i<=t;i++)printf("%d\n",ans[i]);
	}
	return 0;
}