fork download
copy 
  1. #include "stdio.h"
  2. #include "string.h"
  3. #include "cstdio"
  4. #include "cstdlib"
  5. #include "cmath"
  6. #include "iostream"
  7.  
  8. long long int tree[5000001]={0};
  9. using namespace std;
  10.  
  11. 	inline long readLong()
  12. 	{
  13. 		char t;
  14. 		long x=0;
  15. 		t=getchar_unlocked();
  16. 		while(t<48 || t>57)
  17. 			t=getchar_unlocked();
  18. 		x+=(t-'0');
  19. 		t=getchar_unlocked();
  20. 		while(t>=48 && t<=57)
  21. 		{
  22. 			x*=10;
  23. 			x+=(t-'0');
  24. 			t=getchar_unlocked();
  25. 		}
  26. 		return x;
  27. 	} 
  28.  
  29. 	inline int readInt()
  30. 	{
  31. 		char t;
  32. 		int x=0;
  33. 		t=getchar_unlocked();
  34. 		while(t<48 || t>57)
  35. 			t=getchar_unlocked();
  36. 		x+=(t-'0');
  37. 		t=getchar_unlocked();
  38. 		while(t>=48 && t<=57)
  39. 		{
  40. 			x*=10;
  41. 			x+=(t-'0');
  42. 			t=getchar_unlocked();
  43. 		}
  44. 		return x;
  45. 	} 
  46.  
  47.  
  48. inline void fastOutput(long long int n)
  49. {
  50. 	int i=21;
  51. 	char output_buffer[22];
  52. 	output_buffer[21]='\n';
  53. 	do
  54. 	{
  55. 		output_buffer[--i]=(n%10)+'0';
  56. 		n/=10;
  57. 	}while(n);
  58. 	do
  59. 	{
  60. 		putchar_unlocked(output_buffer[i]);
  61. 	}while(++i<22);
  62. }
  63.  
  64.  
  65. void buildTree(int ar[],long Node,long a,long b)
  66. {
  67. 	if(a>b)			// for cases where i,j are out of the required range
  68. 		return;
  69. 	if(a==b)		// on reaching the leaf node
  70. 		{	
  71. 			tree[Node]=ar[a];		// assigning value 
  72. 			return;
  73. 		}
  74. 	long mid = (a+b)/2;
  75. 	buildTree(ar,(Node*2),a,mid);			//divide into left half of  tree
  76. 	buildTree(ar,1+(Node*2),mid+1,b);		//divide into right half of tree
  77. 	tree[Node]=tree[(Node*2)]+tree[(Node*2)+1];	//storing sum of 2 child nodes into the parent node
  78.  
  79. }
  80.  
  81.  
  82. // void update(int ar[],long long tree[],int value,long i,long j,long a,long b,long Node)
  83. // {
  84. // 	if(a>j || b<i || a>b )
  85. // 		return;
  86. // 	if(a==i && b==j )
  87. // 		{
  88. // 			tree[Node] +=value;
  89. // 			return;
  90. // 		}
  91.  
  92. // 	long mid = (a+b)/2;
  93. // 	update(ar,tree,value,i,j,a,mid,(Node*2));
  94. // 	update(ar,tree,value,i,j,mid+1,b,1+(Node*2));
  95. // 	tree[Node]=tree[2*Node]+tree[(2*Node)+1];
  96. // }
  97.  
  98.  
  99. long long query(int ar[],long Node,long a,long b,long i,long j)
  100. {
  101. 	if(a>b || b<i || a>j )
  102. 		return 0;
  103. 	if(a>=i && b<=j )
  104. 		return tree[Node];
  105. 	long mid = (a+b)/2;
  106. 	long long q1= query(ar,(Node*2),a,mid,i,j);
  107. 	long long q2= query(ar,1+(Node*2),mid+1,b,i,j);
  108. 	return (q1+q2);
  109. }
  110.  
  111.  
  112. int main()
  113. {
  114. 	long long n,q;
  115. 	// scanf("%lld",&n);
  116. 	// scanf("%lld",&q);
  117. 	n=readLong();
  118. 	q=readLong();
  119. 	int a[n];
  120. 	for (int i = 0; i <n; i++)
  121. 		a[i]=readInt();
  122. 	buildTree(a,1,0,(n-1));
  123. 	for (int i = 0; i < q; i++)
  124. 	{
  125. 		char ch;
  126. 		long l,r;
  127. 		ch=getchar_unlocked();
  128.     	while(1)//maybe there is some extra space in the input file...according to the comments on the problem page!!!!
  129.     	{
  130.     		if(ch=='S'||ch=='T'||ch=='G')
  131.     		{
  132.     			break;
  133.     		}
  134.     		ch=getchar_unlocked();
  135.     	}
  136. 		l=readLong();
  137. 		r=readLong();
  138. 		if(ch=='S')
  139. 		{
  140. 			printf("%lld\n", query(a,1,0,(n-1),l,r));
  141. 		}
  142. 		else if(ch=='G')
  143. 		{
  144. 			a[l]+=r;
  145. 			buildTree(a,1,0,(n-1));
  146. 		}
  147. 		else
  148. 		{
  149. 			a[l]-=r;
  150. 			buildTree(a,1,0,(n-1));
  151. 		}
  152.  
  153. 	}
  154. 	return 0;
  155. }
  156.  
Success #stdin #stdout 0s 41752KB
comments (?)
stdin
copy 
5 3
1000 1002 1003 1004 1005
S 0 2
G 0 3
S 0 2
stdout
copy 
3005
3008
https://ideone.com/ZScyoG
language:
C++ 4.3.2 (gcc-4.3.2)
created:
10 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!