省选测试45

A 求和 (Unaccepted)

题目大意：

Code

Show Code

B 农民

题目大意：一颗二叉树，每个点左子树中的点只有点权比这个点小的才可能得到肥，右子树相反，修改一个点的点权，或翻转一个子树内所有点的左右儿子，询问一个点是否有肥

考虑一条向左的边会对这个子树内所有点产生一个最大值的限制，向右的相反，所以查询一个点的时候就看从这个点到跟这条链上所有的限制是否都能满足
所以线段树分别维护最大最小值限制的最大最小值，单点修改，翻转的时候就区间翻，把最大最小值的限制反过来就行

Code

Show Code

#include <cstdio>
#include <algorithm>
#define ls (rt << 1)
#define rs (rt << 1 | 1)
#define Get(x) (ch[fa[x]][1] == x)

using namespace std;
const int N = 1e5 + 5;

int read(int x = 0, int f = 1, char c = getchar()) {
    for (; c < '0' || c > '9'; c = getchar()) if (c == '-') f = -1;
    for (; c >='0' && c <='9'; c = getchar()) x = x * 10 + c - '0';
    return x * f;
}

bool v[N], tag[N*4];
int n, m, a[N], ch[N][2], rt;
int son[N], sz[N], fa[N], tp[N], dep[N], dfn[N], dfc, rk[N];

void Dfs(int x) {
    dep[x] = dep[fa[x]] + 1; sz[x] = 1;
    for (int i = 0, y; i <= 1; ++i) {
        if (!(y = ch[x][i])) continue;
        fa[y] = x; Dfs(y); sz[x] += sz[y];
        if (sz[son[x]] < sz[y]) son[x] = y;
    }
}

void Dfs(int x, int top) {
    tp[x] = top; dfn[x] = ++dfc; rk[dfc] = x;
    if (son[x]) Dfs(son[x], top);
    for (int i = 0, y; i <= 1; ++i)
        if ((y = ch[x][i]) && y != son[x]) Dfs(y, y);
}

struct Tree {
    int dl, xl, dr, xr;
}t[N*4];

Tree operator + (const Tree &a, const Tree &b) {
    Tree c = a;
    if (!c.dl) c.dl = b.dl, c.xl = b.xl;
    else if (b.dl) c.dl = max(c.dl, b.dl), c.xl = min(c.xl, b.xl);
    if (!c.dr) c.dr = b.dr, c.xr = b.xr;
    else if (b.dr) c.dr = max(c.dr, b.dr), c.xr = min(c.xr, b.xr);
    return c;
}

void Update(int rt) {
    tag[rt] ^= 1;
    swap(t[rt].dl, t[rt].dr); 
    swap(t[rt].xl, t[rt].xr);
}

void Pushdown(int rt) {
    if (!tag[rt]) return; 
    tag[rt] = 0; Update(ls); Update(rs);
}

void Build(int rt, int l, int r) {
    if (l == r) {
        if (Get(rk[l])) t[rt].dl = t[rt].xl = a[fa[rk[l]]];
        else t[rt].dr = t[rt].xr = a[fa[rk[l]]];
        return;
    }
    int mid = l + r >> 1;
    Build(ls, l, mid); Build(rs, mid+1, r);
    t[rt] = t[ls] + t[rs];
}

void Modify(int rt, int l, int r, int x) {
    if (l == r) {
        if (t[rt].dl) t[rt].dl = t[rt].xl = a[fa[rk[l]]];
        else t[rt].dr = t[rt].xr = a[fa[rk[l]]];
        return;
    }
    int mid = l + r >> 1; Pushdown(rt);
    if (x <= mid) Modify(ls, l, mid, x);
    else Modify(rs, mid + 1, r, x);
    t[rt] = t[ls] + t[rs];
}

void Reverse(int rt, int l, int r, int x, int y) {
    if (x <= l && r <= y) return Update(rt);
    int mid = l + r >> 1; Pushdown(rt);
    if (x <= mid) Reverse(ls, l, mid, x, y);
    if (y >  mid) Reverse(rs,mid+1,r, x, y);
    t[rt] = t[ls] + t[rs];
}

Tree Ask(int rt, int l, int r, int x, int y) {
    if (x <= l && r <= y) return t[rt];
    int mid = l + r >> 1; Pushdown(rt);
    Tree ans = (Tree) {0, 0, 0, 0};
    if (x <= mid) ans = ans + Ask(ls, l, mid, x, y);
    if (y >  mid) ans = ans + Ask(rs,mid+1,r, x, y);
    return ans;
}

int main() {
    //freopen("IN", "r", stdin);
    freopen("farmer.in", "r", stdin);
    freopen("farmer.out", "w", stdout);
    n = read(); m = read();
    for (int i = 1; i <= n; ++i) {
        a[i] = read(); 
        ch[i][0] = read(); ch[i][1] = read();
        v[ch[i][0]] = v[ch[i][1]] = 1;
    }
    for (int i = 1; i <= n; ++i)
        if (!v[i]) rt = i;
    Dfs(rt); Dfs(rt, rt); Build(1, 1, n);
    while (m--) {
        int od = read(), x = read();
        if (od == 1) {
            a[x] = read();
            if (ch[x][0]) Modify(1, 1, n, dfn[ch[x][0]]);
            if (ch[x][1]) Modify(1, 1, n, dfn[ch[x][1]]);
        }
        else if (od == 2) {
            int l = dfn[x] + 1, r = dfn[x] + sz[x] - 1;
            if (l <= r) Reverse(1, 1, n, l, r);
        }
        else {
            int w = a[x]; Tree ans = (Tree) {0, 0, 0, 0};
            while (tp[x] != 1)
                ans = ans + Ask(1, 1, n, dfn[tp[x]], dfn[x]), x = fa[tp[x]];
            if (dfn[x] != 1) ans = ans + Ask(1, 1, n, 2, dfn[x]);
            puts(w > ans.dl && (w < ans.xr || !ans.xr) ? "YES" : "NO");
        }
    }
    return 0;
}

C 仙人掌

题目大意：

Code

Show Code