fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. using ll = long long;
  4. std::mt19937 rng((unsigned)chrono::high_resolution_clock::now().time_since_epoch().count());
  5.  
  6. struct Node {
  7.     int val;
  8.     int pr;
  9.     int sz;
  10.     ll sum;
  11.     bool rev;
  12.     Node *l, *r;
  13.     Node(int _v=0): val(_v), pr((int)rng()), sz(1), sum(_v), rev(false), l(nullptr), r(nullptr) {}
  14. };
  15.  
  16. inline int getsz(Node* t){ return t ? t->sz : 0; }
  17. inline ll getsum(Node* t){ return t ? t->sum : 0; }
  18.  
  19. void pull(Node* t){
  20.     if(!t) return;
  21.     t->sz = 1 + getsz(t->l) + getsz(t->r);
  22.     t->sum = (ll)t->val + getsum(t->l) + getsum(t->r);
  23. }
  24.  
  25. void apply_rev(Node* t){
  26.     if(!t) return;
  27.     t->rev ^= 1;
  28.     swap(t->l, t->r);
  29. }
  30.  
  31. void push(Node* t){
  32.     if(!t || !t->rev) return;
  33.     if(t->l) apply_rev(t->l);
  34.     if(t->r) apply_rev(t->r);
  35.     t->rev = false;
  36. }
  37.  
  38. // split by first k elements: left contains first k, right the rest
  39. void split(Node* t, int k, Node*& left, Node*& right){
  40.     if(!t){ left = right = nullptr; return; }
  41.     push(t);
  42.     if(getsz(t->l) >= k){
  43.         // all needed in left subtree
  44.         split(t->l, k, left, t->l);
  45.         right = t;
  46.         pull(right);
  47.     } else {
  48.         split(t->r, k - getsz(t->l) - 1, t->r, right);
  49.         left = t;
  50.         pull(left);
  51.     }
  52. }
  53.  
  54. Node* merge(Node* a, Node* b){
  55.     if(!a || !b) return a ? a : b;
  56.     if(a->pr > b->pr){
  57.         push(a);
  58.         a->r = merge(a->r, b);
  59.         pull(a);
  60.         return a;
  61.     } else {
  62.         push(b);
  63.         b->l = merge(a, b->l);
  64.         pull(b);
  65.         return b;
  66.     }
  67. }
  68.  
  69. int main(){
  70.     ios::sync_with_stdio(false);
  71.     cin.tie(nullptr);
  72.     int n, m;
  73.     if(!(cin >> n >> m)) return 0;
  74.     Node* root = nullptr;
  75.     // build by successive merges (expected O(n))
  76.     for(int i=0;i<n;i++){
  77.         int x; cin >> x;
  78.         Node* node = new Node(x);
  79.         root = merge(root, node);
  80.     }
  81.  
  82.     while(m--){
  83.         int t, a, b;
  84.         cin >> t >> a >> b;
  85.         // split into [1..a-1], [a..b], [b+1..n]
  86.         Node *L, *M, *R;
  87.         split(root, a-1, L, R);
  88.         split(R, b - a + 1, M, R);
  89.         if(t == 1){
  90.             // reverse segment
  91.             if(M) apply_rev(M);
  92.         } else if(t == 2){
  93.             ll ans = M ? M->sum : 0;
  94.             cout << ans << '\n';
  95.         }
  96.         // merge back
  97.         root = merge( merge(L, M), R );
  98.     }
  99.     return 0;
  100. }
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/8GSs0h
language:
C++14 (gcc 8.3)
created:
7 hours 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!