树剖模板求调 马蜂良好

Luo_Saisei @ 2024-08-20 22:09:58

#include <array>
#include <bits/stdc++.h>
using namespace std;
const int N = 4E5;
int head[N], nxt[N], to[N], cnt, n, m, rt, p, op, x, y, v, a[N], size[N], dep[N], fa[N], son[N], top[N], seg[N], rnk[N];
#define add_edge(u, v) nxt[++cnt] = head[u], head[u] = cnt, to[cnt] = v, nxt[++cnt] = head[u], head[u] = cnt, to[cnt] = v
void dfs1(int u, int f, int depth) {
    dep[u] = depth, fa[u] = f, size[u] = 1;
    for (int i = head[u]; i; i = nxt[i]) {
        if (to[i] == f) continue;
        dfs1(to[i], u, depth + 1), size[u] += size[to[i]];
        if (size[to[i]] > size[son[u]]) son[u] = to[i];
    }
}
void dfs2(int u, int tp) {
    if (son[u]) seg[son[u]] = ++seg[0], top[son[u]] = top[u], rnk[seg[0]] = son[u], dfs2(son[u], u);
    for (int i = head[u]; i; i = nxt[i])
        if (!top[to[i]]) seg[to[i]] = ++seg[0], rnk[seg[0]] = to[i], top[to[i]] = to[i], dfs2(to[i], u);
}
struct tree {
    int l, r, val, add;
} tr[N];
#define pushup(u) tr[u].val = (tr[u << 1].val + tr[u << 1 | 1].val + p) % p
#define mid (tr[u].l + tr[u].r) >> 1
void change(int u, int val) { tr[u].val = (tr[u].val + (tr[u].r - tr[u].l + 1) * val % p+p) % p, tr[u].add = (tr[u].add + val % p+p) % p; }
void pushdown(int u) {
    if (tr[u].add) change(u << 1, tr[u].add), change(u << 1 | 1, tr[u].add), tr[u].add = 0;
}
void build(int u, int l, int r) {
    if (l == r)
        tr[u] = tree { l, r, a[rnk[l]], 0 };
    else {
        tr[u] = tree { l, r };
        int mmid = (l + r) >> 1;
        build(u << 1, l, mmid), build(u << 1 | 1, mmid + 1, r), pushup(u);
    }
}
void modify(int u, int l, int r, int val) {
    if (tr[u].l >= l && tr[u].r <= r) {
        change(u, val);
    } else {
        pushdown(u);
        if (l <= mid) modify(u << 1, l, r, val);
        if (r > mid) modify(u << 1 | 1, l, r, val);
        pushup(u);
    }
}
int query(int u,int l,int r)
{
    int ans=0;
    if(tr[u].l>=l&&tr[u].r<=r)
    {
        return tr[u].val%p;
    }
    else{
        pushup(u);
        if(l<=mid) ans=(ans+query(u<<1, l, r)%p+p)%p;
        if(r>mid) ans=(ans+query(u<<1|1,l,r)%p+p);
        return ans%p;
    }
}
void tree_add(int x,int y,int val)
{
    while(top[x]!=top[y])
    {
        if(dep[x]<dep[y]) swap(x, y);
        modify(1, seg[top[x]], seg[x], val),x=fa[top[x]];
    }
    if(dep[x]>dep[y]) swap(x,y);
    modify(1, seg[x], seg[y], val);
}
int tree_query(int x,int y)
{
    int ans=0;
    while(top[x]!=top[y]){
        if(dep[x]<dep[y]) swap(x,y);
        ans=(ans+query(1, seg[top[x]], seg[x])%p+p)%p;
    }
    if(dep[x]>dep[y]) swap(x,y);
    ans=(ans+query(1, seg[x], seg[y])%p+p)%p;
    return ans;
}
int main() {
    cin >> n >> m >> rt >> p;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i < n; i++) cin >> x >> y, add_edge(x, y);
    dfs1(rt, 0, 1);
    dfs2(rt, rt);
    build(1, 1, n);
    while (m--) {
        cin >> op;
        if(op==1) cin>>x>>y>>v,tree_add(x, y, v%p);
        else if(op==2) cin>>x>>y,cout<<tree_query(x, y)<<endl;
        else if(op==3) cin>>x>>y,modify(1, seg[x], seg[x]+size[x]-1,y%p);
        else if(op==4) cin>>x,cout<<query(1, seg[x], seg[x]+size[x]-1)<<endl;
    }
}

by 142857tree @ 2024-08-20 22:33:03

树剖往上跳的时候比较的是 x 和 y 的 top 的深度

by Luo_Saisei @ 2024-08-20 22:46:52

基本全RE

by Luo_Saisei @ 2024-08-20 22:47:03

@142857tree

by Walter_Fang @ 2024-08-20 22:53:46

@gcomplex 本地都过不了，if (tr[u].l >= l && tr[u].r <= r) {这一行 RE。

by Luo_Saisei @ 2024-08-20 22:57:51

@Walter_Fang 嗯 我知道 所以想知道为啥

by Walter_Fang @ 2024-08-20 23:07:00

@gcomplex 范围问题吧

by 142857tree @ 2024-08-20 23:12:08

好像连边define那里写错了

by Luo_Saisei @ 2024-08-20 23:15:46

@Walter_Fang 改完范围就变TLE了/kk

by Luo_Saisei @ 2024-08-20 23:16:21

#include <array>
#include <bits/stdc++.h>
using namespace std;
const int N = 4E6;
int head[N], nxt[N], to[N], cnt, n, m, rt, p, op, x, y, v, a[N], size[N], dep[N], fa[N], son[N], top[N], seg[N], rnk[N];
#define add_edge(u, v) nxt[++cnt] = head[u], head[u] = cnt, to[cnt] = v, nxt[++cnt] = head[v], head[v] = cnt, to[cnt] = u
void dfs1(int u, int f, int depth) {
    dep[u] = depth, fa[u] = f, size[u] = 1;
    for (int i = head[u]; i; i = nxt[i]) {
        if (to[i] == f) continue;
        dfs1(to[i], u, depth + 1), size[u] += size[to[i]];
        if (size[to[i]] > size[son[u]]) son[u] = to[i];
    }
}
void dfs2(int u, int tp) {
    if (son[u]) seg[son[u]] = ++seg[0], top[son[u]] = top[u], rnk[seg[0]] = son[u], dfs2(son[u], u);
    for (int i = head[u]; i; i = nxt[i])
        if (!top[to[i]]) seg[to[i]] = ++seg[0], rnk[seg[0]] = to[i], top[to[i]] = to[i], dfs2(to[i], u);
}
struct tree {
    int l, r, val, add;
} tr[N];
void pushup(int u) { tr[u].val = (tr[u << 1].val + tr[u << 1 | 1].val + p) % p; }
void change(int u, int val) { tr[u].val = (tr[u].val + (tr[u].r - tr[u].l + 1) * val % p + p) % p, tr[u].add = (tr[u].add + val % p + p) % p; }
void pushdown(int u) {
    if (tr[u].add) change(u << 1, tr[u].add), change(u << 1 | 1, tr[u].add), tr[u].add = 0;
}
void build(int u, int l, int r) {
    if (l == r)
        tr[u] = tree { l, r, a[rnk[l]], 0 };
    else {
        tr[u] = tree { l, r };
        int mmid = (l + r) >> 1;
        build(u << 1, l, mmid), build(u << 1 | 1, mmid + 1, r), pushup(u);
    }
}
void modify(int u, int l, int r, int val) {
    if(tr[u].r<l||tr[u].l>r) return ;
    if (tr[u].l >= l && tr[u].r <= r) {
        change(u, val);
    } else {
        int mid=(tr[u].l + tr[u].r) >> 1;
        pushdown(u);
        if (l <= mid) modify(u << 1, l, r, val);
        if (r > mid) modify(u << 1 | 1, l, r, val);
        pushup(u);
    }
}
int query(int u, int l, int r) {
    int ans = 0;
    if(tr[u].r<l||tr[u].l>r) return ans;
    if (tr[u].l >= l && tr[u].r <= r) {
        return tr[u].val % p;
    } else {
        pushdown(u);
        int mid=(tr[u].l + tr[u].r) >> 1;
        if (l <= mid) ans += (ans + query(u << 1, l, r) % p + p) % p;
        if (r > mid) ans += (ans + query(u << 1 | 1, l, r) % p + p);
        pushup(u);
    }
    return ans % p;
}
void tree_add(int x, int y, int val) {
    while (top[x] != top[y]) {
        if (dep[top[x]] < dep[top[y]]) swap(x, y);
        modify(1, seg[top[x]], seg[x], val), x = fa[top[x]];
    }
    if (dep[x] > dep[y]) swap(x, y);
    modify(1, seg[x], seg[y], val);
}
int tree_query(int x, int y) {
    int ans = 0;
    while (top[x] != top[y]) {
        if (dep[top[x]] < dep[top[y]]) swap(x, y);
        ans = (ans + query(1, seg[top[x]], seg[x]) % p + p) % p;
    }
    if (dep[x] > dep[y]) swap(x, y);
    ans = (ans + query(1, seg[x], seg[y]) % p + p) % p;
    return ans;
}
int main() {
    cin >> n >> m >> rt >> p;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i < n; i++) cin >> x >> y, add_edge(x, y);
    dfs1(rt, 0, 1);
    dfs2(rt, rt);
    build(1, 1, n);
    while (m--) {
        cin >> op;
        if (op== 1)
            cin >> x >> y >> v, tree_add(x, y, v % p);
        else if (op == 2)
            cin >> x >> y, cout << tree_query(x, y) << endl;
        else if (op == 3)
            cin >> x >> y, modify(1, seg[x], seg[x] + size[x] - 1, y % p);
        else if (op == 4) 
            cin >> x, cout << query(1, seg[x], seg[x] + size[x] - 1) << endl;
    }
}

by Luo_Saisei @ 2024-08-20 23:16:55

最新一版 连边和判有无交集都改了 现在是TLE 本地都T