【洛谷题解】P7706 「Wdsr

【洛谷题解】P7706 「Wdsr

原题链接：P7706

更好的阅读体验：吾の博客

文文的摄影布置-题解

题意分析

简化题意就是给定两个序列 A , B A,B A,B，规定： ψ ( i , k ) = A i + A k − min ⁡ { B j } ( i < j < k ) psi(i,k)=A_i+A_k-minleft.{B_jright.}(i<j<k) ψ(i,k)=Ai​+Ak​−min{Bj​}(i<j<k)。给定一个区间 ( l , r ) (l,r) (l,r) 求该区间内的 max ⁡ ( ψ ) max(psi) max(ψ)。两个序列的数值可能发生变化。

这是典型的单点修改、区间查询问题，显而易见可以运用线段树解决。

维护信息-分类讨论

依题意，首先需要维护每个区间分别最大的 A i A_i Ai​ 和最小的 B j B_j Bj​。

ψ ( i , k ) = A i + A k − min ⁡ { B j } ( i < j < k ) psi(i,k)=A_i+A_k-minleft.{B_jright.}(i<j<k) ψ(i,k)=Ai​+Ak​−min{Bj​}(i<j<k)

对于该式，想要求 max ⁡ ( ψ ) max(psi) max(ψ)，就是求 max ⁡ ( A i + A k − min ⁡ { b j } ) max(A_i+A_k-minleft.{b_jright.}) max(Ai​+Ak​−min{bj​})， i , j , k i,j,k i,j,k 的位置并不是一定的，于是我们考虑 i , j , k i,j,k i,j,k 的位置，并且考虑如何计算某种情况下的 max ⁡ ( ψ ) max(psi) max(ψ)：

情况 1：都在左子树或都在右子树

这种情况好搞，就是在维护区间信息(做 push_up 操作)时取一下左右子树最大值就行。

情况 2：横跨左右子树

将原式可以拆成两个小式子 A i − B j ( i < j ) A_i-B_j(i<j) Ai​−Bj​(i<j) 和 A k − B j ( j < k ) A_k-B_j(j<k) Ak​−Bj​(j<k)，并且考虑 i , j , k i,j,k i,j,k 在不同子树下的两式最大值计算。横跨左右子树分 i , j i,j i,j 在左子树而 k k k 在右子树和 i i i 在左子树而 j , k j,k j,k 在右子树两种情况。

对于前者情况，我们维护当前区间左子树最大的 A i A_i Ai​ 和右子树最小的 B j B_j Bj​ 的差；对于后者情况，我们维护当前区间右子树最大的 A k A_k Ak​ 和左子树最小的 B j B_j Bj​ 的差。

最后

最后，求 max ⁡ ( ψ ) max(psi) max(ψ)，对于情况 2 的前者的式子再加上右子树最大的 A k A_k Ak​；对于情况 2 的后者的式子再加上左区间最大的 A i A_i Ai​，共两种情况。

对于情况 1 分别为左右子树的 max ⁡ ( ψ ) max(psi) max(ψ)，共两种情况。

上述四种情况，取最大值即为当前区间的 max ⁡ ( ψ ) max(psi) max(ψ)。

一些笔者的提醒和建议（也可能有点多余）：

• 维护信息时要注意一下顺序。

• 建树时要把情况 2 中的两式最大值和 ψ psi ψ 初始化为负无穷。

• 考虑到这题会爆 int 但是我们维护的信息比较多，参考了一下几位大佬的写法，可以 define int 为 LL，主函数返回值类型写成 signed。

其他的，大家看代码吧。

AC代码

#include <iostream>
#include <cstdio>
#define int long longusing namespace std;const int  N = 5e5 + 10, INF = -0x3f3f3f3f;struct Segment
{int a, b;
}seg[N];
struct Node
{int l, r;int amax; //A的最大值 int bmin; //B的最小值 int lmax; //A_i - B_j且i < j的最大值 int rmax; //A_k - B_j且j < k的最大值 int tmax; //psi 
}tr[N * 4];
int n, m;void push_up(Node &u, Node &l, Node &r)
{u.amax = max(l.amax, r.amax);u.bmin = min(l.bmin, r.bmin);//对应Node节点的信息 u.lmax =  l.amax - r.bmin; //a_i - ax = r.amax - l.bmin; //a_k - b_j//再与左右子树取最大值u.lmax = max(u.lmax, max(l.lmax, r.lmax));u.rmax = ax, ax, r.rmax));//求ψu.tmax = max(max(l.lmax + r.amax, r.rmax + l.amax), ax, r.tmax)); 
}void push_up(int u)
{push_up(tr[u], tr[u << 1], tr[u << 1 | 1]);
}void build(int u, int l, int r)
{if (l == r){tr[u] = {l, r, seg[r].a, seg[r].b, INF, INF, INF}; }else{tr[u] = {l, r};int mid = l + r >> 1;build(u << 1, l, mid);build(u << 1 | 1, mid + 1, r);push_up(u);}
}void modify(int u, int x, int v, int tag)
{if (tr[u].l == x && tr[u].r == x){if (tag == 1) tr[u].amax = v;if (tag == 2) tr[u].bmin = v;}else{int mid = tr[u].l + tr[u].r >> 1;if (x <= mid) modify(u << 1, x, v, tag);else modify(u << 1 | 1, x, v, tag);push_up(u);}
}Node query(int u, int l, int r)
{if (tr[u].l >= l && tr[u].r <= r) return tr[u];else{int mid = tr[u].l + tr[u].r >> 1;if (r <= mid) return query(u << 1, l, r);else if (l > mid) return query(u << 1 | 1, l, r);else{Node res;auto Left = query(u << 1, l, r);auto Right = query(u << 1 | 1, l, r);push_up(res, Left, Right);return res;}}
}signed main()
{scanf("%lld%lld", &n, &m);for (int i = 1; i <= n; i++) scanf("%lld", &seg[i].a);for (int i = 1; i <= n; i++) scanf("%lld", &seg[i].b);build(1, 1, n);for (int i = 1; i <= m; i++){int op, x, y;scanf("%lld%lld%lld", &op, &x, &y);if (op == 1 || op == 2) modify(1, x, y, op);else printf("%lldn", query(1, x, y).tmax);}return 0;}

这是笔者在洛谷的第一份题解，若有错误欢迎各位指正，有问题大家可以在评论区探讨。