fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define SET 1
  3. #define FLIP 2
  4. #define N (1024*1024+1)
  5. #define M 101
  6. int n, T, m, nQuery;
  7. int cStr[M];
  8. int lStr[M];
  9. int t[2 * N];
  10. int setTo[N];
  11. int mode[N];
  12. int tsize[2 * N];
  13. char str[M][M];
  14.  
  15. void build()
  16. {
  17. 	for (int i = n; i < 2 * n; i++)
  18. 		tsize[i] = 1;
  19. 	for (int i = n - 1; i > 0; i--)
  20. 	{
  21. 		tsize[i] = tsize[i << 1] + tsize[i << 1 | 1];
  22. 		mode[i] = setTo[i] = 0;
  23. 		t[i] = t[i << 1] + t[i << 1 | 1];
  24. 	}
  25. 	mode[0]=setTo[0]=t[0]=tsize[0]=0;
  26. }
  27.  
  28. void apply (int i, int modo, int val)
  29. {
  30. 	if(i==0) return;
  31. 	if (modo == SET)
  32. 	{
  33. 		t[i] = val * tsize[i];
  34. 		if(i<n){
  35. 			setTo[i] = val;
  36. 			mode[i] = SET;
  37. 		}
  38. 	}
  39. 	else if (modo == FLIP)
  40. 	{
  41. 		t[i] = tsize[i] - t[i];
  42. 		if(i<n){
  43. 			if(mode[i]==SET) setTo[i]=!setTo[i];
  44. 			else if(mode[i]==FLIP) mode[i]=0;
  45. 			else mode[i] = FLIP;
  46. 		}
  47. 	}
  48. }
  49. void pull (int i)
  50. {
  51. 	while (i >>= 1)
  52. 	{
  53. 		if (mode[i] == 0)
  54. 			t[i] = t[i << 1] + t[i << 1 | 1];
  55. 		else if (mode[i] == SET)
  56. 			t[i] = setTo[i] * tsize[i];
  57. 		else if (mode[i] == FLIP)
  58. 			t[i] = tsize[i] - t[i << 1] - t[i << 1 | 1];
  59. 	}
  60. }
  61. void push (int i)
  62. {
  63. 	for (int s = 32; s >0 ; s--)
  64. 	{
  65. 		int p = i >> s;
  66. 		if(p==0) continue;
  67. 		if (mode[p] != 0) 
  68. 		{
  69. 			apply(p << 1, mode[p], setTo[p]);
  70. 			apply(p << 1 | 1, mode[p], setTo[p]);
  71. 			setTo[p] = mode[p] = 0;
  72. 		}
  73. 	}
  74. }
  75.  
  76. void update (int modo, int l, int r, int val)
  77. {
  78. 	int l0 = l + n, r0 = r + n;
  79. 	push(l0);
  80. 	push(r0);
  81. 	for (l += n, r += n; l <= r; l>>=1, r>>=1)
  82. 	{
  83. 		if (  l & 1 ) apply(l++, modo, val);
  84. 		if (!(r & 1)) apply(r--, modo, val);
  85. 	}
  86. 	pull(l0);
  87. 	pull(r0);
  88. }
  89.  
  90. int query (int l, int r)
  91. {
  92. 	int res = 0;
  93. 	push(l + n), push(r + n);
  94. 	for (l += n, r += n; l <= r; l>>=1, r>>=1)
  95. 	{
  96. 		if (  l & 1 ) res += t[l++];
  97. 		if (!(r & 1)) res += t[r--];
  98. 	}
  99. 	return res;
  100. }
  101. int main()
  102. {
  103. 	scanf("%d", &T);
  104. 	for (int z = 1; z <= T; z++)
  105. 	{
  106. 		scanf("%d", &m);
  107. 		n = 0;
  108. 		for (int i = 0; i < m; i++)
  109. 		{
  110. 			scanf("%d %s", &cStr[i], &str[i]);
  111. 			lStr[i] = strlen(str[i]);
  112. 			n+=lStr[i]*cStr[i];
  113. 		}
  114. 		for (int i = 0,pos=0; i < m; i++)
  115. 			for (int j = 0; j < cStr[i]; j++)
  116. 				for (int k = 0; k < lStr[i]; k++)
  117. 					t[n+pos++] = str[i][k] - '0';
  118. 		build();
  119. 		printf("Case %d:\n", z);
  120. 		scanf("%d", &nQuery);
  121. 		int nQuestion = 1;
  122. 		for (int i = 0; i < nQuery; i++)
  123. 		{
  124. 			char c[32];
  125. 			int l, r;
  126. 			scanf("%s %d %d", &c, &l, &r);
  127. 			switch (c[0])
  128. 			{
  129. 			case 'F':
  130. 				update(SET, l, r, 1);
  131. 				break;
  132. 			case 'E':
  133. 				update(SET, l, r, 0);
  134. 				break;
  135. 			case 'I':
  136. 				update(FLIP, l, r, 0);
  137. 				break;	
  138. 			case 'S':
  139. 				printf("Q%d: %d\n", nQuestion++, query(l, r));
  140. 				break;
  141. 			}
  142. 		}
  143.  
  144. 	}
  145. }
Success #stdin #stdout 0s 28000KB
comments (?)
stdin
copy 
2
2
5
10
2
1000
5
F 0 17
I 0 5
S 1 10
E 4 9
S 2 10
3
3
1
4
0
2
0
2
I 0 2
S 0 8
stdout
copy 
Case 1:
Q1: 5
Q2: 1
Case 2:
Q1: 0
https://ideone.com/3gAYS2
language:
C++ (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!