fork download
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. typedef unsigned long long ull;
  6. typedef long long ll;
  7. typedef pair<int, int> ii;
  8. typedef vector<ii> vii;
  9. typedef vector<int> vi;
  10. typedef vector<ll> vll;
  11.  
  12. #define PI (2*acos(0.0))
  13. #define eps 1e-9
  14. #define pb push_back
  15. #define endl "\n"
  16. #define watch(x) cout << (#x) << " is " << (x) << endl;
  17. #define show(v) for(int fi = 0; fi < v.size(); fi++) cout << v[fi] << " "; cout << endl;
  18. #define showpair(v) for(int fi = 0; fi < v.size(); fi++) cout << v[fi].first << " " << v[fi].second << endl;
  19. #define mp make_pair
  20. #define ff first
  21. #define ss second
  22. #define fu cout << "lol" << endl;
  23. #define precision(n) cout << fixed << setprecision(n);
  24. #define lb lower_bound
  25. #define up upper_bound
  26. #define vscan for(i = 0;i<n;i++){cin>>in; v.pb(in);}
  27. #define all(a) a.begin(), a.end()
  28. #define min3(a,b,c) min(a,min(b,c))
  29. #define max3(a,b,c) max(a,max(b,c))
  30. #define mem(a,val) memset(a,val,sizeof(a))
  31. #define loop(i,n) for(i = 0; i < n; i++)
  32. #define TC() ull T; cin>>T; while(T--)
  33. #define IN(x) {scanf("%d",&x);}
  34. #define LL(x) {scanf("%lld",&x);}
  35. #define CC(x) {scanf("%c",&x);}
  36. #define pfl(x) printf("%d\n",x)
  37. #define pfll(x) printf("%lld\n",x)
  38. #define newl puts("")
  39. #define space printf(" ")
  40. #define MOD 1000000007
  41. #define speed ios_base::sync_with_stdio(false); cin.tie(NULL);
  42.  
  43. const int N = 1024010;
  44. int tree[4*N];
  45. int arr[4*N];
  46. string s;
  47.  
  48. void push(int node, int l, int r){
  49. if(l == r) return;
  50. int mid = l + r >> 1;
  51. if(arr[node*2]) push(node*2, l, mid);
  52. if(arr[node*2+1]) push(node*2+1,mid+1,r);
  53. if(arr[node] == 1){
  54. tree[node*2] = mid - l + 1;
  55. tree[node*2+1] = r - (mid+1) + 1;
  56. arr[node*2] = arr[node*2+1] = 1;
  57. }
  58. else if(arr[node] == 2){
  59. tree[node*2] = 0;
  60. tree[node*2+1] = 0;
  61. arr[node*2] = arr[node*2+1] = 2;
  62. }
  63. else if(arr[node] == 3){
  64. tree[node*2] = mid - l + 1 - tree[node*2];
  65. tree[node*2+1] = r - (mid+1) + 1 - tree[node*2+1];
  66. arr[node*2] = arr[node*2+1] = 3;
  67. }
  68. arr[node] = 0;
  69. }
  70.  
  71. void build(int node, int l, int r){
  72. if(l == r){
  73. tree[node] = s[l] - 48;
  74. arr[node] = 0;
  75. return;
  76. }
  77. int mid = l + r >> 1;
  78. build(node*2, l, mid);
  79. build(node*2+1, mid+1, r);
  80. tree[node] = tree[node*2] + tree[node*2+1]; //keep track of how many ones there are in the range covered by node
  81. arr[node] = 0;
  82. }
  83.  
  84. void upd(int node, int l, int r, int x, int y, int t){
  85. if(x > r || y < l) return;
  86. if(x == l && y == r){
  87. if(arr[node]) push(node,l,r);
  88. arr[node] = t;
  89. if(t == 1) tree[node] = r-l+1; //all values in this range would turn 1
  90. if(t == 2) tree[node] = 0; //number of 1s in this range becomes 0
  91. if(t == 3) tree[node] = (r-l+1) - tree[node]; //all 1s should turn into 0 and vice versa.
  92. return;
  93. }
  94. int mid = l+r>>1;
  95. if(arr[node]) push(node, l, r);
  96. upd(node*2, l, mid, x, min(y,mid),t);
  97. upd(node*2+1,mid+1,r,max(x,mid+1),y,t);
  98. tree[node] = tree[node*2] + tree[node*2+1];
  99. }
  100.  
  101. int query(int node, int l, int r, int x, int y){
  102. if(x > r || y < l) return 0;
  103. if(x == l && y == r) return tree[node];
  104. int mid = l + r >> 1;
  105. if(arr[node]) push(node, l, r);
  106. return query(node*2, l, mid, x, min(y,mid)) + query(node*2+1, mid+1, r, max(x,mid+1), y);
  107. }
  108.  
  109. int main()
  110. {
  111. int i = 0, j = 0, in, cs = 0;
  112. speed; // faster io
  113. TC(){ // for each test case
  114. s.clear();
  115. int n; cin>>n;
  116. for(i = 0; i < n; i++){
  117. int t; cin>>t;
  118. string a; cin>>a;
  119. while(t--) s += a;
  120. }
  121. int q; cin>>q;
  122. cout << "Case " << ++cs << ":" << endl;
  123. int c = 0;
  124. int pos = s.size();
  125. build(1,0,pos-1);
  126. while(q--){
  127. char a; cin>>a;
  128. int l, r; cin>>l>>r;
  129. if(a == 'F') upd(1,0,pos-1,l,r,1);
  130. else if(a == 'E') upd(1,0,pos-1,l,r,2);
  131. else if(a == 'I') upd(1,0,pos-1,l,r,3);
  132. else if(a == 'S') cout << "Q" << ++c << ": " << query(1,0,pos-1,l,r) << endl;
  133. }
  134. }
  135. return 0;
  136. }
  137.  
Success #stdin #stdout 0s 4380KB
stdin
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
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