Cod sursa(job #2587650)

Utilizator AlexPop28Pop Alex-Nicolae AlexPop28 Data 23 martie 2020 12:57:21
Problema Secv8 Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.07 kb
#include <bits/stdc++.h>
#define dbg() cerr <<
#define name(x) (#x) << ": " << (x) << ' ' <<

using namespace std;

struct Treap {
  struct Node {
    int val, pri;
    int l = 0, r = 0, sz = 0, lazy = 0; 
    Node() {}
    Node(int val_, int pri_) : val(val_), pri(pri_) {}
  };

  mt19937 rng = mt19937(424321);
  vector<Node> tree = vector<Node>(1, Node(-1, -1));
  int root = 0;

  void Recalc(int node) {
    int l = tree[node].l, r = tree[node].r;
    tree[node].sz = tree[l].sz + tree[r].sz + 1;
  }

  void Propag(int node) {
    if (!tree[node].lazy || node == 0) return;
    
    for (int son : {tree[node].l, tree[node].r}) {
      tree[son].lazy ^= 1;
      swap(tree[son].l, tree[son].r);
    }
    tree[node].lazy = 0;
  }

  int Join(int t0, int t1) {
    Propag(t0), Propag(t1);
    if (t0 == 0) return t1;
    if (t1 == 0) return t0;

    if (tree[t0].pri > tree[t1].pri) {
      tree[t0].r = Join(tree[t0].r, t1);
      Recalc(t0);
      return t0;
    } else {
      tree[t1].l = Join(t0, tree[t1].l);
      Recalc(t1);
      return t1;
    }
  }

  pair<int, int> Split(int node, int key) {
    Propag(node);
    if (node == 0) return {0, 0};
    int lft_sz = tree[tree[node].l].sz;
    if (lft_sz > key) {
      int l, r; tie(l, r) = Split(tree[node].l, key);
      tree[node].l = r;
      Recalc(node);
      return {l, node};
    } else {
      int l, r; tie(l, r) = Split(tree[node].r, key - lft_sz - 1);
      tree[node].r = l;
      Recalc(node);
      return {node, r};
    }
  }

  int Alloc(int val) {
    tree.emplace_back(Node(val, rng()));
    Recalc(tree.size() - 1);
    return tree.size() - 1;
  }

  tuple<int, int, int> Slice(int node, int l, int r) {
    int lft, mid, rgt;
    tie(mid, rgt) = Split(node, r);
    tie(lft, mid) = Split(mid, l - 1);
    return make_tuple(lft, mid, rgt);
  }
  
  void Insert(int key, int val) {
    int l, r; tie(l, r) = Split(root, key - 1);
    int m = Alloc(val);
    root = Join(Join(l, m), r);
  }

  int GetKth(int key) {
    int l, m, r; tie(l, m, r) = Slice(root, key, key);
    root = Join(Join(l, m), r);
    return tree[m].val;
  }

  void Reverse(int l, int r) {
    int lft, mid, rgt; tie(lft, mid, rgt) = Slice(root, l, r);
    tree[mid].lazy = 1;
    swap(tree[mid].l, tree[mid].r);
    root = Join(Join(lft, mid), rgt);
  }

  void Delete(int l, int r) {
    int lft, mid, rgt; tie(lft, mid, rgt) = Slice(root, l, r);
    root = Join(lft, rgt);
  }
};

int main() {
  ifstream cin("secv8.in");
  ofstream cout("secv8.out");

  int q; cin >> q;
  int foo; cin >> foo;

  Treap t;
  int n = 0;
  while (q--) {
    char type; cin >> type;
    if (type == 'I') {
      int pos, val; cin >> pos >> val; --pos;
      t.Insert(pos, val);
      ++n;
    } else if (type == 'A') {
      int pos; cin >> pos; --pos;
      cout << t.GetKth(pos) << '\n';
    } else if (type == 'R') {
      int l, r; cin >> l >> r; --l, --r;
      t.Reverse(l, r);
    } else {
      assert(type == 'D');
      int l, r; cin >> l >> r; --l, --r;
      t.Delete(l, r);
      n -= r - l + 1;
    }
  } 
  for (int i = 0; i < n; ++i) {
    cout << t.GetKth(i) << ' ';
  }
  cout << endl;
}