fork download
copy 
  1.  
  2. #include <iostream>
  3. #include <string>
  4. #include <string.h>
  5. using namespace std;
  6.  
  7.  
  8. struct Node {
  9. 	long sum;
  10. 	int CountV[10];
  11. 	int pending;
  12. } ;
  13.  
  14. 	Node *Tree;
  15.  
  16. int max(int a, int b) {
  17. 	if (a > b) return a;
  18. 	else return b;
  19. }
  20.  
  21. int min(int a, int b) {
  22. 	if (a < b) return a;
  23. 	else return b;
  24. }
  25.  
  26.  
  27. void AddMod(int U, int delt) {
  28. //cout << "!!"<<U<<" "<<delt<<endl;
  29. 	int temp[10];
  30. 	memcpy(temp, Tree[U].CountV, 10 * sizeof(int));
  31. 	for (int i = 0;i<10;i++)
  32. 		Tree[U].CountV[(i + delt) % 10] = temp[i];
  33. }
  34.  
  35. void addV(int &x, int y) {
  36. 	x += y;
  37. 	x %= 10;
  38. }
  39.  
  40. void relax(int U, int d){
  41.     AddMod(U, d);
  42.     addV(Tree[U].pending, d);
  43.     Tree[U].sum = 0;
  44. 	for (int i = 0;i<10;i++)
  45. 			Tree[U].sum += i*Tree[U].CountV[i];
  46. }
  47.  
  48. void forcePush(int U){
  49.  
  50. 	relax(2*U,Tree[U].pending);
  51. 	relax(2*U + 1,Tree[U].pending);
  52.  
  53. 	Tree[U].pending = 0;
  54. 	Tree[U].sum = 0;
  55. 	for (int i = 0;i<10;i++)
  56. 		Tree[U].sum += i*(Tree[U].CountV[i] = Tree[2 * U].CountV[i] + Tree[2 * U + 1].CountV[i]);
  57. }
  58.  
  59. void add(int U, int L, int R, int l, int r, int val) {
  60.     //cout <<U<<" "<<L<<" "<<R<<" "<<l<<" "<<r<<" <---> "<<val<<endl;
  61. 	if (L >= r || R <= l) return;
  62. 	l = max(l, L);
  63. 	r = min(R, r);
  64. 	if (L == l && R == r) {
  65. 	    relax(U,val);
  66. 		//cout << " <---> "<<"?"<<Tree[U].sum<<endl;	
  67. 		return;
  68. 	}
  69. 	forcePush(U);
  70. 	add(2 * U, L, (L + R) >> 1, l, r, val);
  71. 	add(2 * U + 1, (L + R) >> 1, R, l, r, val);
  72. 	forcePush(U);
  73.  
  74. }
  75.  
  76.  
  77.  
  78. long getSum(int U, int L, int R, int l, int r) {
  79. 	if (L >= r || R <= l)
  80. 	   return 0;
  81. 	l = max(l, L);
  82. 	r = min(R, r);
  83. 	if (L == l && R == r) 
  84. 		return Tree[U].sum;
  85. 	forcePush(U);
  86. 	long res = getSum(2 * U, L, (L + R) >> 1, l, r) + getSum(2 * U + 1, (L + R) >> 1, R, l, r);
  87.  
  88.     //cout <<U<<" "<<L<<" "<<R<<" "<<l<<" "<<r<<" ---> "<<res<<endl;
  89. 	return res;
  90. }
  91. int *INIT;
  92.  
  93. void init(int U, int L, int R){
  94.     if (L >= R) return;
  95.     if (L + 1 == R){
  96.         Tree[U].CountV[ INIT[L] ] = 1;
  97.         Tree[U].sum = INIT[L];
  98.         return;
  99.     }
  100.     init(2*U,L, (L + R) >> 1);
  101.     init(2*U+1,(L + R) >> 1,R);
  102. 	for (int i = 0;i<10;i++)
  103. 		Tree[U].sum += i*(Tree[U].CountV[i] = Tree[2 * U].CountV[i] + Tree[2 * U + 1].CountV[i]);
  104. }
  105.  
  106. int main()
  107. {
  108. 	int size, opNumber;
  109. 	cin >> size >> opNumber;
  110.  
  111. 	Tree = new Node[4 * size];
  112. 	memset(Tree,0,sizeof(Node)*4*size);
  113. 	INIT = new int[size];
  114.  
  115. 	for (int i = 0; i < size; i++)
  116. 		cin >> INIT[i];
  117.     init(1,0,size);
  118. 	int left, right;
  119.  
  120. 	for (int i = 0; i < opNumber; i++) {
  121.         int app;
  122.         //cout << endl<<endl<<endl;
  123. 		cin >> app >> left >> right;
  124.         if (app == 1)
  125.             cout << getSum(1, 0, size, left - 1, right) << endl;
  126.         else {
  127.             cin >> app;
  128.             add(1,0,size, left-1,right, app);
  129.         }
  130. 	}
  131.  
  132.  
  133.     return 0;
  134. }
  135.  
  136.  
Success #stdin #stdout 0s 3468KB
comments (?)
stdin
copy 
7 9
9 0 8 0 0 0 0
1 1 3
2 1 3 1
1 3 7
2 3 7 1
1 1 3
2 1 3 1
1 3 7
2 3 7 1
1 1 3
stdout
copy 
17
9
1
5
5
https://ideone.com/1vuNAm
5 7
1 2 3 4 5
1 1 5
1 2 4
0 1 5 3
1 1 5
0 2 4 1
1 1 5
1 2 4
language:
C++14 (clang 8.0)
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!