August Long Challenge 2017: Hill Jumping

正答数を見る限りだと正攻法ではないんだろなとは思う。

計算量
\(O(100 Q \log N)\)
キーワード
link-cut tree | envelope

考察

  • 各点におけるジャンプ先をsucc[i]とする。変更クエリにより書き換わるsuccの要素数はたかだか200である。
  • succ[i]で繋いでいくと木になる。この問題は木上のkth-ancestorを求める問題と見做せる。
  • link-cut treeによりlink, cut, kth-ancestorはいずれもO(log N) amortizedで処理できる。
  • kth-ancestorは二分探索木のkth-minと同様
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <deque>
#include <cassert>
 
using namespace std;
 
constexpr int N = 1e5 + 10;
 
struct node {
  node *l = nullptr;
  node *r = nullptr;
  node *p = nullptr;
  int size = 1;
  int key;
};
 
bool is_root(node *x) {
  return !x->p || (x != x->p->l && x != x->p->r);
}
 
int size(node *x) {
  return x ? x->size : 0;
}
 
void fix(node *x) {
  x->size = 1 + size(x->l) + size(x->r);
}
 
void rot(node *x) {
  node *y = x->p;
  node *z = y->p;
  if (z) {
    if (y == z->l) z->l = x;
    if (y == z->r) z->r = x;
  }
  x->p = z;
  y->p = x;
  if (x == y->l) {
    y->l = x->r;
    x->r = y;
    if (y->l) y->l->p = y;
  } else {
    y->r = x->l;
    x->l = y;
    if (y->r) y->r->p = y;
  }
  fix(y);
}
 
void splay(node *x) {
  while (!is_root(x)) {
    node *y = x->p;
    if (!is_root(y)) {
      node *z = y->p;
      rot((x == y->l) == (y == z->l) ? y : x);
    }
    rot(x);
  }
  fix(x);
}
 
void expose(node *x) {
  node *tmp = x;
  node *r = nullptr;
  while (x) {
    splay(x);
    x->r = r;
    fix(x);
    r = x;
    x = x->p;
  }
  splay(tmp);
}
 
void link(node *c, node *p) {
  expose(c);
  expose(p);
  p->r = c;
  c->p = p;
  fix(p);
}
 
void cut(node *x) {
  expose(x);
  x->l->p = nullptr;
  x->l = nullptr;
  fix(x);
}
 
int kth_element(node *x, int k) {
  expose(x);
  while (true) {
    if (size(x->r) == k) {
      break;
    } else if (k < size(x->r)) {
      x = x->r;
    } else {
      if (!x->l) {
        break;
      }
      k -= 1 + size(x->r);
      x = x->l;
    }
  }
  splay(x);
  return x->key;
}
 
long long ft[N];
 
void add(int k, int v) {
  for (k++; k < N; k += k & -k) {
    ft[k] += v;
  }
}
 
long long getval(int k) {
  long long ret = 0;
  for (k++; k > 0; k &= k - 1) {
    ret += ft[k];
  }
  return ret;
}
 
int main() {
  int n, q;
  cin >> n >> q;
  for (int i = 0; i < n; i++) {
    int a;
    scanf("%d", &a);
    add(i, a);
    add(i + 1, -a);
  }
 
  vector<int> succ(n, -1);
  for (int i = 0; i < n; i++) {
    succ[i] = i;
  }
  vector<node *> nodes(n);
  for (int i = 0; i < n; i++) {
    nodes[i] = new node();
    nodes[i]->key = i;
  }
 
  auto update = [&](int l, int r) {
    l = max(0, l);
    deque<int> mono;
    for (int i = min(n - 1, r + 100); i >= r + 1; i--) {
      while (!mono.empty() && getval(i) >= getval(mono.front())) {
        mono.pop_front();
      }
      mono.push_front(i);
    }
    for (int i = r; i >= l; i--) {
      while (!mono.empty() && mono.back() > i + 100) {
        mono.pop_back();
      }
      while (!mono.empty() && getval(i) >= getval(mono.front())) {
        mono.pop_front();
      }
      mono.push_front(i);
      if (mono.size() == 1) {
        if (succ[i] != i) {
          cut(nodes[i]);
        }
        succ[i] = i;
      } else {
        if (succ[i] != i) {
          cut(nodes[i]);
        }
        succ[i] = mono[1];
        link(nodes[i], nodes[mono[1]]);
      }
    }
  };
  update(0, n - 1);
 
  while (q--) {
    int type;
    scanf("%d", &type);
    if (type == 1) {
      int u, cnt;
      scanf("%d %d", &u, &cnt);
      u--;
      printf("%d\n", kth_element(nodes[u], cnt) + 1);
    } else {
      int l, r, x;
      scanf("%d %d %d", &l, &r, &x);
      l--;
      r--;
      add(l, x);
      add(r + 1, -x);
      update(r - 99, r);
      update(l - 100, l - 1);
    }
  }
}