fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. const int N = 1024001;
  4. int t, m, x, ln, q;
  5. char s[1024001], w[55], lazy[N * 4 + 2];
  6. int inter[N * 4 + 2];
  7. void build(int indx, int l, int r) {
  8. 	if (l > r)
  9. 		return;
  10. 	if (l == r) {
  11. 		inter[indx] = s[l] == '1';
  12. 		lazy[indx] = '.';
  13. 		return;
  14. 	}
  15. 	int mid = (l + r) / 2;
  16. 	build(indx * 2, l, mid);
  17. 	build(indx * 2 + 1, mid + 1, r);
  18. 	inter[indx] = inter[indx * 2] + inter[indx * 2 + 1];
  19. 	lazy[indx] = '.';
  20. }
  21. void update_child(int indx, int l, int r, char c) {
  22. 	if (c == 'F')
  23. 		inter[indx] = (r - l + 1);
  24. 	else if (c == 'E')
  25. 		inter[indx] = 0;
  26. 	else
  27. 		inter[indx] = (r - l + 1 - inter[indx]);
  28. 	if (l != r) {
  29. 		if (lazy[indx] == 'F' || lazy[indx] == 'E')
  30. 			lazy[indx * 2] = lazy[indx * 2 + 1] = lazy[indx];
  31. 		else
  32. 			lazy[indx * 2] = (lazy[indx * 2] == 'F') ? 'E' :
  33. 								(lazy[indx * 2] == 'E') ? 'F' :
  34. 								(lazy[indx * 2] == 'I') ? '.' : 'I', lazy[indx
  35. 					* 2 + 1] = (lazy[indx * 2 + 1] == 'F') ? 'E' :
  36. 								(lazy[indx * 2 + 1] == 'E') ? 'F' :
  37. 								(lazy[indx * 2 + 1] == 'I') ? '.' : 'I';
  38. 	}
  39. 	lazy[indx] = '.';
  40. }
  41. int get(int indx, int l, int r, int a, int b) {
  42. 	if (lazy[indx] != '.')
  43. 		update_child(indx, l, r, lazy[indx]);
  44. 	if (a > r || b < l)
  45. 		return 0;
  46. 	if (a <= l && r <= b) {
  47. 		return inter[indx];
  48. 	}
  49. 	int mid = (l + r) / 2;
  50. 	return get(indx * 2, l, mid, a, b) + get(indx * 2 + 1, mid + 1, r, a, b);
  51. }
  52. void modify(int indx, int l, int r, int a, int b, char c) {
  53. 	if (lazy[indx] != '.')
  54. 		update_child(indx, l, r, lazy[indx]);
  55. 	if (a > r || b < l)
  56. 		return;
  57. 	if (a <= l && r <= b) {
  58. 		if (c == 'F')
  59. 			inter[indx] = (r - l + 1), lazy[indx * 2] = lazy[indx * 2 + 1] = 'F';
  60. 		else if (c == 'E')
  61. 			inter[indx] = 0, lazy[indx * 2] = lazy[indx * 2 + 1] = 'E';
  62. 		else {
  63. 			lazy[indx * 2] = (lazy[indx * 2] == 'F') ? 'E' :
  64. 								(lazy[indx * 2] == 'E') ? 'F' :
  65. 								(lazy[indx * 2] == 'I') ? '.' : 'I', lazy[indx
  66. 					* 2 + 1] = (lazy[indx * 2 + 1] == 'F') ? 'E' :
  67. 								(lazy[indx * 2 + 1] == 'E') ? 'F' :
  68. 								(lazy[indx * 2 + 1] == 'I') ? '.' : 'I';
  69. 			inter[indx] = (r - l + 1 - inter[indx]);
  70. 		}
  71. 		return;
  72. 	}
  73. 	int mid = (l + r) / 2;
  74. 	modify(indx * 2, l, mid, a, b, c);
  75. 	modify(indx * 2 + 1, mid + 1, r, a, b, c);
  76. 	inter[indx] = inter[indx * 2] + inter[indx * 2 + 1];
  77. }
  78. int main(int argc, char **argv) {
  79. #ifndef ONLINE_JUDGE
  80. 	freopen("a.in", "r", stdin);
  81. #endif
  82. 	int t;
  83. 	scanf("%d", &t);
  84. 	for (int cas = 1; cas <= t; ++cas) {
  85. 		printf("Case %d:\n", cas);
  86. 		scanf("%d", &m);
  87. 		strcpy(s, "");
  88. 		while (m--) {
  89. 			scanf("%d %s", &x, w);
  90. 			while (x--)
  91. 				strcat(s, w);
  92. 		}
  93. 		ln = strlen(s);
  94. 		build(1, 0, ln - 1);
  95. 		scanf("%d", &q);
  96. 		int que = 0, x, y;
  97. 		char c;
  98. 		while (q--) {
  99. 			scanf(" %c %d %d", &c, &x, &y);
  100. 			if (c == 'S')
  101. 				printf("Q%d: %d\n", ++que, get(1, 0, ln - 1, x, y));
  102. 			else
  103. 				modify(1, 0, ln - 1, x, y, c);
  104. 		}
  105. 	}
  106. 	return 0;
  107. }
  108.  
Success #stdin #stdout 0s 24104KB
comments (?)
stdin
copy 
1
1
64
110000011101011110011110110010001
345
F 951 1793
S 43 491
S 36 1431
I 1529 2065
I 516 946
S 344 1395
S 440 745
F 609 1598
F 410 1438
S 484 1211
I 956 1141
E 909 1447
E 1547 1793
I 1244 1500
I 334 398
E 807 1356
I 3 1616
S 586 1167
I 226 493
E 978 1562
E 71 1209
F 980 1808
S 401 661
F 490 1969
I 191 2108
E 82 1547
I 1550 1564
E 89 1374
I 379 1857
F 703 2006
S 760 1167
F 863 1837
E 137 1329
S 1819 2097
I 1397 1880
I 1159 1962
F 1414 1729
E 676 1867
E 422 1060
S 746 1189
I 1475 1950
I 162 1675
S 1813 2006
I 288 1862
I 603 1147
E 258 1173
S 1179 2051
F 752 1806
I 413 818
S 518 1629
E 581 992
E 1218 1748
I 1113 1794
F 1057 1465
S 91 2068
E 942 1193
E 261 1707
S 1013 1838
I 534 1490
S 1764 2009
S 24 542
E 242 297
I 134 2036
S 1045 1848
S 1137 1200
E 31 1827
I 601 1802
S 1426 1528
E 2009 2063
I 1299 1779
E 106 1803
S 2081 2101
F 187 1051
E 1133 2036
I 569 1188
E 24 904
S 673 1569
F 883 1583
S 780 1522
I 840 2080
I 138 182
S 3 108
I 67 1159
I 119 180
S 813 1216
S 838 1403
F 1511 1556
S 1047 1464
S 521 788
S 63 1425
I 1117 1608
I 1611 1927
E 678 1742
E 1729 1925
S 655 1094
E 385 770
F 1853 2005
S 281 1421
E 97 1704
I 160 1796
I 1342 1983
I 197 1221
F 631 1900
I 176 1581
F 188 2078
E 569 959
I 700 2010
F 802 982
E 574 706
I 322 1067
F 258 869
E 104 455
E 1014 1087
I 1327 1618
S 1293 2100
I 1500 1862
I 1413 1760
F 515 1220
S 400 1221
E 240 1789
S 1109 1227
S 1213 2071
I 179 2089
E 1862 1894
S 1233 1850
E 760 1303
I 604 1310
E 448 1888
I 240 633
I 1456 2030
S 489 1145
E 1169 1957
F 1210 1768
I 554 992
E 177 731
F 90 1001
F 199 1376
E 198 712
E 1409 1647
S 93 753
E 955 1306
I 814 1151
F 807 1887
F 1092 1425
I 46 109
S 263 851
S 847 1639
S 1512 1837
F 1436 2017
E 650 1593
S 436 1314
S 1075 1315
I 1090 2005
F 134 2097
E 181 1069
F 283 1096
F 499 1944
E 1042 1408
I 121 1313
S 737 2027
F 1229 2042
S 192 557
E 149 160
F 198 699
E 615 1332
E 640 1615
E 66 992
E 936 1108
I 606 1293
I 1776 2094
S 315 2024
F 470 1467
E 694 1886
F 1284 1457
F 24 816
S 593 728
I 1466 1721
I 124 609
F 189 1215
I 943 1632
S 878 1259
E 678 1417
S 37 517
E 919 1801
E 569 2063
I 251 1226
S 182 644
F 180 768
F 1022 1415
S 606 1831
I 117 1548
E 492 853
I 891 1465
S 1021 1874
F 1825 2034
I 28 1023
I 210 741
S 132 455
E 197 1870
S 1413 1653
S 1524 1770
F 215 847
S 912 1680
E 653 1494
I 639 1765
I 557 1663
E 356 575
F 553 1237
I 620 814
S 115 1089
E 116 1703
F 502 627
E 1414 2056
I 215 796
I 249 513
E 1070 2107
E 1645 1882
I 835 1931
F 323 1519
S 561 649
S 516 677
E 105 1369
F 1377 2022
F 1523 1592
I 1613 1841
F 295 1901
I 704 1671
E 1470 1554
F 740 1941
E 478 889
S 1058 1152
F 1071 1163
E 1137 1557
E 612 1345
S 114 1993
F 473 1043
S 1178 1228
E 600 946
I 1404 1499
F 181 1523
I 1398 2109
E 357 1260
S 1844 1978
S 1211 1693
E 1022 1157
S 152 209
E 1233 1444
E 278 1880
E 1841 1969
S 1317 1951
E 299 1314
I 526 1817
E 258 339
F 62 1951
E 397 925
I 847 1135
I 320 1898
E 153 2015
I 74 620
S 629 2026
E 213 884
S 425 2031
E 322 388
F 281 384
I 781 1385
E 1535 1692
E 1542 1901
I 1445 1599
E 1640 2065
S 647 1411
F 386 1595
S 740 2085
E 425 1619
E 645 706
S 1685 2091
S 1514 1539
I 480 1367
S 919 1918
E 447 1396
F 1013 1858
S 197 544
F 353 1001
E 144 572
S 258 1217
S 755 855
E 50 282
E 827 1038
F 697 1456
S 45 1271
I 1059 1104
S 1648 1667
F 1676 2084
F 117 1676
I 54 375
E 1185 1194
S 248 1245
I 171 890
S 787 1691
E 914 1603
F 754 2083
S 1619 1892
F 1115 1247
E 876 1403
F 216 930
I 67 246
S 316 1195
I 378 1206
E 389 2057
F 1160 1548
S 254 1977
I 35 1805
I 1214 1253
I 570 673
F 274 786
S 250 1096
S 179 1420
E 557 1724
I 150 1010
I 59 332
E 1428 2100
F 383 1858
I 999 1021
F 859 1736
I 1509 2074
I 212 1041
E 577 1632
S 556 1308
E 1523 1742
F 760 1855
E 1171 1327
S 100 1618
I 591 1084
I 1170 1451
F 912 1827
F 1221 1954
F 483 1776
E 461 1039
F 733 1816
S 22 1494
I 462 773
F 937 955
S 1194 2021
I 384 1079
S 858 1310
E 32 150
stdout
copy 
Case 1:
Q1: 246
Q2: 981
Q3: 737
Q4: 148
Q5: 728
Q6: 361
Q7: 0
Q8: 408
Q9: 234
Q10: 0
Q11: 169
Q12: 342
Q13: 1045
Q14: 1182
Q15: 53
Q16: 132
Q17: 128
Q18: 305
Q19: 0
Q20: 103
Q21: 9
Q22: 137
Q23: 640
Q24: 9
Q25: 304
Q26: 279
Q27: 113
Q28: 268
Q29: 1029
Q30: 23
Q31: 104
Q32: 371
Q33: 765
Q34: 0
Q35: 134
Q36: 557
Q37: 145
Q38: 146
Q39: 139
Q40: 793
Q41: 326
Q42: 0
Q43: 0
Q44: 891
Q45: 91
Q46: 848
Q47: 136
Q48: 109
Q49: 416
Q50: 138
Q51: 810
Q52: 478
Q53: 30
Q54: 0
Q55: 0
Q56: 0
Q57: 507
Q58: 89
Q59: 162
Q60: 95
Q61: 619
Q62: 0
Q63: 0
Q64: 171
Q65: 29
Q66: 0
Q67: 4
Q68: 9
Q69: 605
Q70: 880
Q71: 26
Q72: 0
Q73: 449
Q74: 159
Q75: 634
Q76: 101
Q77: 699
Q78: 20
Q79: 860
Q80: 791
Q81: 274
Q82: 615
Q83: 513
Q84: 823
Q85: 994
Q86: 0
Q87: 853
Q88: 945
Q89: 828
Q90: 231
https://ideone.com/3QmSt8
language:
C++ (gcc 8.3)
created:
10 years ago
visibility:
secret

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!