HDu 1892(2 Dツリー配列)
14823 ワード
1 #include<iostream>
2 using namespace std;
3 int a[1010][1010],c[1010][1010],n=1005;
4 int lowbit(int x)
5 {
6 return x&(-x);
7 }
8 int sum(int x,int y)
9 {
10 int i,j,sum=0;
11 for(i=x;i>0;i-=lowbit(i))
12 {
13 for(j=y;j>0;j-=lowbit(j))
14 {
15 sum+=c[i][j];
16 }
17 }
18 return sum;
19 }
20 void inster(int x,int y,int z)
21 {
22 int i,j;
23 for(i=x;i<=n;i+=lowbit(i))
24 {
25 for(j=y;j<=n;j+=lowbit(j))
26 {
27 c[i][j]+=z;
28 }
29 }
30 }
31 int main()
32 {
33 int x1,y1,x2,y2,t,m,i,j,n1,f=0;
34 scanf("%d",&t);
35 while(t--)
36 {
37 printf("Case %d:
",++f);
38 memset(a,0,sizeof(a));
39 memset(c,0,sizeof(c));
40 for(i=1;i<=n;i++)
41 for(j=1;j<=n;j++)
42 {
43 a[i][j]=1;
44 inster(i,j,1);
45 }
46 scanf("%d",&m);
47 while(m--)
48 {
49 char s;
50 getchar();
51 s=getchar();
52 if(s=='S')
53 {
54 scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
55 x1++;x2++;y1++;y2++;
56 if(x1>x2)
57 swap(x1,x2);
58 if(y1>y2)
59 swap(y1,y2);
60 printf("%d
",sum(x2,y2)-sum(x2,y1-1)-sum(x1-1,y2)+sum(x1-1,y1-1));
61 }
62 else
63 if(s=='A')
64 {
65 scanf("%d%d%d",&x1,&y1,&n1);
66 x1++;y1++;
67 inster(x1,y1,n1);
68 a[x1][y1]+=n1;
69 }
70 else
71 if(s=='D')
72 {
73 scanf("%d%d%d",&x1,&y1,&n1);
74 x1++;y1++;
75 if(n1>a[x1][y1])
76 n1=a[x1][y1];
77 inster(x1,y1,-n1);
78 a[x1][y1]-=n1;
79 }
80 else
81 if(s=='M')
82 {
83 scanf("%d %d %d %d %d",&x1,&y1,&x2,&y2,&n1);
84 x1++;y1++;x2++;y2++;
85 if(a[x1][y1]>=n1)
86 {
87 a[x1][y1]-=n1;
88 inster(x1,y1,-n1);
89 inster(x2,y2,n1);
90 a[x2][y2]+=n1;
91 }
92 else
93 {
94 inster(x1,y1,-a[x1][y1]);
95 inster(x2,y2,a[x1][y1]);
96 a[x2][y2]+=a[x1][y1];
97 a[x1][y1]=0;
98 }
99 }
100 }
101
102 }
103 return 0;
104 }
105 http://acm.hdu.edu.cn/showproblem.php?pid=1892