fork(4) download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <stdio.h>
  4. using namespace std;
  5. typedef vector<int> vi;
  6. class segTree{
  7. public:
  8.     segTree(vi &main,int sz){markers.assign(4*sz+4,0); lazy.assign(4*sz+4,0); st.assign(4*sz+4,0); A=main; flags.assign(4*sz+4,1); buildTree(1,0,sz-1);}
  9. 	vi st,A,flags,lazy;
  10. 	vector<bool> markers;
  11. 	int buildTree(int,int,int);
  12. 	int query(int,int,int,int,int);
  13. 	int update(int,int,int,int,int,int);
  14. 	int left(int p){return (p<<1);}
  15. 	int right(int p){ return (p<<1)+1;}
  16.  
  17. };
  18. int main()
  19. {
  20.  
  21. /*	vi A({1,1,1,0,0,0,0,0,0});
  22.  
  23. 	segTree st(A,A.size());
  24. 	st.update(1,0,A.size()-1,0,2,-1);
  25. 	//st.update(1,0,A.size()-1,0,1,-1);
  26. 	cout<<st.query(1,0,A.size()-1,0,2);
  27. */
  28. 	int t;
  29. 	cin>>t;
  30. 	for(int test=1;test<=t;++test)
  31. 	{	
  32. 		int m;
  33. 		cin>>m;
  34. 		string s;
  35. 		while(m--)
  36. 		{
  37. 			int T;
  38. 			cin>>T;
  39. 			string temp;
  40. 			cin>>temp;
  41. 			while(T--)
  42. 				s.append(temp);
  43. 		}
  44. 		int n = s.size();
  45. 		vi temp(n,0);
  46. 		for(int i=0;i<n;++i)
  47. 			temp[i] = s[i] - 48;
  48. 		segTree st(temp,n);
  49.  
  50. 		int q;
  51. 		cin>>q;
  52. 		int asks = 1;
  53. 		printf("Case %d:\n",test);
  54. 		while(q--)
  55. 		{
  56. 			char c;
  57. 			int i,j;
  58. 			cin>>c>>i>>j;
  59. 			if(c=='F')
  60. 			{
  61. 				st.update(1,0,n-1,i,j,1);
  62.  
  63. 			}
  64. 			else if(c=='E')
  65. 			{
  66. 				st.update(1,0,n-1,i,j,0);
  67. 			}
  68. 			else if(c == 'I')
  69. 			{
  70. 				st.update(1,0,n-1,i,j,-1);
  71. 			}
  72. 			else if(c=='S')
  73. 				printf("Q%d: %d\n",asks++,st.query(1,0,n-1,i,j));
  74.  
  75. 		}
  76.  
  77.  
  78.  
  79.  
  80.  
  81.  
  82.  
  83. 	}	
  84.  
  85.  
  86. }
  87.  
  88.  
  89.  
  90. int segTree::buildTree(int p,int L,int R)
  91. {
  92. 	if(L==R)
  93. 	{ 	
  94. 		st[p] = A[L];
  95. 		flags[p] = 1; 
  96. 		return st[p]; 
  97. 	}
  98.  
  99. 	int a = buildTree(left(p),L,(L+R)/2) , b = buildTree(right(p),(L+R)/2+1,R);
  100. 	st[p] = a+b;
  101. 	flags[p] = 1;
  102. 	return st[p];
  103.  
  104. }
  105.  
  106. int segTree::query(int p,int L,int R,int i,int j)
  107. {
  108.  
  109. 	if(j<L||i>R) return -1;
  110. 	if(markers[p])
  111. 	{
  112. 		if(lazy[p] == 1)
  113. 		{
  114. 			st[p] = R - L + 1;
  115. 			if(L!=R){
  116. 			lazy[left(p)] = 1;
  117. 			lazy[right(p)] = 1;
  118. 			markers[left(p)] = 1;
  119. 			markers[right(p)] = 1;
  120. 		}
  121. 		}
  122. 		else if(lazy[p] == 0)
  123. 		{
  124. 			st[p] = 0;
  125. 		if(L!=R)
  126. 		{
  127. 			lazy[left(p)] = 0;
  128. 			lazy[right(p)] = 0;
  129. 			markers[left(p)] = 1;
  130. 			markers[right(p)] = 1;
  131. 		}
  132. 		}
  133. 		else if(lazy[p] == -1)
  134. 		{
  135. 			st[p] = (R-L+1) - st[p];
  136. 			if(L!=R)
  137. 			{
  138. 				if(!markers[left(p)])
  139. 				{
  140. 					lazy[left(p)] = -1;
  141. 					markers[left(p)] = 1;
  142. 				}
  143. 				else
  144. 				{
  145. 					if(lazy[left(p)] == 1)
  146. 						lazy[left(p)] = 0;
  147. 					else if(lazy[left(p)]== 0)
  148. 						lazy[left(p)] = 1;
  149. 					else if(lazy[left(p)] == -1)
  150. 						markers[left(p)] = 0; 
  151.  
  152. 				}
  153. 				if(!markers[right(p)])
  154. 				{
  155. 					lazy[right(p)] = -1;
  156. 					markers[right(p)] = 1;
  157. 				}
  158. 				else
  159. 				{
  160. 					if(lazy[right(p)] == 1)
  161. 						lazy[right(p)] = 0;
  162. 					else if(lazy[right(p)]== 0)
  163. 						lazy[right(p)] = 1;
  164. 					else if(lazy[right(p)] == -1)
  165. 						markers[right(p)] = 0; 
  166.  
  167. 				}
  168.  
  169. 			}	
  170.  
  171.  
  172. 		}
  173.  
  174.  
  175. 	}
  176. 	markers[p] = 0;
  177. 	if(j<L||i>R) return -1;
  178. 	if(L >= i && R <= j)
  179. 	{ 	
  180. 		return st[p]; 
  181. 	}
  182. 	int a = query(left(p),L,(L+R)/2,i,j);
  183. 	int b = query(right(p),(L+R)/2+1,R,i,j);
  184. 	if(a==-1)
  185. 		return b;
  186. 	if(b==-1)
  187. 		return a;	
  188.  
  189. 	return a+b;
  190.  
  191. }
  192.  
  193.  
  194. int segTree::update(int p,int L,int R,int i,int j,int v)
  195. {
  196. 	if(markers[p])
  197. 	{
  198. 		if(lazy[p] == 1)
  199. 		{
  200. 			st[p] = R - L + 1;
  201. 			if(L!=R){
  202. 			lazy[left(p)] = 1;
  203. 			lazy[right(p)] = 1;
  204. 			markers[left(p)] = 1;
  205. 			markers[right(p)] = 1;
  206. 		}
  207. 		}
  208. 		else if(lazy[p] == 0)
  209. 		{
  210. 			st[p] = 0;
  211. 		if(L!=R)
  212. 		{
  213. 			lazy[left(p)] = 0;
  214. 			lazy[right(p)] = 0;
  215. 			markers[left(p)] = 1;
  216. 			markers[right(p)] = 1;
  217. 		}
  218. 		}
  219. 		else if(lazy[p] == -1)
  220. 		{
  221. 			st[p] = (R-L+1) - st[p];
  222. 			if(L!=R)
  223. 			{
  224. 				if(!markers[left(p)])
  225. 				{
  226. 					lazy[left(p)] = -1;
  227. 					markers[left(p)] = 1;
  228. 				}
  229. 				else
  230. 				{
  231. 					if(lazy[left(p)] == 1)
  232. 						lazy[left(p)] = 0;
  233. 					else if(lazy[left(p)]== 0)
  234. 						lazy[left(p)] = 1;
  235. 					else if(lazy[left(p)] == -1)
  236. 						markers[left(p)] = 0; 
  237.  
  238. 				}
  239. 				if(!markers[right(p)])
  240. 				{
  241. 					lazy[right(p)] = -1;
  242. 					markers[right(p)] = 1;
  243. 				}
  244. 				else
  245. 				{
  246. 					if(lazy[right(p)] == 1)
  247. 						lazy[right(p)] = 0;
  248. 					else if(lazy[right(p)]== 0)
  249. 						lazy[right(p)] = 1;
  250. 					else if(lazy[right(p)] == -1)
  251. 						markers[right(p)] = 0; 
  252.  
  253. 				}
  254.  
  255. 			}	
  256.  
  257.  
  258. 		}
  259.  
  260.  
  261. 	}
  262. 	markers[p] = 0;
  263. 	if(L >= i && R <= j)
  264. 	{
  265. 		if(v==1)
  266. 		{
  267. 			st[p] = R-L+1;
  268. 		if(L!=R){
  269. 			lazy[left(p)] = 1;
  270. 			lazy[right(p)] = 1;
  271. 			markers[left(p)] = 1;
  272. 			markers[right(p)] = 1;
  273. 		}
  274. 		}
  275. 		else if(v == 0)
  276. 		{
  277. 			st[p] = 0;
  278. 		if(L!=R){
  279. 			lazy[left(p)] = 0;
  280. 			lazy[right(p)] = 0;
  281. 			markers[left(p)] = 1;
  282. 			markers[right(p)] = 1;
  283. 		}
  284. 		}
  285. 		else if(v == -1)
  286. 		{
  287. 			st[p] = (R - L + 1) - st[p];
  288. 			if(L!=R)
  289. 			{
  290. 				if(!markers[left(p)])
  291. 				{
  292. 					lazy[left(p)] = -1;
  293. 					markers[left(p)] = 1;
  294. 				}
  295. 				else
  296. 				{
  297. 					if(lazy[left(p)] == 1)
  298. 						lazy[left(p)] = 0;
  299. 					else if(lazy[left(p)]== 0)
  300. 						lazy[left(p)] = 1;
  301. 					else if(lazy[left(p)] == -1)
  302. 						markers[left(p)] = 0; 
  303.  
  304. 				}
  305. 				if(!markers[right(p)])
  306. 				{
  307. 					lazy[right(p)] = -1;
  308. 					markers[right(p)] = 1;
  309. 				}
  310. 				else
  311. 				{
  312. 					if(lazy[right(p)] == 1)
  313. 						lazy[right(p)] = 0;
  314. 					else if(lazy[right(p)]== 0)
  315. 						lazy[right(p)] = 1;
  316. 					else if(lazy[right(p)] == -1)
  317. 						markers[right(p)] = 0; 
  318.  
  319. 				}
  320.  
  321. 			}
  322.  
  323. 		}
  324.  
  325. 		return st[p];
  326. 	}
  327. 	if(L==R)
  328. 		return st[p];
  329. 	int a = update(left(p),L,(L+R)/2,i,j,v);
  330. 	int b = update(right(p),(L+R)/2+1,R,i,j,v);
  331. 	st[p] = a+b;
  332. 	return a+b;
  333. }
  334.  
  335.  
  336.  
  337.  
Success #stdin #stdout 0s 3348KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/EKNaRN
language:
C++ (gcc 8.3)
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!