Codeforces Round #200 (Div. 1) D. Water Tree

オイラーツアーツアー終点です。
セグメント木は典型以外はあんまり自信持って書けません。

問題

Problem - 343D - Codeforces

解法

やっぱりオイラーツアーします。

そしてやっぱりセグメント木を 2 つ用意します。
一つは区間に一様に値 x を入れて更新し, かつ ある座標 x における値を取り出すセグメント木(1),
もうひとつはある座標 x における値を更新し, かつ ある区間の最大値を取り出すセグメント木(2)を用意します。

基本的なアイデアは, v について fill の操作をやった一番最近のクエリ番号と empty の操作を行った一番最近のクエリ番号を覚えておき, fill か empty かを判定するときにはどちらのクエリ番号のほうがより最近行った更新かを見れば良いという感じです。

このとき, fill の操作は (1) のセグメント木を使えば良く, empty の操作は (2) のセグメント木を使えば求めることが出来ます。
(1) についてはオイラーツアーを使えばそのままなのでわかりやすいと思います。 (2) は要するに頂点 v より下にある頂点(v の子となる頂点)で一番最近更新したものが何かがわかれば良いので (2) のセグメント木で求められます。

// fill用
// 区間に更新, 1点の値を導出
class segTree1 {
public:
    int N;
    vector<int> seg;
    segTree1(int V) {
        N = 1;
        while (N < V) N *= 2;
        seg.resize(2*N-1, -2);
    }
    void update(int a, int b, int k, int l, int r, int x) {
        if (r <= a || b <= l) return;
        if (a <= l && r <= b) {
            seg[k] = max(seg[k], x);
            return;
        }
        update(a, b, 2*k+1, l, (l+r)/2, x);
        update(a, b, 2*k+2, (l+r)/2, r, x);
    }
    void update(int a, int b, int x) {
        update(a, b, 0, 0, N, x);
    }
    int get(int k) {
        k += N-1;
        int ret = -2;
        while (k >= 0) {
            ret = max(ret, seg[k]);
            k = (k!=0) ? (k-1) / 2 : -1;
        }
        return ret;
    }
};

// clear用
// 1 点に更新, 区間の最大値を導出
class segTree2 {
public:
    int N;
    vector<int> seg;
    segTree2(int V) {
        N = 1;
        while (N < V) N *= 2;
        seg.resize(2*N-1, -1);
    }
    void update(int k, int x) {
        k += N-1;
        seg[k] = x;
        while (k) {
            k = (k-1) / 2;
            seg[k] = max(seg[2*k+1], seg[2*k+2]);
        }
    }
    int get(int a, int b, int k, int l, int r) {
        if (r <= a || b <= l) return -1;
        if (a <= l && r <= b) return seg[k];
        return max(get(a, b, 2*k+1, l, (l+r)/2), get(a, b, 2*k+2, (l+r)/2, r));
    }
    int get(int a, int b) {
        return get(a, b, 0, 0, N);
    }
};

// Euler-Tour
const int MAXSIZE = 500020;
int BEGIN[MAXSIZE], END[MAXSIZE];
vector<int> euler_tour;
int K;
vector<vi> G;

void createEulerTour(int v, int p) {
    BEGIN[v] = K++;
    euler_tour.push_back(v);
    for (int el : G[v]) {
        if (el == p) continue;
        createEulerTour(el, v);
        euler_tour.push_back(v);
        K++;
    }
    END[v] = K;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;
    scanf("%d", &n);
    G.resize(n);
    segTree1 fi(2*n);
    segTree2 cl(2*n);
    for (int i = 0; i < n-1; i++) {
        int a, b;
        scanf("%d%d", &a, &b);
        a--; b--;
        G[a].push_back(b);
        G[b].push_back(a);
    }
    createEulerTour(0, -1);
    int q;
    scanf("%d", &q);
    for (int i = 0; i < q; i++) {
        int c, v;
        scanf("%d%d", &c, &v);
        v--;
        if (c == 1) {
            fi.update(BEGIN[v], END[v], i);
        } else if (c == 2) {
            cl.update(BEGIN[v], i);
        } else {
            if (fi.get(BEGIN[v]) > cl.get(BEGIN[v], END[v])) printf("1\n");
            else printf("0\n");
        }
    }
    return 0;
}