basic.cc

#include <bits/stdc++.h>
using namespace std;

const int INF = 1000000000;
const int MAX_N = 1000010;

using random_type = uint_fast32_t;

struct node_t {
  int val;
  random_type pri;
  int cnt;
  int min;
  node_t *lch, *rch;

  node_t(int v, random_type p)
      : val(v), pri(p), cnt(1), min(v), lch(NULL), rch(NULL) {}
};

int count(node_t *t) { return !t ? 0 : t->cnt; }

int min(node_t *t) { return !t ? INF : t->min; }

node_t *update(node_t *t) {
  t->cnt = count(t->lch) + count(t->rch) + 1;
  t->min = min({min(t->lch), min(t->rch), t->val});
  return t;
}

node_t *merge(node_t *l, node_t *r) {
  if (!l || !r)
    return !l ? r : l;

  if (l->pri > r->pri) {
    l->rch = merge(l->rch, r);
    return update(l);
  } else {
    r->lch = merge(l, r->lch);
    return update(r);
  }
}

pair<node_t *, node_t *> split(node_t *t, int k) {
  // if (!t) return make_pair(NULL, NULL); // compile error on GCC C++14
  if (!t)
    return make_pair(nullptr, nullptr); //

  if (k <= count(t->lch)) {
    pair<node_t *, node_t *> s = split(t->lch, k);
    t->lch = s.second;
    return make_pair(s.first, update(t));
  } else {
    pair<node_t *, node_t *> s = split(t->rch, k - count(t->lch) - 1);
    t->rch = s.first;
    return make_pair(update(t), s.second);
  }
}

// split で [l, r) を切り出して根を見る方法もある
int range_min(node_t *n, int l, int r) {
  l = std::max<int>(l, 0);
  r = std::min(r, count(n));
  if (l >= r)
    return INF;
  if (l == 0 && r == count(n))
    return min(n);
  int res = INF;
  int sl = count(n->lch);
  res = std::min(res, range_min(n->lch, l, r));
  if (l <= sl && sl < r)
    res = std::min(res, n->val);
  res = std::min(res, range_min(n->rch, l - sl - 1, r - sl - 1));
  return res;
}

// ライブラリここまで

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define all(c) begin(c), end(c)
#define dump(x) cerr << __LINE__ << ":\t" #x " = " << (x) << endl

void test() {
  const int N = 100;
  const int Q = 100;
  static int a[N];
  rep(i, N) a[i] = i * 2 + 1;
  mt19937 pmt(1);
  uniform_int_distribution<random_type> prand(0, 1 << 30);
  node_t *n = NULL;
  rep(i, N) n = merge(n, new node_t(a[i], prand(pmt)));

  mt19937 mt(1);
  uniform_int_distribution<random_type> rand(0, N);

  rep(i, Q) {
    int k = rand(mt);
    auto p = split(n, k);
    node_t *l, *r;
    tie(l, r) = p;
    n = merge(r, l);
    rotate(a, a + k, a + N);
    int ql = 0;
    int qr = 0;
    while (ql == qr) {
      ql = rand(mt);
      qr = rand(mt);
    }
    if (ql > qr)
      swap(ql, qr);
    int res = range_min(n, ql, qr);
    int exp = INF;
    for (int i = ql; i < qr; ++i) {
      exp = min(exp, a[i]);
    }
    assert(res == exp);
  }
  cout << "ok!" << endl;
}

void benchmark() {
  int N, Q;
  cin >> N >> Q;
  static int a[MAX_N];
  rep(i, N) cin >> a[i];
  mt19937 primt(1);
  uniform_int_distribution<random_type> prirand(
      0, numeric_limits<random_type>::max());
  node_t *n = NULL;
  rep(i, N) n = merge(n, new node_t(a[i], prirand(primt)));

  vector<tuple<int, int, int>> queries(Q);
  rep(i, Q) {
    int a, b, c;
    cin >> a >> b >> c;
    queries[i] = make_tuple(a, b, c);
  }

  auto started = chrono::high_resolution_clock::now();
  int res = 0;
  rep(i, Q) {
    int a, b, c;
    tie(a, b, c) = queries[i];
    if (a == 0) {
      int rm = range_min(n, b, c);
      res ^= rm;
    } else {
      auto p = split(n, b);
      node_t *l, *r;
      tie(l, r) = p;
      n = merge(r, l);
    }
  }
  cout << res << endl;
  auto done = chrono::high_resolution_clock::now();
  cout << chrono::duration_cast<chrono::milliseconds>(done - started).count()
       << " ms" << endl;
}

int main() {
  // test();
  benchmark();
}

fast.cc

#include <bits/stdc++.h>

using random_type = uint_fast32_t;
random_type xor128() {
  static random_type x = 123456789, y = 362436069, z = 521288629, w = time(0);
  random_type t = x ^ (x << 11);
  x = y;
  y = z;
  z = w;
  w = (w ^ (w >> 19)) ^ (t ^ (t >> 8));
  return w;
}

using key_type = int;
const key_type INF = 1000000000;
const int MAX_N = 1000010; // 挿入の回数 + 少し

struct Node {
  key_type key;
  random_type priority;
  Node *left, *right;
  int size;
  key_type min;

  static Node *const nil;
  static int node_count;

  Node() {}

  Node(const key_type &x) : Node(x, xor128(), nil, nil, 1, x) {}

  Node(const key_type &key_, random_type priority_, Node *left_, Node *right_,
       int size_, const key_type &min_)
      : key(key_), priority(priority_), left(left_), right(right_), size(size_),
        min(min_) {}

  void *operator new(std::size_t) {
    static Node pool[MAX_N];
    return pool + node_count++;
  }

  static void delete_all() { Node::node_count = 1; }
};

using np = Node *;
using npair = std::pair<np, np>;

int Node::node_count = 0;
Node *const Node::nil =
    new Node(key_type(), std::numeric_limits<random_type>::min(), nullptr,
             nullptr, 0, INF);

void verify(np n, int depth = 0) {
  if (n == Node::nil)
    return;
  assert(n->size == 1 + n->left->size + n->right->size);
  assert(n->min == std::min({n->left->min, n->key, n->right->min}));
  assert(n->left != nullptr);
  assert(n->right != nullptr);
  assert(n->priority >= n->left->priority);
  verify(n->left, depth + 1);
  assert(n->priority >= n->right->priority);
  verify(n->right, depth + 1);
}

int get_depth(np n) {
  if (n == Node::nil)
    return 0;
  return 1 + std::max(get_depth(n->left), get_depth(n->right));
}

np update(np n) {
  n->size = 1 + n->left->size + n->right->size;
  n->min = std::min({n->left->min, n->key, n->right->min});
  return n;
}

np make_tree(key_type *left, key_type *right) {
  int sz = right - left;
  if (sz == 0)
    return Node::nil;
  key_type *mid = left + sz / 2;
  np lc = make_tree(left, mid);
  np rc = make_tree(mid + 1, right);
  return new Node(*mid, -1, lc, rc, sz, std::min({lc->min, *mid, rc->min}));
}

np make_treap(key_type *left, key_type *right) {
  np root = make_tree(left, right);
  int n = right - left;
  std::vector<random_type> ps(n);
  std::generate(ps.begin(), ps.end(), xor128);
  std::sort(ps.begin(), ps.end());
  std::queue<np> que;
  que.push(root);
  while (que.size()) {
    np n = que.front();
    que.pop();
    random_type pri = ps.back();
    ps.pop_back();
    n->priority = pri;
    if (n->left != Node::nil)
      que.push(n->left);
    if (n->right != Node::nil)
      que.push(n->right);
  }
  return root;
}

key_type range_min(np n, int l, int r) {
  l = std::max<int>(l, 0);
  r = std::min(r, n->size);
  if (l >= r)
    return INF;
  if (l == 0 && r == n->size)
    return n->min;
  key_type res = INF;
  int sl = n->left->size;
  res = std::min(res, range_min(n->left, l, r));
  if (l <= sl && sl < r)
    res = std::min(res, n->key);
  res = std::min(res, range_min(n->right, l - sl - 1, r - sl - 1));
  return res;
}

np merge(np l, np r) {
  if (l == Node::nil)
    return r;
  if (r == Node::nil)
    return l;
  if (l->priority > r->priority) {
    l->right = merge(l->right, r);
    return update(l);
  } else {
    r->left = merge(l, r->left);
    return update(r);
  }
}

npair split(np n, int k) {
  if (n == Node::nil)
    return {Node::nil, Node::nil};
  if (k <= n->left->size) {
    npair p = split(n->left, k);
    n->left = p.second;
    return npair(p.first, update(n));
  } else {
    npair p = split(n->right, k - n->left->size - 1);
    n->right = p.first;
    return npair(update(n), p.second);
  }
}

void set(np n, int k, const key_type &x) {
  if (k < n->left->size)
    set(n->left, k, x);
  else if (n->left->size == k)
    n->key = x;
  else
    set(n->right, k - n->left->size - 1, x);
  update(n);
}

key_type get(np n, int k) {
  if (k < n->left->size)
    return get(n->left, k);
  else if (n->left->size == k)
    return n->key;
  else
    return get(n->right, k - n->left->size - 1);
}

np lower_bound(np n, const key_type &x) {
  if (n == Node::nil)
    return Node::nil;
  else if (n->key >= x) {
    np res = lower_bound(n->left, x);
    return res != Node::nil ? res : n;
  } else
    return lower_bound(n->right, x);
}

np upper_bound(np n, const key_type &x) {
  if (n == Node::nil)
    return Node::nil;
  else if (n->key > x) {
    np res = upper_bound(n->left, x);
    return res != Node::nil ? res : n;
  } else
    return upper_bound(n->right, x);
}

// ライブラリここまで

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define all(c) begin(c), end(c)
#define dump(x) cerr << __LINE__ << ":\t" #x " = " << (x) << endl

void test() {
  Node::delete_all();
  const int N = 100;
  const int Q = 100;
  static int a[N];
  rep(i, N) a[i] = i * 2 + 1;
  np n = make_treap(a, a + N);
  verify(n);

  mt19937 mt(1);
  uniform_int_distribution<int> rand(0, N);

  rep(i, Q) {
    int k = rand(mt);
    auto p = split(n, k);
    np l, r;
    tie(l, r) = p;
    n = merge(r, l);
    rotate(a, a + k, a + N);
    int ql = 0;
    int qr = 0;
    while (ql == qr) {
      ql = rand(mt);
      qr = rand(mt);
    }
    if (ql > qr)
      swap(ql, qr);
    int res = range_min(n, ql, qr);
    int exp = INF;
    for (int i = ql; i < qr; ++i) {
      exp = min(exp, a[i]);
    }
    assert(res == exp);
  }
  cout << "ok!" << endl;
}

void benchmark() {
  Node::delete_all();
  int N, Q;
  cin >> N >> Q;
  static int a[MAX_N];
  rep(i, N) cin >> a[i];
  np n = make_treap(a, a + N);

  vector<tuple<int, int, int>> queries(Q);
  rep(i, Q) {
    int a, b, c;
    cin >> a >> b >> c;
    queries[i] = make_tuple(a, b, c);
  }

  auto started = chrono::high_resolution_clock::now();
  int res = 0;
  rep(i, Q) {
    int a, b, c;
    tie(a, b, c) = queries[i];
    if (a == 0) {
      int rm = range_min(n, b, c);
      res ^= rm;
    } else {
      auto p = split(n, b);
      np l, r;
      tie(l, r) = p;
      n = merge(r, l);
    }
  }
  cout << res << endl;
  auto done = chrono::high_resolution_clock::now();
  cout << chrono::duration_cast<chrono::milliseconds>(done - started).count()
       << " ms" << endl;
}

int main() {
  // test();
  benchmark();
}

generate.rb

srand(2019)

N = 1_000_000
Q = 1_000_000

puts "#{N} #{Q}"

N.times do
  puts rand(0..1_000_000_000)
end

Q.times do |i|
  if i.even?
    l, r = 0, 0
    while l == r
      l, r = rand(0..N), rand(0..N)
    end
    l, r = r, l unless l < r
    puts "0 #{l} #{r}" # RMQ
  else
    k = rand(0..N)
    puts "1 #{k} -1" # rotate
  end
end