首页 > 其他分享 >洛谷 P3976 [TJOI2015] 旅游

洛谷 P3976 [TJOI2015] 旅游

时间：2024-01-31 22:12:30浏览次数：24  
标签：洛谷 val P3976 int max top dfn TJOI2015 Query

这出题人语言表达能力真的感人……

希望你们看完这篇题解后不要觉得我的语言表达能力和出题人不相上下。

题目大意

给定一棵有点权的树，每次询问从 \(u\) 到 \(v\) 的路径上后经过的点权减去先经过的点权的最大值，再把这条路径上所有点的点权加上一个给定的数。

分析

俗话说得好：如果你觉得一个树上的题很难，那就先把它扔到序列上。

于是有如下两个子问题：

  1. 给定序列，每次询问在 \(l\) 到 \(r\) 的区间内从左向右选两个数，令选的左边的数作为进价，右边的数作为售价，要求利润（售价减进价）最大值。
  2. 给定序列，每次询问在 \(l\) 到 \(r\) 的区间内从右向左选两个数，令选的右边的数作为进价，左边的数作为售价，要求利润（售价减进价）最大值。

考虑子问题 1。显然可以线段树，维护区间最大收益。线段树上一个区间内的最大收益无非三种情况：

  1. 在左儿子的区间内买进且卖出，这种情况左儿子已经维护了；
  2. 在右儿子的区间内买进且卖出，这种情况右儿子已经维护了；
  3. 左儿子的区间内买，右儿子的区间内卖。这种情况需要自己推：右儿子中最大值减去左儿子中最小值。

如果是子问题 2 的话就改一下第 3 种情况：右儿子的区间内买，左儿子的区间内卖，这种情况的收益也变为左儿子中最大值减去右儿子中最小值。

第三种情况需要左右儿子内区间最小值，于是再用线段树维护区间极值。
这样每次询问时在线段树上查询，若一次查询同时递归了左右两个儿子，那就像刚才讨论的那样合并左右儿子的答案。

int Query_val(int o, int l, int r, int L, int R, int dir) { // dir 代表从左往右或从右往左
    if (L * R == 0) 
        return 0;
    if (L <= l && r <= R) 
        return val[dir][o]; // val 是二维数组，分别记录从左往右和从右往左
    pushdown(o);
    int mid = l + r >> 1, sl = 0, sr = 0, ret = 0;
    if (L <= mid) 
        ret = Query_val(o << 1, l, mid, L, R, dir), sl = 1;
    if (R > mid) 
        ret = max(ret, Query_val(o << 1 | 1, mid + 1, r, L, R, dir)), sr = 1;
    if (sl && sr) { // 同时递归了左右儿子，合并答案
        ret = max(ret, 
            !dir ? 
            Query_max(1, 1, N, mid + 1, R) - Query_min(1, 1, N, L, mid) : // 从左往右合并答案
            Query_max(1, 1, N, L, mid) - Query_min(1, 1, N, mid + 1, R)); // 从右往左合并答案
    }
    return ret;
}

序列上的子问题解决了，接下来来到树上。

正片开始。

为了方便，接下来所说的顺树贸易是指买进处比卖出处更接近根，逆树贸易是指卖出处比买进处更靠近根。不难看出子问题 1 实际上是顺树贸易，子问题 2 是逆树贸易。

既然用了树剖，那树上的一条条链就可以类比成线段树上的一个个区间，跳链时就要维护从出发点到当前点的最优贸易。以下设询问的路径起始点为 \(u\)，终点为 \(v\)，\(x\) 从 \(u\) 开始跳，\(y\) 从 \(v\) 开始跳。

以下分类讨论 \(x\) 跳链与 \(y\) 跳链：

假设 \(x\) 刚才跳过一条链。沿用合并区间答案的思想，在合并两条链上的答案的时候，将链看成区间，将 \(x\) 现所在链顶 \(t\) 与 \(u\) 之间的路径视为当前区间，显然这条路径上有两条链。随后将 \(u\) 到 \(x\)（不含）之间的路径视为当前区间的左儿子，\(x\) 到 \(t\) 之间的路径视为右儿子，按子问题 2（逆树贸易）的方式合并区间答案即可。

假设 \(x\) 还没跳过链，那就先让 \(x\) 跳链，随后初始化 \(u\) 到 \(x\) 的路径上的最优贸易与最小值。

第一次跳链之后，\(u\) 到 \(x\)（不含）之间的路径上的最优贸易与最小值就可以让 \(x\) 一边跳一边维护。

\(y\) 的跳链与 \(x\) 类似，还是把 \(y\) 当前所在链顶 \(t\) 到 \(v\) 的路径视为当前区间，只不过要将 \(t\) 到 \(y\) 之间的路径视为左儿子，\(y\)（不含）到 \(v\) 的区间视为右儿子，然后按子问题 1（顺树贸易）的方式合并答案。如果没跳过链的话就先让 \(y\) 跳，再初始化 \(y\)（不含）到 \(v\) 之间的最优贸易与最大值。在那之后也是一样边跳边维护。

    while (top[x] != top[y]) {
        if (dep[top[x]] > dep[top[y]]) {
            if (xton == inf) {
                xret = max(xret, Query_val(1, 1, N, dfn[top[x]], dfn[x], 1));
                xton = Query_min(1, 1, N, dfn[top[x]], dfn[x]);
            } else {
                xret = max(xret, max(Query_val(1, 1, N, dfn[top[x]], dfn[x], 1), 
                    Query_max(1, 1, N, dfn[top[x]], dfn[x]) - xton));
                xton = min(xton, Query_min(1, 1, N, dfn[top[x]], dfn[x]));
            }
            x = f[top[x]];
        } else {
            if (yton == -inf) {
                yret = max(yret, Query_val(1, 1, N, dfn[top[y]], dfn[y], 0));
                yton = Query_max(1, 1, N, dfn[top[y]], dfn[y]);
            } else {
                yret = max(yret, max(Query_val(1, 1, N, dfn[top[y]], dfn[y], 0), 
                    yton - Query_min(1, 1, N, dfn[top[y]], dfn[y])));
                yton = max(yton, Query_max(1, 1, N, dfn[top[y]], dfn[y]));
            }
            y = f[top[y]];
        }
    }

那么这样 \(x\) 和 \(y\) 就来到了同一条链上。在这里有四种情况：

  1. \(x\) 和 \(y\) 都没跳过链；
  2. \(x\) 没跳过链，\(y\) 跳过链；
  3. \(x\) 跳过链，\(y\) 没跳过链；
  4. \(x\) 和 \(y\) 都跳过链。

为了代码方便，在分类讨论之后会统一让 \(x\) 和 \(y\) 各跳链至少一次（可能会只跳某条链的一部分）使其汇合与一点 \(p\)，并合并 \(u\) 到 \(p\) 与 \(p\) 到 \(v\) 的答案。

第 1 种情况没什么好讨论的，就是 \(u\) 和 \(v\) 在同一条链上。函数可以直接返回 \(u\) 到 \(v\) 的答案。注意是顺树贸易还是逆树贸易。

第 2 种情况里有两种情况：

  1. \(x\) 的深度比 \(y\) 的深度大。此时让 \(x\) 向上跳到 \(y\)，做一个逆树贸易，并维护 \(u\) 到 \(x\) 的信息；
  2. \(x\) 的深度比 \(y\) 的深度小。此时让 \(x\) 向下跳到 \(y\)，做一个顺树贸易，并维护 \(u\) 到 \(x\) 的信息。

第 3 种情况里也有两种情况：

  1. \(x\) 的深度比 \(y\) 的深度大。此时让 \(y\) 向下跳到 \(x\)（\(x\) 相对于 \(y\) 向上跳），做一个逆树贸易，并维护 \(y\) 到 \(v\) 的信息；
  2. \(x\) 的深度比 \(y\) 的深度小。此时让 \(y\) 向上跳到 \(x\)（\(x\) 相对于 \(y\) 向下跳），做一个顺树贸易，并维护 \(y\) 到 \(v\) 的信息。

至于第 4 种情况，因为 \(x\) 和 \(y\) 都跳过链了，所以谁往哪跳都无所谓。不过我个人还是倾向于让它们汇聚在它们的 \(lca\) 上。

    if (xton == inf && yton == -inf) {
        if (dep[x] > dep[y]) 
            return Query_val(1, 1, N, dfn[y], dfn[x], 1);
        else 
            return Query_val(1, 1, N, dfn[x], dfn[y], 0);
    } else if (xton == inf) {
        if (dep[x] > dep[y]) {
            xret = Query_val(1, 1, N, dfn[y], dfn[x], 1);
            xton = Query_min(1, 1, N, dfn[y], dfn[x]);
        } else {
            xret = Query_val(1, 1, N, dfn[x], dfn[y], 0);
            xton = Query_min(1, 1, N, dfn[x], dfn[y]);
        }
    } else if (yton == -inf) {
        if (dep[x] > dep[y]) {
            yret = Query_val(1, 1, N, dfn[y], dfn[x], 1);
            yton = Query_max(1, 1, N, dfn[y], dfn[x]);
        } else {
            yret = Query_val(1, 1, N, dfn[x], dfn[y], 0);
            yton = Query_max(1, 1, N, dfn[x], dfn[y]);
        }
    } else if (dep[x] > dep[y]) {
        xret = max(xret, max(Query_val(1, 1, N, dfn[y], dfn[x], 1), Query_max(1, 1, N, dfn[y], dfn[x]) - xton));
        xton = min(xton, Query_min(1, 1, N, dfn[y], dfn[x]));
    } else {
        yret = max(yret, max(Query_val(1, 1, N, dfn[x], dfn[y], 0), yton - Query_min(1, 1, N, dfn[x], dfn[y])));
        yton = max(yton, Query_max(1, 1, N, dfn[x], dfn[y]));
    }
    int ret = max(max(xret, yret), yton - xton);
    return ret;

这题剩下的树上路径修改，我相信能来挑战这题的应该也不至于不会。所以代码就不贴了。接下来长达两百多行的完整代码奉上：

代码

#include <iostream>
#define int long long
using namespace std;
const int N = 131072;
const int inf = 2147483647;
int head[1000005], nxt[1000005], to[1000005], cnt;
inline void add(int u, int v) { to[++cnt] = v, nxt[cnt] = head[u], head[u] = cnt; }
int dfn[1000005], top[1000005], son[1000005], dep[1000005], sz[1000005], f[1000005], ncnt;
int ww[N << 2], w[100005];
// ------------------------------------ 以下树剖板子 ---------------------------------
void dfs1(int x, int fa, int d) {
    dep[x] = d;
    f[x] = fa;
    sz[x] = 1;
    for (int i = head[x]; i != 0; i = nxt[i]) {
        int v = to[i];
        if (v != fa) {
            dfs1(v, x, d + 1);
            sz[x] += sz[v];
            if (sz[v] > sz[son[x]]) 
                son[x] = v;
        }
    }
}
void dfs2(int x, int t) {
    top[x] = t;
    dfn[x] = ++ncnt;
    ww[ncnt] = w[x];
    if (!son[x]) 
        return;
    dfs2(son[x], t);
    for (int i = head[x]; i != 0; i = nxt[i]) {
        int v = to[i];
        if (v != f[x] && v != son[x]) 
            dfs2(v, v);
    }
}
// ------------------------------------ 以下线段树 ---------------------------------------
int mx[N << 2], mn[N << 2], val[2][N << 2], tag[N << 2];
inline void pushup(int o) {
    mx[o] = max(mx[o << 1], mx[o << 1 | 1]);
    mn[o] = min(mn[o << 1], mn[o << 1 | 1]);
    val[0][o] = max(max(val[0][o << 1], val[0][o << 1 | 1]), mx[o << 1 | 1] - mn[o << 1]);
    // 从左往右合并
    val[1][o] = max(max(val[1][o << 1], val[1][o << 1 | 1]), mx[o << 1] - mn[o << 1 | 1]);
    // 从右往左合并
}
inline void pushdown(int o) {
    if (tag[o] == 0) 
        return;
    int t = tag[o];
    tag[o] = 0;
    mx[o << 1] += t, mx[o << 1 | 1] += t;
    mn[o << 1] += t, mn[o << 1 | 1] += t;
    tag[o << 1] += t, tag[o << 1 | 1] += t;
}
void Build(int o, int l, int r) {
    if (l == r) {
        mx[o] = mn[o] = ww[l];
        val[0][o] = val[1][o] = 0;
        return;
    }
    int mid = l + r >> 1;
    Build(o << 1, l, mid);
    Build(o << 1 | 1, mid + 1, r);
    pushup(o);
}
void Change(int o, int l, int r, int L, int R, int k) {
    if (L <= l && r <= R) {
        mx[o] += k;
        mn[o] += k;
        tag[o] += k;
        return;
    }
    pushdown(o);
    int mid = l + r >> 1;
    if (L <= mid) 
        Change(o << 1, l, mid, L, R, k);
    if (R > mid) 
        Change(o << 1 | 1, mid + 1, r, L, R, k);
    pushup(o);
}
int Query_min(int o, int l, int r, int L, int R) {
    if (L * R == 0) 
        return inf;
    if (L <= l && r <= R) 
        return mn[o];
    pushdown(o);
    int mid = l + r >> 1, ret = 2147483647;
    if (L <= mid) 
        ret = min(ret, Query_min(o << 1, l, mid, L, R));
    if (R > mid) 
        ret = min(ret, Query_min(o << 1 | 1, mid + 1, r, L, R));
    return ret;
}
int Query_max(int o, int l, int r, int L, int R) {
    if (L * R == 0) 
        return -inf;
    if (L <= l && r <= R) 
        return mx[o];
    pushdown(o);
    int mid = l + r >> 1, ret = -2147483647;
    if (L <= mid) 
        ret = max(ret, Query_max(o << 1, l, mid, L, R));
    if (R > mid) 
        ret = max(ret, Query_max(o << 1 | 1, mid + 1, r, L, R));
    return ret;
}
int Query_val(int o, int l, int r, int L, int R, int dir) {
    if (L * R == 0) 
        return 0;
    if (L <= l && r <= R) 
        return val[dir][o];
    pushdown(o);
    int mid = l + r >> 1, sl = 0, sr = 0, ret = 0;
    if (L <= mid) 
        ret = Query_val(o << 1, l, mid, L, R, dir), sl = 1;
    if (R > mid) 
        ret = max(ret, Query_val(o << 1 | 1, mid + 1, r, L, R, dir)), sr = 1;
    if (sl && sr) {
        ret = max(ret, 
            !dir ? 
            Query_max(1, 1, N, mid + 1, R) - Query_min(1, 1, N, L, mid) : 
            Query_max(1, 1, N, L, mid) - Query_min(1, 1, N, mid + 1, R));
    }
    return ret;
}
// ------------------------------------ 以下树剖 ---------------------------------------
int Query_path(int x, int y) {
    int xton = inf, yton = -inf, xret = 0, yret = 0;
    // xton 代表 u 到 x 之间的最小值，yton 代表 y 到 v 之间的最大值
    // xret 代表 u 到 x 之间的最大利润，yret 同理
    while (top[x] != top[y]) {
        if (dep[top[x]] > dep[top[y]]) {
            if (xton == inf) {
                xret = max(xret, Query_val(1, 1, N, dfn[top[x]], dfn[x], 1));
                xton = Query_min(1, 1, N, dfn[top[x]], dfn[x]);
            } else {
                xret = max(xret, max(Query_val(1, 1, N, dfn[top[x]], dfn[x], 1), 
                    Query_max(1, 1, N, dfn[top[x]], dfn[x]) - xton));
                xton = min(xton, Query_min(1, 1, N, dfn[top[x]], dfn[x]));
            }
            x = f[top[x]];
        } else {
            if (yton == -inf) {
                yret = max(yret, Query_val(1, 1, N, dfn[top[y]], dfn[y], 0));
                yton = Query_max(1, 1, N, dfn[top[y]], dfn[y]);
            } else {
                yret = max(yret, max(Query_val(1, 1, N, dfn[top[y]], dfn[y], 0), 
                    yton - Query_min(1, 1, N, dfn[top[y]], dfn[y])));
                yton = max(yton, Query_max(1, 1, N, dfn[top[y]], dfn[y]));
            }
            y = f[top[y]];
        }
    }
    if (xton == inf && yton == -inf) { // 都没跳过链
        if (dep[x] > dep[y]) 
            return Query_val(1, 1, N, dfn[y], dfn[x], 1); // 直接返回
        else 
            return Query_val(1, 1, N, dfn[x], dfn[y], 0);
    } else if (xton == inf) { // x 没跳过
        if (dep[x] > dep[y]) {
            xret = Query_val(1, 1, N, dfn[y], dfn[x], 1);
            xton = Query_min(1, 1, N, dfn[y], dfn[x]);
        } else {
            xret = Query_val(1, 1, N, dfn[x], dfn[y], 0);
            xton = Query_min(1, 1, N, dfn[x], dfn[y]);
        }
    } else if (yton == -inf) { // y 没跳过
        if (dep[x] > dep[y]) {
            yret = Query_val(1, 1, N, dfn[y], dfn[x], 1);
            yton = Query_max(1, 1, N, dfn[y], dfn[x]);
        } else {
            yret = Query_val(1, 1, N, dfn[x], dfn[y], 0);
            yton = Query_max(1, 1, N, dfn[x], dfn[y]);
        }
    } else if (dep[x] > dep[y]) { // 都跳过，但是 x 深度大
        xret = max(xret, max(Query_val(1, 1, N, dfn[y], dfn[x], 1), Query_max(1, 1, N, dfn[y], dfn[x]) - xton));
        xton = min(xton, Query_min(1, 1, N, dfn[y], dfn[x]));
    } else { // 都跳过，但是 y 深度大
        yret = max(yret, max(Query_val(1, 1, N, dfn[x], dfn[y], 0), yton - Query_min(1, 1, N, dfn[x], dfn[y])));
        yton = max(yton, Query_max(1, 1, N, dfn[x], dfn[y]));
    }
    int ret = max(max(xret, yret), yton - xton);
    // 合并左右区间答案
    return ret;
}
void Add(int x, int y, int k) {
    while (top[x] != top[y]) {
        if (dep[top[x]] < dep[top[y]]) 
            swap(x, y);
        Change(1, 1, N, dfn[top[x]], dfn[x], k);
        x = f[top[x]];
    }
    if (dep[x] > dep[y]) 
        swap(x, y);
    Change(1, 1, N, dfn[x], dfn[y], k);
}
// ----------------------------------平平无奇的主函数-----------------------------------------
signed main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> w[i];
    for (int i = 1, u, v; i < n; i++) {
        cin >> u >> v;
        add(u, v);
        add(v, u);
    }
    dfs1(1, 0, 1);
    dfs2(1, 1);
    Build(1, 1, N);
    int m;
    cin >> m;
    while (m--) {
        int l, r, v;
        cin >> l >> r >> v;
        cout << Query_path(l, r) << "\n";
        Add(l, r, v);
    }
    return 0;
}

这题的分类讨论我想了很久，建议广大读者自己理解、消化这些奇奇怪怪的情况，想清楚各种分类的情况为什么是对应的贸易类型。想清楚这些，才算真正搞懂本题解之精神所在。

那么，

完结撒花~~

（撒花）（鼓掌）（欢呼）（撒花）

标签：洛谷,val,P3976,int,max,top,dfn,TJOI2015,Query
From： https://www.cnblogs.com/forgotmyhandle/p/18000232

相关文章

  • 洛谷 P1438 无聊的数列
    这题题解的做法千奇百怪，有写了两棵线段树的，有线段树套差分的，还有线段树套二阶差分的。我承认是我看不懂所以我决定写一篇只用一棵线段树的题解。分析众所周知，普通线段树的懒标记存的是一个待更新的量。那对于这个题来说，直接存和（也就是add操作在这个线段上的影响）肯定是不切实际......
  • 洛谷 P4429 [BJOI2018] 染色
    洛谷传送门LOJ传送门非常有趣的结论题。首先显然，整个图不是二分图就无解。然后显然每个连通块独立，可以分连通块判定。然后发现一度点是没什么用的，因为无论和它相连的点颜色是什么，它都能找到一种和这种颜色不同的颜色。所以考虑类似拓扑排序剥一度点。剩下的图的\(deg_u\ge......
  • 洛谷题单指南-暴力枚举-P1088 [NOIP2004 普及组] 火星人
    原题链接：https://www.luogu.com.cn/problem/P1088题意解读：火星人的手指可以通过全排列来表示数字，全排列由小到大的顺序即为表示的数字大小，题目可以转化为：给定按顺序全排列中的某一个排列，求往后数m个排列的内容。解题思路：此题与经典全排列问题的差异在于，需要从指定一个排列开......
  • 洛谷题单指南-暴力枚举-P1706 全排列问题
    原题链接：https://www.luogu.com.cn/problem/P1706题意解读：n个数全排列问题，本质上，给定n个空位，枚举每个能填入空位的数，依次填入，每个数只能填一次。解题思路：如何填入n个数呢，可以借助于递归，流程如下：dfs(填入第k个数){如果已经填满n个数输出结果返回......
  • 洛谷题单指南-暴力枚举-P1157 组合的输出
    原题链接：https://www.luogu.com.cn/problem/P1157题意解读：在1~n的数中挑选r个，有多少种组合，与P1036类似，有两种做法：二进制法、DFS，下面给出DFS版的代码。100分代码：#include<bits/stdc++.h>usingnamespacestd;constintN=25;intn,r;intt[N];voiddfs(intk){......
  • 洛谷题单指南-暴力枚举-P1036 [NOIP2002 普及组] 选数
    原题链接：https://www.luogu.com.cn/problem/P1036题意解读：题目即要在n个数中，枚举出所有的子集，当子集中数字个数刚好为k时，求和，判断是否是素数。解题思路：方法一：二进制法通过二进制法，可以枚举一个集合中所有元素“选”或者“不选”的情况，用二进制1表示选该元素，二进制0表示不选。......
  • 洛谷题单指南-暴力枚举-P1618 三连击（升级版）
    原题链接：https://www.luogu.com.cn/problem/P1618题意解读：枚举所有三位数的组合情况，判断是否符合比例。解题思路：方法一：枚举第一个数根据题意，目的是寻找三个符合比例的三位数，可以直接枚举第一个，最小是123，最大是987设第一个数为x，三个数的比例关系是a：b：c设另外两个数为y，z那么，根......
  • 洛谷题单指南-暴力枚举-P2241 统计方形（数据加强版）
    原题链接：https://www.luogu.com.cn/problem/P2241题意解读：要在整个n*m区域计算正方形和长方形的个数，枚举法即可。解题思路：此题枚举的对象是矩形的高i和宽j，高的范围[1,n]，宽的范围[1,m]，然后计算在n*m区域内有多少个i*j，i==j即属于正方形，i!=j属于长方形。那么，问题就集中在了......
  • 洛谷题单指南-排序-P1012 [NOIP1998 提高组] 拼数
    原题链接：https://www.luogu.com.cn/problem/P1012题意解读：通过某种合理的排序方式，使得排序后的数字连在一起最大。解题思路：此题关键在于排序，对于两个数字，哪个数字应该排在前面呢？1、思考误区很容易想到，给定两个数abcd、xyz，先比较第一位a和x，谁大谁排前面，一直到c和z。再来看d，这......
  • 洛谷题单指南-排序-P1104 生日
    原题链接：https://www.luogu.com.cn/problem/P1104题意解读：将学生按照年龄由大到小排序，如果年龄相同，后输入的排在前面，输出排序后的学生姓名。解题思路：此题是一个排序常规题，年龄大排在前说明年、月、日越小越在前面，核心的排序思路如下：1、如果年份不同，按年份由小到大排序2、如果......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99