RUPC2018 Day3 E Broccoli or Cauliflower
問題概要
日本語なので省略
解法
Euler Tour をとってやると, あとは必要な操作は「区間和」と「区間のブール値反転操作」だけになります.
想定解は遅延評価セグメントツリーを使っています. (解説URL)
ですが, 遅延評価セグメントツリーを使わなくても解けます.
区間和をもつ merge/split 可能な平衡二分木を使います.
区間の左右反転操作とイメージは同じです.
元の値を持った平衡二分木と, さらにブール値が反転した平衡二分木をもう一つ用意します.
すると, 反転したい区間を両方splitして, swapしてからそれぞれ merge してやると遅延評価なしで簡単に反転操作が可能になります.
シンプルで面白いですね.
ソースコード
https://onlinejudge.u-aizu.ac.jp/beta/review.html#RitsCamp18Day3/2760632
#include <bits/stdc++.h> using namespace std; using graph = vector<vector<int>>; const int MAX = 1e5; int it; int lv[MAX], rv[MAX]; int id[MAX]; void euler_tour(int v, const graph& G) { id[it] = v; lv[v] = it++; for (auto to : G[v]) { euler_tour(to, G); } rv[v] = it; } unsigned xor128() { static unsigned x = 123456789, y = 362436069, z = 521288629, w = 88675123; unsigned t = x ^ (x << 11); x = y; y = z; z = w; return w = w ^ (w >> 19) ^ (t ^ (t >> 8)); } struct node { int val, sum; node *lch, *rch; int size; node(int v, node* l = nullptr, node* r = nullptr) : val(v), sum(v), lch(l), rch(r), size(1) {} }; int count(node *t) { return t ? t->size : 0; } int getsum(node *t) { return t ? t->sum : 0; } node *update(node *t) { t->size = count(t->lch) + count(t->rch) + 1; t->sum = getsum(t->lch) + t->val + getsum(t->rch); return t; } node *merge(node *l, node *r) { if (!l) return r; if (!r) return l; if ((int)xor128() % (l->size + r->size) < l->size) { l->rch = merge(l->rch, r); return update(l); } r->lch = merge(l, r->lch); return update(r); } pair<node*, node*> split(node *t, int k) { if (!t) return make_pair(nullptr, nullptr); if (k <= count(t->lch)) { pair<node*, node*> s = split(t->lch, k); t->lch = s.second; return make_pair(s.first, update(t)); } pair<node*, node*> s = split(t->rch, k - count(t->lch) - 1); t->rch = s.first; return make_pair(update(t), s.second); } int main() { ios::sync_with_stdio(false), cin.tie(0); int n, q; cin >> n >> q; graph G(n); for (int i = 1; i < n; i++) { int p; cin >> p; p--; G[p].push_back(i); } euler_tour(0, G); vector<char> c(n); for (int i = 0; i < n; i++) { cin >> c[i]; } node *t = nullptr, *rt = nullptr; for (int i = 0; i < n; i++) { t = merge(t, new node(c[id[i]] == 'G')); rt = merge(rt, new node(c[id[i]] == 'W')); } while (q--) { int v; cin >> v; v--; auto s1 = split(t, lv[v]); auto s2 = split(s1.second, rv[v] - lv[v]); auto rs1 = split(rt, lv[v]); auto rs2 = split(rs1.second, rv[v] - lv[v]); t = merge(s1.first, merge(rs2.first, s2.second)); rt = merge(rs1.first, merge(s2.first, rs2.second)); puts(getsum(t) > getsum(rt) ? "broccoli" : "cauliflower"); } return 0; }
あとがき
実はこの解法はコンテスト終了後にサークルの先輩に教えてもらった方法です.
オンライン参加時は想定解で解きました.