fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define mx 100009
  4. struct Node {
  5.     int zero = 0, one = 0, two = 0, propChnage = 0;
  6. };
  7. Node tree[mx * 3];
  8. Node merge(Node left, Node right) {
  9.     return {
  10.         left.zero + right.zero,
  11.         left.one + right.one,
  12.         left.two + right.two,
  13.         0,
  14.     };
  15. }
  16. void init(int node, int b, int e) {
  17.     // cout << "init\n";
  18.     if(b == e) {
  19.         tree[node] = {
  20.             .zero = 1,
  21.         };
  22.         return;
  23.     }
  24.     int left = node * 2;
  25.     int right = left + 1;
  26.     int mid = (b + e) / 2;
  27.     init(left, b, mid);
  28.     init(right, mid + 1, e);
  29.     tree[node] = merge(tree[left], tree[right]);
  30. }
  31.  
  32. void printTree(int node, int b, int e) {
  33.     cout << b << ' ' << e << 
  34.         '[' << tree[node].zero << ' ' << tree[node].one << ' ' << tree[node].two << "] " 
  35.         << tree[node].propChnage << endl;
  36.     if(b == e) return;
  37.     int left = node * 2;
  38.     int right = left + 1;
  39.     int mid = (b + e) / 2;
  40.     printTree(left, b, mid);
  41.     printTree(right, mid + 1, e);
  42. }
  43.  
  44. void update(int node, int b, int e, int i, int j) {
  45.     // cout << "update" << endl;
  46.     if(e < i || b > j) return;
  47.     if(b >= i && e <= j) {
  48.         tree[node].propChnage++;
  49.         tree[node].propChnage %= 3;
  50.  
  51.         int tmp = tree[node].zero;
  52.         tree[node].zero = tree[node].two;
  53.         tree[node].two = tree[node].one;
  54.         tree[node].one = tmp;
  55.  
  56.  
  57.         return;
  58.     }
  59.     int left = node * 2;
  60.     int right = left + 1;
  61.     int mid = (b + e) / 2;
  62.     update(left, b, mid, i, j);
  63.     update(right, mid + 1, e, i, j);
  64.     tree[node] = merge(tree[left], tree[right]);
  65. }
  66. Node query(int node, int b, int e, int i, int j, int change) {
  67.     // cout << "query\n";
  68.     if(e < i || b > j) {
  69.         return {0, 0, 0, 0};
  70.     }
  71.     if(b >= i && e <= j) {
  72.         switch (change)
  73.         {
  74.             case 1: {
  75.                 int tmp = tree[node].zero;
  76.                 tree[node].zero = tree[node].two;
  77.                 tree[node].two = tree[node].one;
  78.                 tree[node].one = tmp;
  79.                 break;
  80.             }
  81.             case 2: {
  82.                 int tmp2 = tree[node].two;
  83.                 tree[node].two = tree[node].zero;
  84.                 int tmp1 = tree[node].one;
  85.                 tree[node].one = tmp2;
  86.                 tree[node].zero = tmp1;
  87.                 break;
  88.             }
  89.         }
  90.         return tree[node];
  91.     }
  92.     int left = node * 2;
  93.     int right = left + 1;
  94.     int mid = (b + e) / 2;
  95.     return merge(query(left, b, mid, i, j, tree[node].propChnage + change), query(right, mid + 1, e, i, j, tree[node].propChnage + change));
  96.     tree[node].propChnage = 0;
  97. }
  98. int main() {
  99.     int n, q;
  100.     cin >> n >> q;
  101.     init(1, 1, n);
  102.     // printTree(1, 1, n);
  103.     while(q--) {
  104.         int qtype, i, j;
  105.         cin >> qtype >> i >> j;
  106.         i++, j++;
  107.         if(qtype == 0) update(1, 1, n, i, j);
  108.         else cout << query(1, 1, n, i, j, 0).zero << endl;
  109.         // printTree(1, 1, n);
  110.     }
  111.     return 0;
  112. }
Runtime error #stdin #stdout 1.97s 2095860KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/fdOGB6
problem MULTQ3, based on SPOJ submission 32909779 (CPP14), 2024-04-12 18:55:32
language:
C++14 (gcc 8.3)
created:
23 days 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!