kazuma8128’s blog

競プロの面白い問題を解きます

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;
}

あとがき

実はこの解法はコンテスト終了後にサークルの先輩に教えてもらった方法です.
オンライン参加時は想定解で解きました.