fork(1) download
copy 
  1. #include <bits/stdc++.h> 
  2. using namespace std ;
  3.  
  4. #define MAXN 100005 
  5. #define mod 3
  6. #define MAXM 500 
  7. #define LL long long int 
  8.  
  9. int N,Q,C,X,Y,BS,NB,BLOCK[MAXM][3],LAZY[MAXM],F[MAXM],ORG[MAXN],BLOCKEND[MAXM],BLOCKSTART[MAXM],A[MAXN];
  10. char str[MAXN] ;
  11. LL ANS[3],ans,TEMP[3];
  12.  
  13. int getblock(int idx){
  14. 	return ((idx-1)/BS + 1) ;
  15. }
  16.  
  17.  
  18. void buildSQRT(){
  19. 	for(int i=1;i<=N;i++){
  20. 		int block = getblock(i) ;
  21. 		BLOCK[block][A[i]] ++ ;
  22. 		if(BLOCKSTART[block] == 0)
  23. 			BLOCKSTART[block] = i ;
  24. 		BLOCKEND[block] = i ;
  25. 	}
  26. }
  27.  
  28.  
  29.  
  30. void update(int idx,int val){
  31.  
  32.  
  33. 	val = val%mod ;
  34. 	val = val - ORG[idx] ;
  35. 	val += mod ;
  36. 	val %= mod ;
  37. 	ORG[idx] += val ;
  38. 	ORG[idx] %= mod ;
  39.  
  40. 	int block = getblock(idx) ;
  41.  
  42. 	if(F[block]){
  43. 		for(int i=BLOCKSTART[block];i<=BLOCKEND[block];i++){
  44. 			A[i] = A[i]+LAZY[block] ;
  45. 			A[i] %= mod ;
  46. 		}
  47. 		F[block] = 0;
  48. 		LAZY[block] = 0;
  49. 	}
  50.  
  51. 	for(int i=idx;i<=BLOCKEND[block];i++){
  52. 		BLOCK[block][A[i]] -- ;
  53. 		A[i] += val ;
  54. 		A[i] %= mod ;
  55. 		BLOCK[block][A[i]] ++ ;
  56. 	}
  57.  
  58. 	for(int i=block+1;i<=NB;i++){
  59. 		F[i] = 1;
  60. 		LAZY[i] += val ;
  61. 		LAZY[i] %= mod ;
  62. 		TEMP[0] = TEMP[1] = TEMP[2] = 0 ;	
  63. 		TEMP[(val+0)%mod] = BLOCK[i][0] ;
  64. 		TEMP[(val+1)%mod] = BLOCK[i][1] ;
  65. 		TEMP[(val+2)%mod] = BLOCK[i][2] ;						
  66. 		BLOCK[i][0] = TEMP[0] ;
  67. 		BLOCK[i][1] = TEMP[1] ;
  68. 		BLOCK[i][2] = TEMP[2] ;	
  69. 	}		
  70.  
  71. }
  72.  
  73. void query(int L,int R){
  74.  
  75.  
  76. 	int block = getblock(L) ;
  77. 	ANS[0] = ANS[1] = ANS[2] = 0;
  78.  
  79. 	if(F[block]){
  80. 		for(int i=BLOCKSTART[block];i<=BLOCKEND[block];i++){
  81. 			A[i] = A[i]+LAZY[block] ;
  82. 			A[i] %= mod ;
  83. 		}
  84. 		F[block] = 0;
  85. 		LAZY[block] = 0;
  86. 	}
  87.  
  88. 	for(;L<=min(BLOCKEND[block],R);L++){
  89. 		ANS[A[L]] ++ ;
  90. 	}
  91. 	block = getblock(R) ;
  92. 	if(F[block]){
  93. 		for(int i=BLOCKSTART[block];i<=BLOCKEND[block];i++){
  94. 			A[i] = A[i]+LAZY[block] ;
  95. 			A[i] %= mod ;
  96. 		}
  97. 		F[block] = 0;
  98. 		LAZY[block] = 0;
  99. 	}
  100.  
  101. 	for(;R>=max(BLOCKSTART[block],L);R--){
  102. 		ANS[A[R]] ++ ;
  103. 	}
  104. 	if(L<=R){	
  105. 		for(int i=getblock(L);i<=getblock(R);i++){
  106. 			ANS[0] += BLOCK[i][0] ;
  107. 			ANS[1] += BLOCK[i][1] ;
  108. 			ANS[2] += BLOCK[i][2] ;
  109. 		}
  110. 	}
  111. }
  112. int main(){
  113.  
  114. 	scanf("%d%d",&N,&Q) ;
  115. 	scanf("%s",str+1) ;
  116. 	for(int i=1;i<=N;i++){
  117. 		A[i] = str[i] - '0' ;
  118. 		A[i] += A[i-1] ;A[i] %= mod ;
  119. 		ORG[i] = str[i] -'0' ;ORG[i] %= mod ;
  120. 	}
  121.  
  122. 	BS = sqrt(N) ;
  123. 	NB = (N/BS) + bool(N%BS) ;
  124.  
  125. 	buildSQRT() ;
  126. 	while(Q--){
  127.  
  128. 		scanf("%d%d%d",&C,&X,&Y) ;
  129. 		if(C == 1){
  130. 			update(X,Y) ;
  131. 		}else{
  132. 			query(X,Y) ;
  133. 			int val = (A[X-1]+LAZY[(X == 1 ? 0 : getblock(X-1))]);
  134. 			val %= mod ;
  135. 			TEMP[(0-val+mod)%mod] = ANS[0] ;
  136. 			TEMP[(1-val+mod)%mod] = ANS[1] ;
  137. 			TEMP[(2-val+mod)%mod] = ANS[2] ;
  138. 			ANS[0] = TEMP[0] ;
  139. 			ANS[1] = TEMP[1] ;
  140. 			ANS[2] = TEMP[2] ;
  141. 			ans = 0 ;
  142. 			ans += (ANS[0]*(ANS[0]+1)/2) ;
  143. 			ans += (ANS[1]*(ANS[1]-1)/2) ;
  144. 			ans += (ANS[2]*(ANS[2]-1)/2) ;				
  145. 			printf("%lld\n",ans ) ;
  146. 		}
  147. 	}		
  148. 	return 0;
  149. }
Success #stdin #stdout 0s 3996KB
comments (?)
stdin
copy 
5 3
01245
2 1 3
1 4 5
2 3 5
stdout
copy 
3
1
https://ideone.com/NMQlRR
language:
C++14 (gcc 8.3)
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!