fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. using namespace std;
  4.  
  5. struct node {
  6.     int value = 0;
  7.     node * right, * left;
  8.     int l, r;
  9.     int unPushed = 0;
  10.     node(int l, int r) : left(nullptr), right(nullptr), l(l), r(r) { }
  11.     node * clone() {
  12.         node * ans = new node(l, r);
  13.         ans -> right = right;
  14.         ans -> left = left;
  15.         ans -> value = value;
  16.         ans -> unPushed = unPushed;
  17.         return ans;
  18.     }
  19. };
  20. vector<node *> v;
  21. int sum(node * left, node * right) {
  22.     int ans = 0;
  23.     if(left != nullptr) ans += left -> value;
  24.     if(right != nullptr) ans += right -> value;
  25.     return ans;
  26. }
  27. void push(node *(&k)) {
  28.     k -> unPushed %= 2;
  29.     if (k -> unPushed) {
  30.         int center = (k -> l + k -> r) / 2;
  31.         if (k -> left == nullptr) k -> left = new node(k -> l, center);
  32.         else k -> left = k -> left -> clone();
  33.         if (k -> right == nullptr) k -> right = new node(center + 1, k -> r);
  34.         else k -> right = k -> right -> clone();
  35.         ++k -> left -> unPushed;
  36.         ++k -> right -> unPushed;
  37.         k -> left -> value = (center - k -> l + 1) - k -> left -> value;
  38.         k -> right -> value = (k -> r - center) - k -> right -> value;
  39.         k -> unPushed = 0;
  40.     }
  41.  
  42. }
  43. void updateSegment(node *(&k), int left, int right, int l, int r) {
  44.     if(k == nullptr) k = new node(left, right);
  45.     else k = k -> clone();
  46.     if(l > r) return;
  47.     if(l == left && r == right) {
  48.         ++k -> unPushed;
  49.         k -> value = (r - l + 1) - k -> value;
  50.         return;
  51.     }
  52.     int center = (left + right) / 2;
  53.     push(k);
  54.     updateSegment(k -> left, left, center, l, min(r, center));
  55.     updateSegment(k -> right, center + 1, right, max(l, center + 1), r);
  56.     push(k -> left);
  57.     push(k -> right);
  58.     k -> value = sum(k -> left, k -> right);
  59. }
  60. void update(node *&k, int left, int right, int pos, int a) {
  61.     if (k == nullptr) k = new node(left, right);
  62.     else k = k -> clone();
  63.     if (left == right) {
  64.         k -> value = a;
  65.         return;
  66.     }
  67.     int center = (left + right) / 2;
  68.     push(k);
  69.     if(pos <= center) {
  70.         update(k -> left, left, center, pos, a);
  71.         push(k -> left);
  72.     }
  73.     else {
  74.         update(k -> right, center + 1, right, pos, a);
  75.         push(k -> right);
  76.     }
  77.     k -> value = sum (k -> left, k -> right);
  78. }
  79. int query(node *k, int left, int right, int l, int r) {
  80.     if (l > r) return 0;
  81.     if(k == nullptr) return 0;
  82.     if(left == l && r == right) return k -> value;
  83.     int center = (left + right) / 2;
  84.     push(k);
  85.     return query(k -> left, left, center, l, min(center, r)) + query(k -> right, center + 1, right, max(l, center + 1), r);
  86. }
  87.  
  88. int main() {
  89. 	int n, m, type, pos, l, r;
  90. 	scanf("%d %d", &n, &m);
  91.     v.push_back(new node(1, n));
  92.     for(int i = 1; i <= m; i++) {
  93.         scanf("%d", &type);
  94.         if(type <= 2) {
  95.             scanf("%d", &pos);
  96.             type = 2 - type;
  97.             v.push_back(v.back() -> clone());
  98.             int k = query(v.back(), 1, n, pos, pos);
  99.             if(k != type) updateSegment(v.back(), 1, n, pos, pos);
  100.         }
  101.         else if(type == 3) {
  102.             scanf("%d %d", &l, &r);
  103.             v.push_back(v.back() -> clone());
  104.             updateSegment(v.back(), 1, n, l, r);
  105.         }
  106.         else if(type == 4) {
  107.             scanf("%d", &pos);
  108.             v.push_back(v[pos] -> clone());
  109.         }
  110.         else if(type == 5) {
  111.             scanf("%d %d", &l, &r);
  112.             v.push_back(v.back() -> clone());
  113.             printf("%d\n", query(v.back(), 1, n, l, r));
  114.         }
  115.     }
  116.     return 0;
  117. }
Success #stdin #stdout 0s 15240KB
comments (?)
stdin
copy 
4 7
1 2
1 3
2 2
3 1 3
5 1 2
4 1
5 1 2
stdout
copy 
2
1
https://ideone.com/LCirHc
Нулі та одиниці
language:
C++14 (gcc 8.3)
created:
5 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!