31pts 求调

P3038 [USACO11DEC] Grass Planting G

BalanceSegment @ 2023-07-25 14:28:40

板子是直接从上一题改过来的,所以一些写法很怪。

不知道是不是写法的原因。

#include <bits/stdc++.h>
#define lc id << 1
#define rc id << 1 | 1
using namespace std;
const int maxn = 2e5 + 10;
int h[maxn * 2], nxt[maxn * 2], to[maxn * 2], w[maxn * 2];
int st[maxn], ed[maxn];
int dfn[maxn], top[maxn], siz[maxn];
int fa[maxn], son[maxn], va[maxn], val[maxn], dep[maxn];
int n, m, cnt, cur;
void add(int u, int v, int val) {
    to[++cnt] = v;
    nxt[cnt] = h[u];
    h[u] = cnt;
    w[cnt] = val;
}
void dfs1(int x, int f){
    fa[x] = f;
    siz[x] = 1;
    dep[x] = dep[f] + 1;
    int sz = -1;
    for(int i = h[x]; i; i = nxt[i]) {
        int v = to[i];
        if(v == f) continue;
        va[v] = w[i];
        dfs1(v, x);
        siz[x] += siz[v];
        if(sz < siz[v])
            sz = siz[v], son[x] = v;
    }
}
void dfs2(int x, int t) {
    top[x] = t;
    dfn[x] = ++cur;
    val[cur] = va[x];
    if(!son[x]) return;
    dfs2(son[x], t);
    for(int i = h[x]; i; i = nxt[i]) {
        int v = to[i];
        if(v == fa[x] || v == son[x])
            continue;
        dfs2(v, v);
    }
}
struct Seg {
    struct node{
        int l, r;
        int sum, laz;
    }a[maxn * 4];
    void maintain(int id) {
        a[id].sum = a[lc].sum + a[rc].sum;
    }
    void maketag(int id) {
        a[id].laz = 1;
        a[id].sum += (a[id].r - a[id].l + 1);
    }
    void pushdown(int id) {
        if(!a[id].laz) return;
        maketag(lc);
        maketag(rc);
        a[id].laz = 0;
    }
    void build(int id, int l, int r) {
        a[id].l = l;
        a[id].r = r;
        if(l == r) {
            a[id].sum = 0;
            return;
        }
        int mid = (l + r) >> 1;
        build(lc, l, mid);
        build(rc, mid + 1, r);
        maintain(id);
    }
    void modify(int id, int l, int r) {
        if(a[id].l >= l && a[id].r <= r) {
            maketag(id);
            return;
        }
        pushdown(id);
        int mid = (a[id].l + a[id].r) >> 1;
        if(l <= mid) modify(lc, l, r);
        if(mid < r) modify(rc, l, r);
        maintain(id);
    }
    int qsum(int id, int l, int r) {
        if(a[id].l >= l && a[id].r <= r)
            return a[id].sum;
        pushdown(id);
        int ret = 0;
        int mid = (a[id].l + a[id].r) >> 1;
        if(l <= mid) ret += qsum(lc, l, r);
        if(mid < r) ret += qsum(rc, l, r);
        return ret;
    }
}T;
int getsum(int x, int y) {
    int ret = 0;
    while(top[x] != top[y]) {
        if(dep[top[x]] < dep[top[y]])
            swap(x, y);
        ret += T.qsum(1, dfn[top[x]], dfn[x]);
        x = fa[top[x]];
    }
    if(dep[x] < dep[y]) swap(x, y);
    ret += T.qsum(1, dfn[y] + 1, dfn[x]);
    return ret;
}
void change(int x, int y) {
    while(top[x] != top[y]) {
        if(dep[top[x]] < dep[top[y]])
            swap(x, y);
        T.modify(1, dfn[top[x]], dfn[x]);
        x = fa[top[x]];
    }
    if(dep[x] < dep[y]) swap(x, y);
    T.modify(1, dfn[y] + 1, dfn[x]);
}
int main() {
    char opt;
    cin >> n >> m;
    for(int i = 1, u, v; i < n; i++) {
        cin >> u >> v;
        add(u, v, 0);
        add(v, u, 0);
    }
    dfs1(1, 0);
    dfs2(1, 1);
    T.build(1, 1, n);
    int u, v;
    while(m--){
        cin >> opt >> u >> v;
        if(opt == 'P') change(u, v);
        if(opt == 'Q') cout << getsum(u, v) << endl;
    }
    return 0;
}

by MAZHIYUAN @ 2023-11-16 16:31:02

void maketag(int id) {
        a[id].laz = 1;
        a[id].sum += (a[id].r - a[id].l + 1);
    }

应该改为

void maketag(int id) {
        a[id].laz += 1;
        a[id].sum += (a[id].r - a[id].l + 1);
    }

因为懒标记可能被更新不止一次

附hack数据

in

6 3
1 2
1 3
3 4
4 5
5 6
P 3 6
P 3 6
Q 5 6

out

2

by MAZHIYUAN @ 2023-11-16 17:00:50

还有pushdown不能共用maketag函数,应改为

void pushdown(int id) {
    if(!a[id].laz) return;
    a[lc].sum += (a[lc].r - a[lc].l + 1) * a[id].laz;
    a[rc].sum += (a[rc].r - a[rc].l + 1) * a[id].laz;
    a[lc].laz += a[id].laz;
    a[rc].laz += a[id].laz;
    a[id].laz = 0;
}

改完就过了


|