fork(1) download
copy 
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <string>
  4. #include <cstring>
  5.  
  6. using namespace std;
  7.  
  8. int T, m, t, q, a, b, n, o, cnt, res;
  9. string str, s;
  10. char ch;
  11. int segtree[2100000], operation[2100000];
  12. string op = "NEFI";
  13.  
  14. void lazy_propagation (int v, int l, int r)
  15. {
  16. 	if (operation[v])
  17. 	{
  18. 		if (operation[v] == 1)
  19. 			segtree[v] = 0, operation[2*v] = operation[2*v+1] = 1;
  20. 		else if (operation[v] == 2)
  21. 			segtree[v] = r-l+1, operation[2*v] = operation[2*v+1] = 2;
  22. 		else
  23. 		{
  24. 			segtree[v] = (r-l+1) - segtree[v];
  25. 			operation[2*v] = 3-operation[2*v], operation[2*v+1] = 3-operation[2*v+1];
  26. 		}
  27. 		operation[v] = 0;
  28. 	}
  29. }
  30.  
  31. void create (int v, int l, int r)
  32. {
  33. 	if (l == r)
  34. 		segtree[v] = str[l] - '0';
  35. 	else
  36. 	{
  37. 		create(2*v, l, (l+r)/2);
  38. 		create(2*v+1, (l+r)/2+1, r);
  39. 		segtree[v] = segtree[2*v] + segtree[2*v+1];
  40. 	}
  41. }
  42.  
  43. void update (int v, int l, int r)
  44. {
  45. 	lazy_propagation(v, l, r);
  46. 	if (l > b || r < a)		return;
  47. 	if (a <= l && r <= b)
  48. 	{
  49. 		operation[v] = o;
  50. 		lazy_propagation(v, l, r);
  51. 		return;
  52. 	}
  53. 	update(2*v, l, (l+r)/2);
  54. 	update(2*v+1, (l+r)/2+1, r);
  55. 	segtree[v] = segtree[2*v] + segtree[2*v+1];
  56. }
  57.  
  58. int query (int v, int l, int r)
  59. {
  60. 	lazy_propagation(v, l, r);
  61. 	if (l > b || r < a)		return 0;
  62. 	if (a <= l && r <= b)	return segtree[v];
  63. 	return query(2*v, l, (l+r)/2) + query(2*v+1, (l+r)/2+1, r);
  64. }
  65.  
  66. int main ()
  67. {
  68. 	scanf("%d", &T);
  69. 	for (int I = 1; I <= T && scanf("%d", &m) == 1; ++I)
  70. 	{
  71. 		printf("Case %d:\n", I);
  72. 		str = "";
  73. 		for (int J = 0; J < m; ++J)
  74. 		{
  75. 			scanf("%d", &t);
  76. 			cin >> s;
  77. 			while (t--)	str += s;
  78. 		}
  79. 		n = str.length();
  80. 		create(1, 0, n-1);
  81. 		memset(operation, 0, sizeof operation);
  82. 		scanf("%d", &q);
  83. 		cnt = 0;
  84. 		for (int J = 1; J <= q; ++J)
  85. 		{
  86. 			cin >> ch >> a >> b;
  87. 			if (ch == 'S')
  88. 			{
  89. 				res = query(1, 0, n-1);
  90. 				printf("Q%d: %d\n", ++cnt, res);
  91. 			}
  92. 			else
  93. 			{
  94. 				if (ch == 'E')
  95. 					o = 1;
  96. 				else if (ch == 'F')
  97. 					o = 2;
  98. 				else
  99. 					o = 3;
  100. 				update(1, 0, n-1);
  101. 			}
  102. 		}
  103. 	}
  104. 	return 0;
  105. }
Success #stdin #stdout 0s 19840KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/4NNbV5
language:
C++ (gcc 8.3)
created:
11 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!