fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define _nhatminh  int main()
  3. #define ll long long
  4. #define str string
  5. #define fir first
  6. #define sec second
  7. #define ld long double
  8. #define pb push_back
  9. #define MOD 100000009
  10. #define freopen(name) if(fopen(name".INP","r")) {freopen (name".INP","r",stdin); freopen (name".OUT","w",stdout);}
  11. #define ALL(x) (x).begin(),(x).end()
  12. #define piint pair < int , int >
  13. #define piL pair < int , ll>
  14. #define pLL pair < ll , ll >
  15. #define TIME (1.0*clock()/CLOCKS_PER_SEC)
  16. using namespace std;
  17. const int Max_n=1e5;
  18. str cc123 ;
  19. int n , q;
  20. int s[4*Max_n+3] ;
  21. vector < int > chuan ( vector < int > a , vector < int > b ){
  22. 	if ( b == vector < int > {} ) return a ;
  23. 	else if ( a == vector < int > {}) return b ;
  24. 	else if ( a ==vector < int > {} && b == vector < int > {}) return {};
  25. 	vector < int > c ;
  26. 	c = a ;
  27. 	int ktra = c.back() ;
  28. 	int i = 0 ;
  29. 	for (i = 0 ; i < b.size() ; i ++ ) {
  30. 		if ( ktra != b[i] ) break ;  
  31. 	}
  32. 	for (int j = i ; j < b.size() ; j ++ )
  33. 		c.pb(b[j]) ;
  34. 	return c ;
  35. }
  36.  
  37. bool check_sub2 = 1 , check_sub3 = 1 ;
  38. struct sacso1{
  39. 	char wt ; 
  40. 	int l , r ; 
  41. };
  42. sacso1 a[Max_n+3] ;
  43. vector < int > mot[4*Max_n+3] ;
  44. int g[4*Max_n+3] , lazy[4*Max_n+3];
  45. void build_sub1 ( int id , int l , int r ){
  46. 	if ( l == r ) {
  47. 		mot[id].pb(s[l]) ;
  48. 		g[id] = mot[id].size() ;
  49. 		return ;
  50. 	}
  51. 	int m = ( l + r ) >> 1;
  52. 	build_sub1 ( id * 2 , l , m ) ;
  53. 	build_sub1 ( id * 2 + 1 , m + 1 , r  );
  54. 	vector < int > c_id2 = mot[id*2];
  55. 	vector < int > c_id21 = mot[id*2+1] ;
  56. 	mot[id] = chuan ( c_id2 , c_id21 ) ;
  57. 	g[id] = mot[id].size() ;
  58. }
  59. void fix_sub1 ( int id , int l , int  r){
  60. 	if ( lazy[id] == 0 ) return ;
  61. 	mot[id].clear() ; 
  62. 	mot[id].pb(lazy[id]) ;
  63. 	if ( l == r) {
  64. 		lazy[id] = 0 ;
  65. 		return ;
  66. 	} 
  67. 	if ( l != r ){
  68. 		lazy[id*2] = lazy[id*2+1] = lazy[id] ;
  69. 	}
  70. 	lazy[id] = 0 ;
  71. }
  72. void update ( int id , int l , int r , int u , int v , int x ){
  73. 	fix_sub1(id , l , r );
  74. 	if ( u > r || v < l ) return ;
  75. 	if ( u <= l && r <= v ){
  76. 		lazy[id] = x ;
  77. 		fix_sub1(id , l , r );
  78. 		return ;
  79. 	}
  80. 	int m = ( l + r ) >> 1 ;
  81. 	update ( id * 2 , l , m , u , v , x);
  82. 	update ( id * 2 + 1 , m + 1 , r , u , v , x );
  83. 	vector < int > c_id2 = mot[id*2];
  84. 	vector < int > c_id21 = mot[id*2+1] ;
  85. 	mot[id] = chuan ( c_id2 , c_id21 ) ;
  86. 	g[id] = mot[id].size() ;
  87. }
  88. vector < int >  get ( int id , int l , int r , int u , int v ){
  89. 	fix_sub1 ( id , l , r );
  90. 	if ( u > r || v < l ) return {} ;
  91. 	if ( u <= l && r <= v ){
  92. 		return mot[id] ;
  93. 	}
  94. 	int m = ( l + r )>> 1; 
  95. 	vector < int > c_id2 = get(id*2 , l , m , u , v );
  96. 	vector < int > c_id21 = get(id * 2 + 1 , m + 1 , r , u , v ) ;
  97. 	return chuan ( c_id2 , c_id21 ) ;
  98. }
  99. void sub1(){
  100. 	build_sub1( 1 , 1 , n );
  101. 	for (int i = 1 ; i <= q ; i ++ ){
  102. 		if ( a[i].wt == 'g'){
  103. 			vector < int > c = get ( 1 , 1 , n , a[i].l , a[i].r);
  104. 			cout << c.size() << '\n';
  105. 		}
  106. 		else update(1 ,1  , n , a[i].l , a[i].r , a[i].wt );
  107. 	}
  108. }
  109. pair < ll , ll > hai[Max_n+3];
  110. void sub2() {
  111. 	for (int i = 1 ; i <= n ; i ++ )
  112. 	{
  113. 		hai[i] = hai[i-1];
  114. 		if (s[i] != s[i-1]) {
  115. 			hai[i].sec+=1;
  116. 			hai[i].fir = i - 1;
  117. 		}
  118. 	}
  119. 	for (int i = 1 ; i <= q ; i ++ ){
  120. 		cout << hai[a[i].r].sec - hai[hai[a[i].l].fir].sec << '\n';
  121. 	}
  122. }
  123. int back_3[4*Max_n+4] , front_3[4*Max_n+3] ;
  124. int lazy_3[4*Max_n+3] ;
  125. void build_sub3( int id , int l , int r ){
  126. 	if ( l == r){
  127. 		front_3[id] = back_3[id] = s[l] ;
  128. 		g[id] = 1 ;
  129. 		return; 
  130. 	}
  131. 	int m = ( l + r ) >> 1;
  132. 	build_sub3 (id * 2 , l , m );
  133. 	build_sub3 (id * 2 + 1 , m + 1 , r);
  134. 	if (front_3[id*2+1] != back_3[id*2]){
  135. 		g[id] = g[id*2] + g[id*2 + 1 ]; 
  136. 	}
  137. 	else {
  138. 		g[id] = g[id*2] + g[id*2 + 1] - 1 ;
  139. 	}
  140. 	front_3[id] = front_3[id*2] ;
  141. 	back_3[id] = back_3[id*2+1] ;
  142. }
  143. void fix_sub3 ( int id , int l , int  r){
  144. 	if ( lazy_3[id] == 0 ) return ;
  145. 	front_3[id] = back_3[id] = lazy_3[id];
  146. 	g[id] = 1  ;
  147. 	//mot[id].pb(lazy[id]) ;
  148. 	if ( l == r) {
  149. 		lazy_3[id] = 0 ;
  150. 		return ;
  151. 	} 
  152. 	if ( l != r ){
  153. 		lazy_3[id*2] = lazy_3[id*2+1] = lazy_3[id] ;
  154. 	}
  155. 	lazy_3[id] = 0 ;
  156. }
  157. void update_sub3( int id , int l , int r , int u , int v , int x ){
  158. 	fix_sub3(id , l , r );
  159. 	if ( u > r || v < l ) return ;
  160. 	if ( u <= l && r <= v ){
  161. 		lazy_3[id] = x ;
  162. 		fix_sub3(id , l , r );
  163. 		return ;
  164. 	}
  165. 	int m = ( l + r ) >> 1 ;
  166. 	update_sub3( id * 2 , l , m , u , v , x);
  167. 	update_sub3( id * 2 + 1 , m + 1 , r , u , v , x );
  168. 	if (front_3[id*2+1] != back_3[id*2]){
  169. 		g[id] = g[id*2] + g[id*2 + 1 ]; 
  170. 	}
  171. 	else {
  172. 		g[id] = g[id*2] + g[id*2 + 1] - 1 ;
  173. 	}
  174. 	front_3[id] = front_3[id*2] ;
  175. 	back_3[id] = back_3[id*2+1] ;
  176. }
  177. struct sacso{
  178. 	int b , f , val ;
  179. } ;
  180. sacso get_3( int id , int l , int r , int u , int v ){
  181. 	fix_sub3 ( id , l , r );
  182. 	if ( u > r || v < l ) return { 0 , 0 , 0 } ;
  183. 	if ( u <= l && r <= v ){
  184. 		sacso c ;
  185. 		c.b = back_3[id] ;
  186. 		c.f = front_3[id] ;
  187. 		c.val = g[id] ; 
  188. 		return c ;
  189. 	}
  190. 	int m = ( l + r )>> 1; 
  191. 	sacso c_id2 = get_3(id*2 , l , m , u , v );
  192. 	sacso c_id21 = get_3(id * 2 + 1 , m + 1 , r , u , v ) ;
  193. 	sacso ans ;
  194. 	if ( c_id2.val == 0 &&  c_id21.val == 0 ) return { 0 , 0 , 0 } ;
  195. 	if ( c_id2.val == 0 ) return c_id21 ;
  196. 	else if ( c_id21.val == 0 ) return c_id2 ;
  197. 	if (c_id2.b == c_id21.f){
  198. 		ans.val = c_id2.val + c_id21.val -1 ;
  199. 	}
  200. 	else ans.val = c_id2.val + c_id21.val ;
  201. 	ans.f = c_id2.f;
  202. 	ans.b = c_id21.b ;
  203. 	return ans ;
  204. }
  205. void sub3() {
  206. 	build_sub3( 1 , 1 , n );
  207. 	for (int i = 1 ; i <= q ; i ++ ){
  208. 		if ( a[i].wt == 'g'){
  209. 			sacso c = get_3( 1 , 1 , n , a[i].l , a[i].r);
  210. 			cout << c.val << '\n';
  211. 		}
  212. 		else update_sub3(1 ,1  , n , a[i].l , a[i].r , a[i].wt );
  213. 	}
  214. }
  215. void solve(){
  216. 	cin >> n >> q >> cc123 ;
  217. 	for (int i = 1 ; i <= n ; i ++ )
  218. 		s[i] = cc123[i-1] ;
  219. 	for (int i = 1 ; i <= q ; i ++){
  220. 		str wtc ; cin >> wtc ;
  221. 		a[i].wt = wtc[0] ;
  222. 		cin >> a[i].l >> a[i].r ;
  223. 		//if ( a[i].wt == 'g') check_sub2 = 0 ;
  224. 		if (a[i].wt == 'c') {
  225. 			check_sub2 = 0 ;
  226. 			cin >> a[i].wt ;
  227. 		}
  228. 	}
  229. 	if (check_sub2) sub2();
  230.  	else if ( n <= 1000 )sub1() ;
  231.  	else sub3() ;
  232. }
  233. _nhatminh{
  234. freopen("sacso");
  235. ios_base::sync_with_stdio(0);
  236. cin.tie(0); cout.tie(0);
  237. solve();
  238. cerr << '\n' << "Time elapsed " << TIME << "s.\n";
  239. return (0);
  240. }
Success #stdin #stdout #stderr 0.01s 18284KB
comments (?)
stdin
copy 
11 5
GGBBBGGYRRR
get 1 11
get 3 9
get 4 7
change 4 8 B
get 1 11
stdout
copy 
5
4
2
3
stderr
copy 
Time elapsed 0.00831s.
https://ideone.com/1x6FwO
language:
C++14 (gcc 8.3)
created:
7 days 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!