P4315 题解

· · 题解

这道题本人用了 8h13min 才过……其中线段树用时 7h+ 且没有 AC。改成分块之后只用 1h 就过了，分块实在是太好写太好调了，甚至用时还比线段树低了四分之一。

首先肯定是树剖，剖出来之后再考虑数据结构维护。要求：

有很多种数据结构可以，在这里我介绍一下分块。

分块，就是把数据分成 \sqrt n 个块，每个块有 \sqrt n 个元素。这道题需要维护每个块的块内最大值、设值懒标记、加和懒标记。

区间设值我们可以把区间分成三个部分：最左边的一个块，最右边的一个块，中间的所有块。对于两边的块显然可以暴力修改。对于中间的所有块，我们修改其设值懒标记即可。

区间加和类似，只不过如果有设值懒标记，就修改设值懒标记，否则修改加和标记。

查询直接暴力两边的块，然后中间的就用处理出来的块内最大值就可以了。

注意整个块修改之后是可以直接求出修改后最大值的。加和的话就把最大值加上 w；设值就把最大值设为 w。

这道题就做完了，分块就是那么简单。

时间复杂度 O(n+q\sqrt n\log n)，加上树剖和分块的微弱常数，是可以过去的（还比线段树快不少）。

代码如下：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define MAXN 100001
#define MAXM 320

int n, u, v, w, cnt, len, tot;
int us[MAXN], vs[MAXN], id[MAXN], ta[MAXN], a[MAXN], bl[MAXN];
int dep[MAXN], son[MAXN], siz[MAXN], fa[MAXN], top[MAXN];
int L[MAXM], R[MAXM], maxn[MAXM], tag1[MAXM], tag2[MAXM];
string opt;

struct Edge{
    int v, w;
};
vector<Edge> e[MAXN];

void dfs1(int x, int f){
    fa[x] = f;
    dep[x] = dep[f] + 1;
    siz[x] = 1;
    for (auto i: e[x]){
        int v(i.v);
        if (v != f){
            ta[v] = i.w;
            dfs1(v, x);
            siz[x] += siz[v];
            if (siz[son[x]] < siz[v]) son[x] = v;
        }
    }
}

void dfs2(int x, int tp){
    top[x] = tp;
    id[x] = ++cnt;
    a[cnt] = ta[x];
    if (!son[x]) return;
    dfs2(son[x], tp);
    for (auto i: e[x]){
        int v(i.v);
        if (v != fa[x] && v != son[x]) dfs2(v, v);
    }
}

void init(){
    len = sqrt(n);
    tot = (n-1)/len+1;
    for (int i(1); i<=tot; ++i){
        L[i] = R[i-1] + 1;
        R[i] = i * len;
    }
    R[tot] = n;

    for (int i(1); i<=tot; ++i){
        tag1[i] = LLONG_MAX;
        maxn[i] = LLONG_MIN;
        for (int j(L[i]); j<=R[i]; ++j){
            maxn[i] = max(maxn[i], a[j]);
            bl[j] = i;
        }
    }
}

void push_up(int p){
    maxn[p] = LLONG_MIN;
    for (int i(L[p]); i<=R[p]; ++i) maxn[p] = max(maxn[p], a[i]);
}

void push_down(int p){
    if (tag1[p] != LLONG_MAX){
        for (int i(L[p]); i<=R[p]; ++i) a[i] = tag1[p];
        tag1[p] = LLONG_MAX;
        tag2[p] = 0;
    }
    if (tag2[p]){
        for (int i(L[p]); i<=R[p]; ++i) a[i] += tag2[p];
        tag2[p] = 0;
    }
}

void modify1(int l, int r, int k){
    if (l > r) return;
    int p(bl[l]), q(bl[r]);
    if (p == q){
        push_down(p);
        for (int i(l); i<=r; ++i) a[i] = k;
        push_up(p);
        return;
    }

    push_down(p);
    for (int i(l); i<=R[p]; ++i) a[i] = k;
    push_up(p);
    for (int i(p+1); i<q; ++i) tag1[i] = maxn[i] = k;
    push_down(q);
    for (int i(L[q]); i<=r; ++i) a[i] = k;
    push_up(q);
}

void modify2(int l, int r, int k){
    if (l > r) return;
    int p(bl[l]), q(bl[r]);
    if (p == q){
        push_down(p);
        for (int i(l); i<=r; ++i) a[i] += k;
        push_up(p);
        return;
    }

    push_down(p);
    for (int i(l); i<=R[p]; ++i) a[i] += k;
    push_up(p);
    for (int i(p+1); i<q; ++i){
        if (tag1[i] != LLONG_MAX) tag1[i] += k;
        else tag2[i] += k;
    }
    push_down(q);
    for (int i(L[q]); i<=r; ++i) a[i] += k;
    push_up(q);
}

int query1(int l, int r){
    if (l > r) return LLONG_MIN;
    int p(bl[l]), q(bl[r]), ans(LLONG_MIN);
    if (p == q){
        push_down(p);
        for (int i(l); i<=r; ++i) ans = max(ans, a[i]);
        return ans;
    }

    push_down(p);
    for (int i(l); i<=R[p]; ++i) ans = max(ans, a[i]);
    for (int i(p+1); i<q; ++i) ans = max(ans, maxn[i]);
    push_down(q);
    for (int i(L[q]); i<=r; ++i) ans = max(ans, a[i]);
    return ans;
}

void modify3(int x, int y, int k){
    while (top[x] != top[y]){
        if (dep[top[x]] < dep[top[y]]) swap(x, y);
        modify1(id[top[x]], id[x], k);
        x = fa[top[x]];
    }
    if (dep[x] > dep[y]) swap(x, y);
    modify1(id[x]+1, id[y], k);
}

void modify4(int x, int y, int k){
    while (top[x] != top[y]){
        if (dep[top[x]] < dep[top[y]]) swap(x, y);
        modify2(id[top[x]], id[x], k);
        x = fa[top[x]];
    }
    if (dep[x] > dep[y]) swap(x, y);
    modify2(id[x]+1, id[y], k);
}

int query2(int x, int y){
    int res(LLONG_MIN);
    while (top[x] != top[y]){
        if (dep[top[x]] < dep[top[y]]) swap(x, y);
        res = max(res, query1(id[top[x]], id[x]));
        x = fa[top[x]];
    }
    if (dep[x] > dep[y]) swap(x, y);
    return max(res, query1(id[x]+1, id[y]));
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> n;
    for (int i(1); i<n; ++i){
        cin >> u >> v >> w;
        e[u].push_back({v, w});
        e[v].push_back({u, w});
        us[i] = u;
        vs[i] = v;
    }
    dfs1(1, 0);
    dfs2(1, 1);
    init();

    while (cin >> opt){
        if (opt == "Stop") return 0;
        cin >> u >> v;
        if (opt == "Change"){
            if (dep[us[u]] < dep[vs[u]]) modify1(id[vs[u]], id[vs[u]], v);
            else modify1(id[us[u]], id[us[u]], v);
        }else if (opt == "Cover"){
            cin >> w;
            modify3(u, v, w);
        }else if (opt == "Add"){
            cin >> w;
            modify4(u, v, w);
        }else cout << query2(u, v) << '\n';
    }

    return 0;
}