BZOJ 2683: 简单题

标签（空格分隔）： OI BZOJ cdq分治分治

Time Limit: 50 Sec
Memory Limit: 128 MB

Description

你有一个N*N的棋盘，每个格子内有一个整数，初始时的时候全部为0，现在需要维护两种操作：

命令
参数限制
内容
1 x y A
1<=x,y<=N，A是正整数
将格子x,y里的数字加上A
2 x1 y1 x2 y2
1<=x1<= x2<=N
1<=y1<= y2<=N
输出x1 y1 x2 y2这个矩形内的数字和
3
无
终止程序
Input

输入文件第一行一个正整数N。
接下来每行一个操作。

Output

对于每个2操作，输出一个对应的答案。

Sample Input

1 2 3 3

2 1 1 3 3

1 2 2 2

2 2 2 3 4

Sample Output

HINT

1<=N<=500000,操作数不超过200000个，内存限制20M。

对于100%的数据，操作1中的A不超过2000。

Solution####

同1176
cdq分治+树状数组 (O(n*log_2n))。

Code####

#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<bitset>
#include<vector>
using namespace std;
#define PA pair<int,int>
const int N=0,M=0;
int read()
{int s=0,f=1;char ch=getchar();
 while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
 while(ch>='0'&&ch<='9'){s=(s<<1)+(s<<3)+ch-'0';ch=getchar();}
 return s*f;
}
//smile please
int n,T;
struct que
{
	bool ask;int x,y,s,t,h;
}q[800005];int qs;
bool operator<(que a,que b)
{
	return a.x<b.x||(a.x==b.x&&a.ask<b.ask);
}
int s[500005];
que *a[800005];
que *aa[800005];
int ans[200005];
void gb(int l,int r)
{
	int mid=l+r>>1;
	int i=l,j=mid+1,k=l;
	for(int i=l;i<=r;i++)
	   aa[i]=a[i];
	while(i!=mid+1||j!=r+1)
	  {if(i==mid+1)a[k++]=aa[j++];
	   else if(j==r+1)a[k++]=aa[i++];
	   else if(*aa[i]<*aa[j])a[k++]=aa[i++];
	   else a[k++]=aa[j++];
	  }
}
void cdq(int l,int r)
{
	if(l>=r)return;
	int mid=l+r>>1;
	cdq(l,mid);cdq(mid+1,r);
	gb(l,r);
	for(int i=l;i<=r;i++)
	   {que now=*a[i];
	    if(now.ask)
	     {if(now.h<=mid)continue;
	      int sum=0;
		  for(int x=now.y;x;x-=x&-x)
	         sum+=s[x];
	      ans[now.t]+=sum*now.s;
		 }
	   else
	     {if(now.h>mid)continue;
	      for(int x=now.y;x<=n;x+=x&-x)
	         s[x]+=now.s;
		 }
	   }
	for(int i=l;i<=r;i++)
	   {que now=*a[i];
	    if(!now.ask)
	      {if(now.h>mid)continue;
	       for(int x=now.y;x<=n;x+=x&-x)
	          s[x]=0;
		  }
	   }
}
int main()
{
	n=read();T=1;
	for(int op=read();op!=3;op=read(),++T)
	    if(op==1)
	      q[++qs]=(que){0,read(),read(),read(),T,qs},ans[T]=-1;
		else
		  {int x1=read(),y1=read(),x2=read(),y2=read();
		   q[++qs]=(que){1,x2,y2,1,T,qs};
		   q[++qs]=(que){1,x2,y1-1,-1,T,qs};
		   q[++qs]=(que){1,x1-1,y2,-1,T,qs};
		   q[++qs]=(que){1,x1-1,y1-1,1,T,qs};
		  }
	for(int i=1;i<=qs;i++)a[i]=&q[i];
	cdq(1,qs);
	for(int i=1;i<T;i++)
	   if(ans[i]!=-1)
	     printf("%d
",ans[i]);
	return 0;
}