Codeforces 343D 线段树

水深无声 2021-12-12 01:59 229阅读 0赞

题意：给你一颗以点1为根的数，有两种操作，一种是把x及其子树的所有点都灌满水，一种是把x及其所有祖先都放空水，一种是询问，问某个点里有没有水？

思路：看网上大多数是树剖，但实际上5e5的数据树剖还是有点慌的。。。我只用了线段树。我们发现，只要一个点被清空之后，如果没有灌水，那么这个点将一直是空的。同理，如果这个点被灌满水后一直不是空的，那么它将一直是满的，所以，这个点的状态实际取决于离查询时间最近的是放水还是灌水。我们可以用线段树来维护这个，我们首先来维护灌水时间，这个在dfs序后用线段树的区间操作，很好完成。那么放水呢？我们换个思维，清空这个点及其祖先，反过来说，如果这个点被清空了，那么一定是它的子树中的某个点被清空了，所以我们可以用线段树查询它被清空的最晚时间，与之前的操作比较，如果清空操作较晚，那么这个点就是空的，否则就是满的。

代码：

#include <bits/stdc++.h>
    #define LL long long
    #define INF 0x3f3f3f3f
    #define db double
    #define pii pair<int, int>
    #define ls (x << 1)
    #define rs ((x << 1) | 1)
    using namespace std;
    const int maxn = 500010;
    int a[maxn];
    int dfn[maxn], tot, sz[maxn];
    vector<int> G[maxn];
    struct node {
    	int add, del;
    	int lz;
    };
    node tr[maxn * 4];
    void add(int x, int y) {
    	G[x].push_back(y);
    	G[y].push_back(x);
    }
    void pushup(int x) {
    	tr[x].del = max(tr[ls].del, tr[rs].del);
    }
    void maintain(int x, int y) {
    	tr[x].add = y;
    	tr[x].lz = y;
    }
    void pushdown(int x) {
    	if(tr[x].lz != -1) {
    		maintain(ls, tr[x].lz);
    		maintain(rs, tr[x].lz);
    		tr[x].lz = -1;
    	}
    }
    void build(int x, int l, int r) {
    	if(l == r) {
    		tr[x].lz = -1;
    		return;
    	}
    	int mid = (l + r) >> 1;
    	build(ls, l, mid);
    	build(rs, mid + 1, r);
    	pushup(x);
    }
    void add1(int x, int l, int r, int ql ,int qr, int val) {
    	if(l >= ql && r <= qr) {
    		maintain(x, val);
    		return;
    	}
    	pushdown(x);
    	int mid = (l + r) >> 1;
    	if(ql <= mid) add1(ls, l, mid, ql, qr, val);
    	if(qr > mid) add1(rs, mid + 1, r, ql, qr, val);
    	pushup(x);
    }
    void add2(int x, int l, int r, int pos, int val) {
    	if(l == r) {
    		tr[x].del = val;
    		return;
    	}
    	pushdown(x);
    	int mid = (l + r) >> 1;
    	if(pos <= mid) add2(ls, l, mid, pos, val);
    	else add2(rs, mid + 1, r, pos, val);
    	pushup(x);
    }
    int query1(int x, int l, int r, int pos) {
    	if(l == r) return tr[x].add;
    	pushdown(x);
    	int mid = (l + r) >> 1;
    	if(pos <= mid) return query1(ls, l, mid, pos);
    	else return query1(rs, mid + 1, r, pos);
    }
    int query2(int x, int l, int r, int ql, int qr) {
    	if(l >= ql && r <= qr) return tr[x].del;
    	pushdown(x);
    	int mid = (l + r) >> 1;
    	int ans = 0;
    	if(ql <= mid) ans = max(ans, query2(ls, l, mid, ql, qr));
    	if(qr > mid) ans = max(ans, query2(rs, mid + 1, r, ql, qr));
    	return ans;
    } 
    void dfs(int x, int fa) {
    	dfn[x] = ++tot;
    	sz[x] = 1;
    	for (auto y : G[x]) {
    		if(y == fa) continue;
    		dfs(y, x);
    		sz[x] += sz[y];
    	}
    }
    int main() {
    	int n, m, x, y;
    	scanf("%d", &n);
    	for (int i = 1; i < n; i++) {
    		scanf("%d%d", &x, &y);
    		add(x, y);
    	}
    	dfs(1, -1);
    	build(1, 1, n);
    	scanf("%d", &m);
    	for(int i = 1; i <= m; i++) {
    		scanf("%d%d", &x, &y);
    		if(x == 1) {
    			add1(1, 1, n, dfn[y], dfn[y] + sz[y] - 1, i);
    		} else if(x == 2) {
    			add2(1, 1, n, dfn[y], i);
    		} else {
    			int tmp1 = query1(1, 1, n, dfn[y]), tmp2 = query2(1, 1, n, dfn[y], dfn[y] + sz[y] - 1);
    			if(tmp1 <= tmp2) printf("0\n");
    			else printf("1\n");
    		}
    	}
    }

转载于:https://www.cnblogs.com/pkgunboat/p/10952821.html