AOJ 1508 RMQ
問題
日本語なので本文参照(http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1508)
RMQに、値の変更および、[l, r]の部分を巡回シフトさせるクエリが飛んでくる。
制約条件
n≦2 * 10^5
q≦2 * 10^5
方針
平方分割で頑張れば、要素の追加と削除がO(√n)で出来るRMQが書ける。
何回か追加と削除をすると、偏るので、√n回に1回くらいバケットを再構築する。
これで以前通した。
今回は平衡二分木を使ったRMQを書いた。
split, mergeという操作が出来るので、区間に対する操作が大体なんでもO(log n)で出来る。
参考スライド:http://www.slideshare.net/iwiwi/2-12188757
ソースコード
template<class T> struct treap{ struct node_t{ T val; T sum; node_t *lch, *rch; int pri; int cnt; node_t(T v, int p) : val(v), pri(p), cnt(1), sum(v){ lch = rch = NULL; } }; node_t *root; treap() : root(NULL){ } int count(node_t *t){ return t ? t->cnt : 0; } T sum(node_t *t) { return t ? t->sum : inf; } int size() { return count(root); } node_t *update(node_t *t){ t->cnt = count(t->lch) + count(t->rch) + 1; t->sum = min(min(sum(t->lch), sum(t->rch)), t->val); return t; } node_t *merge(node_t *l, node_t *r){ if(!l || !r) return l ? l : r; 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 mp((node_t*)NULL, (node_t*)NULL); if(k <= count(t->lch)){ pair<node_t*, node_t*> s = split(t->lch, k); t->lch = s.second; return mp(s.first, update(t)); } else{ pair<node_t*, node_t*> s = split(t->rch, k - count(t->lch) - 1); t->rch = s.first; return mp(update(t), s.second); } } node_t *insert(node_t *t, int k, T val, int pri){ pair<node_t*, node_t*> s = split(t, k); t = merge(s.first, new node_t(val, pri)); t = merge(t, s.second); return update(t); } node_t *erase(node_t *t, int k){ pair<node_t*, node_t*> s1, s2; s2 = split(t, k + 1); s1 = split(s2.first, k); t = merge(s1.first, s2.second); return update(t); } node_t *find(node_t *t, int k){ int c = count(t->lch); if(k < c) return find(t->lch, k); if(k == c) return t; return find(t->rch, k - c - 1); } void insert(int k, T val){ root = insert(root, k, val, rand()); } void erase(int k){ root = erase(root, k); } node_t *find(int k){ return find(root, k); } void shift(int l, int r){ pair<node_t*, node_t*> a, b, c; c = split(root, r); b = split(c.first, r - 1); a = split(b.first, l); root = merge(a.first, b.second); root = merge(root, a.second); root = merge(root, c.second); } int query(int l, int r, node_t *t){ int sz = count(t); if(l >= sz || r <= 0) return inf; if(l <= 0 && r >= sz) return sum(t); int c = count(t->lch); int lv = query(l, r, t->lch); int rv = query(l - c - 1, r - c - 1, t->rch); int res = min(lv, rv); if(l <= c && c < r) res = min(res, t->val); return res; } }; int main() { srand(time(NULL)); int n, q; treap<int> t; scanf("%d%d", &n, &q); rep(i, n){ int a; scanf("%d", &a); t.insert(i, a); } while(q--){ int c, a, b; scanf("%d%d%d", &c, &a, &b); if(c == 2){ t.erase(a); t.insert(a, b); } else if(c == 1){ printf("%d\n", t.query(a, b + 1, t.root)); } else{ t.shift(a, b + 1); } } return 0; }