二维树状数组
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62 |
#include <cstdio>#include <algorithm>using
namespace std;#define N 1005int c[N][N];int i,j,n,num,p,T,cnt=1;int sum(int
x,int y){ int
i,j,tmp=0; for(i=x;i>0;i-=(i&-i)) for(j=y;j>0;j-=(j&-j)) tmp+=c[i][j]; return
tmp;}void
add(int
x,int y,int num){ for(int
i=x;i<N;i+=(i&-i)) for(int
j=y;j<N;j+=(j&-j)) c[i][j]+=num;}void
init(){ for(int
i=1;i<N;i++)for(int
j=1;j<N;j++)c[i][j]=0; for(int
i=1;i<N;i++)for(int
j=1;j<N;j++)add(i,j,1);}void
scan(int
&x){ char
c; while(c=getchar(),c>‘9‘||c<‘0‘);x=c-‘0‘; while(c=getchar(),c<=‘9‘&&c>=‘0‘)x=x*10+c-‘0‘;} int
main(){ char
s[10]; char
c1,c2; int
y1,y2,x1,x2; scanf("%d",&T); while(T--){ scanf("%d",&n); init(); printf("Case %d:\n",cnt++); while(n--){ c1=getchar(); if(c1==‘A‘){ scan(x1),scan(y1),scan(num); add(x1+1,y1+1,num); }else
if(c1==‘S‘){ scan(x1),scan(y1),scan(x2),scan(y2); if(x1<x2) swap(x1,x2); if(y1<y2) swap(y1,y2); printf("%d\n",sum(x1+1,y1+1)-sum(x1+1,y2)-sum(x2,y1+1)+sum(x2,y2)); }else
if(c1==‘D‘){ scan(x1),scan(y1),scan(num); p=sum(x1+1,y1+1)-sum(x1,y1+1)-sum(x1+1,y1)+sum(x1,y1); num=p<num?p:num; add(x1+1,y1+1,-num); }else
if(c1==‘M‘){ scan(x1),scan(y1),scan(x2),scan(y2),scan(num); p=sum(x1+1,y1+1)-sum(x1,y1+1)-sum(x1+1,y1)+sum(x1,y1); num=num<p?num:p; add(x1+1,y1+1,-num); add(x2+1,y2+1,num); }else
n++; } } return
0;} |
原文：http://www.cnblogs.com/forever97/p/3562500.html