fork download 
  1. //Misc;Segment Tree;Lazy Propagation
  2. #include <iostream>
  3. #include <string>
  4. #include <cstring>
  5. #define MAX 3000100
  6. #define ull long long
  7. using namespace std;
  8.  
  9. struct Node { 
  10.     int a, b;
  11.     int pending;
  12.  
  13.     Node() : a(0), b(0), pending(0) {}
  14.     Node(int a) : a(a), b(0), pending(0) { }
  15.     Node(int a, int b) : a(a), b(b), pending(0) { }
  16.  
  17.     Node change(int n) {
  18.         if (n==1) {
  19.             b += a;
  20.             a = 0;
  21.             pending = n;
  22.         } else if (n==2) { 
  23.             a += b;
  24.             b = 0;
  25.             pending = n;
  26.         } else if (n==3) {
  27.             swap(a, b);
  28.             pending = 3-pending;
  29.         }
  30.  
  31.         return *this;
  32.     }
  33.  
  34.     Node operator +(Node x) {
  35.         return Node(a+x.a, b+x.b);    
  36.     }
  37. };
  38.  
  39. struct Segtree {
  40.     Node T[MAX];
  41.     int n;
  42.  
  43.     void clear(int n, int *P) {
  44.         this->n = n;               
  45.  
  46.         build(1, 1, n, P);
  47.     }
  48.  
  49.     Node build(int v, int a, int b, int *P) {
  50.         if (a==b)
  51.             return T[v] = Node(1-P[a], P[a]);
  52.         else
  53.             return T[v] = 
  54.                 build(2*v, a, (a+b)/2, P) + 
  55.                 build(2*v+1, (a+b)/2+1, b, P);
  56.     }
  57.  
  58.     Node update(int v, int a, int b, int i, int j, int carry, int increment) {
  59.         T[v].change(carry);
  60.  
  61.         if (i>b || j<a)
  62.             return Node(0);
  63.  
  64.         if (i<=a && b<=j) 
  65.             return T[v].change(increment);
  66.  
  67.         Node answer = 
  68.             update(v*2, a, (a+b)/2, i, j, T[v].pending, increment) + 
  69.             update(v*2+1, (a+b)/2+1, b, i, j, T[v].pending, increment);
  70.  
  71.         T[v] = T[v*2] + T[v*2+1];
  72.  
  73.         return answer;
  74.     }
  75.  
  76.     Node update(int i, int j, int inc) {
  77.         return update(1, 1, n, i, j, 0, inc);
  78.     }
  79.  
  80.     Node query(int i, int j) {
  81.         return update(i, j, 0);
  82.     }
  83.  
  84. };
  85.  
  86. Segtree T;
  87. int P[MAX];
  88. string s;
  89.  
  90. int main() {
  91.     int cases; cin >> cases;
  92.  
  93.     for(int tt=1; tt<=cases; tt++) {
  94.         cout << "Case " << tt << ":" << endl;
  95.  
  96.         int m; cin >> m;
  97.         int n = 0;
  98.         for(int i=0; i<m; i++) {
  99.             int t;
  100.             cin >> t >> s;
  101.             for(int j=0; j<t; j++) {
  102.                 for(int k=0; k<s.size(); k++) {
  103.                     P[++n] = s[k]-'0';
  104.                 }
  105.             }
  106.         }
  107.         T.clear(n, P);
  108.  
  109.         int q; cin >> q;
  110.         int query = 0;
  111.         while(q--) {
  112.             char cmd; int a, b;
  113.             cin >> cmd >> a >> b;
  114.             a++; b++;
  115.             if (cmd == 'F') {
  116.                 T.update(a, b, 1);
  117.             } else if (cmd == 'E') {
  118.                 T.update(a, b, 2);
  119.             } else if (cmd == 'I') {
  120.                 T.update(a, b, 3);
  121.             } else {
  122.                 Node node = T.query(a, b);
  123.                 cout << "Q" << ++query << ": " << node.b << endl;
  124.             }
  125.         }
  126.     }
  127. }
Success #stdin #stdout 0.03s 50312KB
comments (?)
stdin 
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 
Case 1:
Q1: 5
Q2: 1
Case 2:
Q1: 0
https://ideone.com/oU0ohg
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!