题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1892
题目大意:
在一个1001*1001的每一个点的初始值为1的矩形中,对某一点上的数值进行加减,或从某一点移动若干数值到某一点,并会有询问某子矩形中的数值,这个子矩形的边与母矩形平行.
题目思路:
二维树状数组...坑爹的一开始写了个二维线段树 =,=,TLE了...
代码:
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include <ctype.h>
#include <math.h>
#include <time.h>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <vector>
#include <string>
#include <iostream>
#include <algorithm>
using namespace std;
#define ll __int64
//#define ll long long
#define son1 New(p.xl,xm,p.yl,ym),(rt<<2)-2
#define son2 New(p.xl,xm,ym+1,p.yr),(rt<<2)-1
#define son3 New(xm+1,p.xr,p.yl,ym),rt<<2
#define son4 New(xm+1,p.xr,ym+1,p.yr),rt<<2|1
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define middle (l+r)>>1
#define ONE 0x00000001
#define INF 0x3F3F3F3F
#define esp (1e-8)
#define MOD 100000007
#define type int
//const double pi=acos(-1.0);
const int M=1005;
type min(type x,type y){return x<y? x:y;}
type max(type x,type y){return x>y? x:y;}
void swap(type& x,type& y){type t=x;x=y;y=t;}
int T,cas=0;
int n,val[M][M],init[M][M];
int lowbit(int x){return (-x)&x;}
void initAdd(int x,int y,int c){
int t=y;
for(;x<M;x+=lowbit(x))
for(y=t;y<M;y+=lowbit(y))
init[x][y]+=c;
}
void add(int x,int y,int c){
int t=y;
for(;x<M;x+=lowbit(x))
for(y=t;y<M;y+=lowbit(y))
val[x][y]+=c;
}
int sum(int x,int y){
int ret=0,t=y;
for(;x>0;x-=lowbit(x))
for(y=t;y>0;y-=lowbit(y))
ret+=val[x][y];
return ret;
}
void run(){
scanf("%d",&n);
memcpy(val,init,sizeof(init));
printf("Case %d:\n",cas);
char op[2];
int x1,y1,x2,y2,c;
while(n--){
scanf("%s",op);
if(op[0]=='S'){
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
if(x1>x2) swap(x1,x2);
if(y1>y2) swap(y1,y2);
x1+=2,y1+=2,x2+=2,y2+=2;
printf("%d\n",sum(x2,y2)-sum(x1-1,y2)-sum(x2,y1-1)+sum(x1-1,y1-1));
}else if(op[0]=='M'){
scanf("%d%d%d%d%d",&x1,&y1,&x2,&y2,&c);
x1+=2,y1+=2,x2+=2,y2+=2;
c=min(c,sum(x1,y1)-sum(x1-1,y1)-sum(x1,y1-1)+sum(x1-1,y1-1));
add(x1,y1,-c),add(x2,y2,c);
}else{
scanf("%d%d%d",&x1,&y1,&c);
x1+=2,y1+=2;
if(op[0]=='A') add(x1,y1,c);
else{
c=min(c,sum(x1,y1)-sum(x1-1,y1)-sum(x1,y1-1)+sum(x1-1,y1-1));
add(x1,y1,-c);
}
}
}
}
int main(){
//freopen("1.in","r",stdin);
//freopen("1.out","w",stdout);
//run();
for(int i=1;i<M;i++)
for(int j=1;j<M;j++)
initAdd(i,j,1);
for(scanf("%d",&T),cas=1;cas<=T;cas++) run();
//while(~scanf("%d",&n) && n) run();
//system("pause");
return 0;
}