fork(1) download
copy 
  1. #include<cstdio>
  2. #include<algorithm>
  3. #include<vector>
  4. #include<cstring>
  5. #include<cmath>
  6. #include<stack>
  7. #include<queue>
  8. #include<map>
  9. using namespace std;
  10.  
  11. #define sd(a) scanf("%d",&a)
  12. #define pd(a) printf("%d\n",(a))
  13. #define LL long long
  14. int t[2050][2050];
  15. int pos[1050][1050],n;
  16.  
  17. void build1(int node,int si,int sj,int parent,int row)
  18. {
  19. 	if(si==sj)
  20. 	{
  21. 		t[parent][node]=0;
  22. 		pos[row][si]=parent*10000+node;
  23. 		return;
  24. 	}
  25. 	build1(node*2,si,(si+sj)/2,parent,row);
  26. 	build1(node*2+1,(si+sj)/2+1,sj,parent,row);
  27. 	t[parent][node]=0;
  28. }
  29. void build(int node,int si,int sj)
  30. {
  31. 	int i;
  32. 	if(si==sj)
  33. 	{	
  34. 		build1(1,0,n-1,node,si);
  35. 		return;
  36. 	}
  37. 	build(node*2,si,(si+sj)/2);
  38. 	build(node*2+1,(si+sj)/2+1,sj);
  39. 	int lim=pow(2,1+ceil(log2(n)));
  40. 	for(i=1;i<=2000;++i)
  41. 		t[node][i]=0;
  42. }
  43. void update1(int node,int parent,int diff)
  44. {
  45. 	if(node)
  46. 	{
  47. 		t[parent][node]+=diff;
  48. 		update1(node>>1,parent,diff);
  49. 	}
  50. }
  51. void update(int node,int child,int diff)
  52. {
  53. 	if(node)
  54. 	{
  55. 		t[node][child]+=diff;
  56. 		update1(child>>1,node,diff);
  57. 		update(node>>1,child,diff);
  58. 	}
  59. }
  60. int query1(int node,int si,int sj,int st,int en,int parent)
  61. {
  62. 	if(si>en||sj<st)
  63. 		return 0;
  64. 	if(si>=st&&sj<=en)
  65. 	{
  66. 		return t[parent][node];
  67. 	}
  68. 	return (query1(node*2,si,(si+sj)/2,st,en,parent)+query1(node*2+1,(si+sj)/2+1,sj,st,en,parent));
  69. }
  70. int query(int node,int si,int sj,int st,int en,int cols,int cole)
  71. {
  72. 	if(si>en||sj<st)
  73. 		return 0;
  74. 	if(si>=st&&sj<=en)
  75. 	{
  76. 		return query1(1,0,n-1,cols,cole,node);
  77. 	}
  78. 	return query(node*2,si,(si+sj)/2,st,en,cols,cole)+query(node*2+1,(si+sj)/2+1,sj,st,en,cols,cole);
  79. }
  80. int main()
  81. {
  82. 	int test,x,y,x1,y1,num,hash,diff,x2,y2;
  83. 	char s[5];
  84. 	sd(test);
  85. 	while(test--)
  86. 	{
  87. 		sd(n);
  88. 		build(1,0,n-1);
  89. 		while(true)
  90. 		{
  91. 			scanf("%s",&s);
  92. 			if(s[1]=='E')
  93. 			{
  94. 				scanf("%d %d %d",&x,&y,&num);
  95. 				hash=pos[x][y];
  96. 				x1=hash/10000;
  97. 				y1=hash%10000;
  98. 				diff=num-t[x1][y1];
  99. 				t[x1][y1]=num;
  100. 				update1(y1>>1,x1,diff);
  101. 				update(x1>>1,y1,diff);
  102. 			}
  103. 			else if(s[1]=='U')
  104. 			{
  105. 				scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
  106. 				printf("%d\n",query(1,0,n-1,x1,x2,y1,y2));
  107. 			}
  108. 			else
  109. 			{
  110. 				printf("\n");
  111. 				break;
  112. 			}
  113. 		}
  114. 	}
  115. }
  116.  
  117.  
Success #stdin #stdout 0s 23408KB
comments (?)
stdin
copy 
1
4
SET 0 0 1
SUM 0 0 3 3
SET 2 2 12
SUM 2 2 2 2
SUM 2 2 3 3
SUM 0 0 2 2
END
stdout
copy 
1
12
12
13
https://ideone.com/ysu8Tr
language:
C++ 4.3.2 (gcc-4.3.2)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!