Can you answer these queries II 做题随笔题解-171主机测评

Can you answer these queries II 做题随笔/题解

文章目录

Can you answer these queries II 做题随笔/题解
- 题意简述
- 正解
- - 示例：数组 `[5, -10, 6]`
  - 结论
  - 变故&解决
  - 梳理一下
  - 实现流程
  - 代码

题意简述

洛谷传送门 vjudge传送门给你一个长度为

(

≤

)

n(1 \\le n \\le 1e5)

$n (1 \leq n \leq 1 e 5)$ 的序列

$a$ ，每个数

∈

[

−

]

a_i ∈[-1e5,1e5]

$a_{i} \in [- 1 e 5, 1 e 5]$ 。现在有

(

≤

)

Q(1 \\le Q \\le 1e5)

$Q (1 \leq Q \leq 1 e 5)$ 次提问，包含两个整数

(

≤

)

X,Y(1 \\le X,Y \\le n)

$X, Y (1 \leq X, Y \leq n)$ ，求出区间最大子段和的值。特别地，对于任何一个权值仅能被计数一次。比如这个样例：

// 输入
9
4 –2 –2 3 –1 –4 2 2 –6
3
1 2
1 5
4 9

// 输出
4
5
3

当第二次询问

X=1,Y=5

$X = 1, Y = 5$ 时，最大子段和为[1,4]，权值和

(

−

)

sum=4+(-2)+3=5

$s u m = 4 + (- 2) + 3 = 5$ ，

−

-2

$- 2$ 只会被算一次，后面遇到就直接跳过。

正解

既然要维护任意区间内的最大子段和并且多次提问，那一定就是用线段树无疑了。不带修的的最大子段和我们肯定信手拈来，现在问题是“对于任何一个权值仅能被计数一次”，如果用正常的模板代码去做的话可能会漏掉最优解。像是刚才说过的第二次询问，模板输出就是

$4$ ，这肯定不行。

那怎么办呢？

使用瞪眼法——“对于任何一个权值仅能被计数一次”，发现其实就是做“种类区分”。还记得洛谷 P1972 [SDOI2009] HH 的项链吗？_{虽然我还没A过。}那一道题也是统计种类。做法是这样：

将所有询问按右端点 r 排序，从左到右依次将元素加入数据结构，并在加入后回答所有 r == i 的询问。

所以这道题是否也能仿照HH的项链一样求解呢？让我们试一试：

预处理
由于题目没有强制在线，所以对所有询问的右端点从小到大排序；
至于线段树……并不能照搬HH的思路，真是个难点

貌似卡住了。

问题源于：我们统计的可不是什么区间内的数字的种数，而是最大子段和。如果按照HH的思路：循环遍历for(int i=1;i<=n;i++)，每次在线段树中区间adda[i]，即add(1,pre[i]+1,i,a[i])¹。但是这样更新完，就只能访问到

$i$ 的最大后缀了，这肯定是不行滴~

又不能把线段树给抛弃了，于是乎就只能在它身上做文章了：

现在结构体

tree

$t r ee$ _{也就是节点k的类型}中有这几个成员变量：

l,r,sum,sumtag

$l, r, s u m, s u m t a g$ 。我们再加一个：

hismax

$hi s ma x$ ，干什么用的呢？

当节点
当节点

这样定义了能干嘛呀？我们先要明确：为啥“更新完

$k$ 就只能访问到

$i$ 的最大后缀了”? 看D老师讲解：

假设我们只有 sum（当前最大值），没有 hismax（历史最大值）。那么，当我们扫描到某个右端点 R 时，线段树的每个叶子节点存储的是以该叶子为左端点、以当前 R 为右端点的去重和。查询区间 [l, R] 返回的是 max_{pos ∈ [l, R]} sum[pos]，这恰好是以 R 为右端点的最大子段和（也就是最大后缀）。但你无法回答一个询问区间 [l, r]，其中 r < R，因为当 R 继续增大后，sum 的值已经变为了以新右端点结尾的和，旧的历史峰值丢失了。

示例：数组 [5, -10, 6]

我们逐步执行扫描（假设去重不影响，因为所有值不同）。

初始化：所有 sum[pos] = 0。

i = 1，加入 5：

区间加 [1,1] +5 → sum[1] = 5。
此时（右端点=1），查询 [1,1] 返回 sum[1] = 5（正确，子段 [1,1] 的和为5）。

i = 2，加入 -10：

区间加 [1,2] -10 → sum[1] = -5，sum[2] = -10。
此时（右端点=2），查询 [1,2] 返回 max(sum[1], sum[2]) = -5。但历史上，在 i=1 时，sum[1]=5，而 i=2 时变为 -5。查询 [1,2] 实际应该考察所有子段（可以是 [1,1] 和 [1,2] 等），最大是 5（子段 [1,1]）。但我们现在只能得到 -5，因为 sum[1] 被降低了。

i = 3，加入 6：

区间加 [1,3] +6 → sum[1] = 1，sum[2] = -4，sum[3] = 6。
现在（右端点=3），查询 [1,3] 返回 max(1, -4, 6) = 6。这个 6 是子段 [3,3] 的和，并非历史上最大的 5（虽然 6 更大，但在其他例子中历史峰值可能更大）。但如果查询 [1,2]（右端点为2，但我们只能回答当前右端点=3时的查询），我们无法直接回答，因为我们已经错过了 i=2 时的状态。

关键点：当我们在处理询问 [l, r] 时，必须在扫描到右端点恰好为 r 时才能回答。如果在扫描到 r 时，某些左端点的 sum 值已经被后来的修改（比如负数的加入）拉低了，而这些左端点历史上曾经有更高的值，那么我们若只存储当前 sum，就会丢失这些历史峰值，导致答案偏小。

结论

没有 hismax，我们只能回答“以当前右端点 i 为结尾的最大子段和”（即最大后缀），因为 max(sum[pos]) 仅代表以 i 为右端点的最大和。而要回答任意区间 [l, r] 的任意子段（右端点可以是 r 之前的任何位置），我们必须记录每个左端点在不同右端点下的历史峰值。这就是 hismax 存在的根本原因。

OK那现在我们理解“为什么需要hismax”了。

也就是说现在——可以爽爽求代码了？

很抱歉，还是不行。

变故&解决

凭啥啊！？

在我们的线段树区间修改中有一个很棘手的问题：信息丢失！

怎么说？

假设父节点 P 在两次不同的时刻，对子节点 C 所在的整个区间进行了区间加操作：

第一次：区间加 +5。

此时 C 的当前值从 X 变成了 X+5，历史峰值更新为 X+5。

第二次：区间加 -10。

此时 C 的当前值从 X+5 变成了 X-5。虽然当前值降低了，但历史峰值仍然保持在 X+5（因为历史记录不会因为数值下降而抹去）。

现在问题来了：在这个过程中，我们并没有立即将每次修改都下传给 C，而是只更新了父节点 P 上的懒标记。P 记录的信息是：

sumtag = -5（两次净变化：+5-10）
但历史最大净变化：+5

接下来：

当某个操作（如查询或后续修改）触发 push_down 时，父节点 P 只能把 sumtag = -5 传给子节点 C。

那么 C 会做这样的更新：

C.sum 从 X 变成 X – 5。

C.hismax 用更新后的 X-5 去刷新，结果仍然是 X-5。

结果：子节点 C 的历史最大值丢失了 +5 的峰值，本应是 X+5，却错误地变成了 X-5。它完全不知道自己在某个时刻曾经达到过 X+5 这个高度。如此一来子节点的hismax在push_up()时就会偏小，最终答案就错误了。

综上所述：如果不能解决信息丢失的问题，我们的算法——就废啦！

在这里插入图片描述

我就是说，谁让你不写主席树的？那现在怎么办？扯了这么久不会告诉我们要推倒重来写主席树吧？

NO NO NO ，大可不必。

那怎么办呢？

且听我娓娓道来：

再定义一个成员变量：

hismaxtag

$hi s ma x t a g$ 变量名最长的一集，不知道的以为是AI

ta表示：在当前节点 k 上，所有尚未下传给子节点的、对 sum 的增量中，历史上曾经达到过的最大值。

只要有了ta，当父节点下传标记时，子节点就知道：“虽然现在我只净增加了 sumtag，但我在历史上曾经净增加过 hismaxtag。我的历史最大值应该基于这个更大的增量来更新。”

这下总行了吧？

没~错！到了现在，我们的线段树已经能够完美胜任这道题了！

梳理一下

我们要维护一棵线段树，每个节点包含以下

$6$ 个成员变量：

l：节点维护的左端点
r：节点维护的右端点
sum：
- 当k为叶子时：表示以该位置为左端点、当前扫描到的右端点 i 为结尾的去重子段和。
- 当k为内部节点时：sum为左右儿子sum的最大值
hismax：
- k为叶子时：hismax为历史sum的最大值(最小为0)
- 当k为内部节点时：hismax为左右儿子hismax的最大值
sumtag：区间修改懒标记
hismaxtag：sumtag的历史最大值

实现流程

预处理pre数组、将问题排序、建树；

循环遍历

输出

终于

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ls (k<<1) // 左孩子索引
#define rs (k<<1|1) // 右孩子索引
const int o=1e6+22;

int n,m;
int a[o]={0};
int pre[o]={0}; // pre[i]：a[i]上一次出现的位置
unordered_map<int,int> lst; // 辅助数组，用于计算pre[i]

// 询问结构体
struct node
{
int tid; // 询问编号
int l,r; // 查询区间 [l, r]
} q[o];

// 按右端点排序
bool cmp(node x,node y)
{
if(x.r != y.r) return x.r < y.r;
return x.l < y.l;
}

// 线段树节点
struct tree
{
int l,r; // 节点管辖的区间范围 [l, r] (物理下标)

int sum; // 当前最大值：
// 叶子：以该位置为左端点、当前扫描右端点下的去重子段和
// 内部：左右儿子 sum 的最大值

int hismax; // 历史最大值：
// 叶子：sum 从开始到当前时刻曾经达到的最大值（至少为0）
// 内部：左右儿子 hismax 的最大值

// 懒标记
int sumtag; // 当前增量懒标记：待下传的净增加值
int hismaxtag; // 历史增量懒标记：sumtag 在历史上达到过的最大值
} t[o<<2];

// 向上更新：用左右孩子更新父节点
void push_up(int k)
{
t[k].sum = max(t[ls].sum, t[rs].sum);
t[k].hismax = max(t[ls].hismax, t[rs].hismax);
}

// 下传懒标记
void push_down(int k) {
// 如果没有任何标记，直接返回
if (t[k].sumtag == 0 && t[k].hismaxtag == 0) return;

// 先用旧的 sum 更新 hismax，再更新 sum，否则历史峰值会被当前值覆盖。标记同理。

// 1. 更新左孩子的历史最大值：用孩子旧的 sum + 父节点的历史峰值增量
t[ls].hismax = max(t[ls].hismax, t[ls].sum + t[k].hismaxtag);
t[rs].hismax = max(t[rs].hismax, t[rs].sum + t[k].hismaxtag);

// 2. 更新孩子的当前值
t[ls].sum += t[k].sumtag;
t[rs].sum += t[k].sumtag;

// 3. 更新孩子的历史懒标记：用孩子旧的 sumtag + 父节点的历史峰值增量
t[ls].hismaxtag = max(t[ls].hismaxtag, t[ls].sumtag + t[k].hismaxtag);
t[rs].hismaxtag = max(t[rs].hismaxtag, t[rs].sumtag + t[k].hismaxtag);

// 4. 更新孩子的当前懒标记
t[ls].sumtag += t[k].sumtag;
t[rs].sumtag += t[k].sumtag;

// 5. 清空父节点标记
t[k].sumtag = t[k].hismaxtag = 0;
}

// 建树：初始化所有值为0
void build(int k,int l,int r)
{
t[k] = {l, r, 0, 0, 0, 0};
if(l == r) return;
int mid = (l + r) >> 1;
build(ls, l, mid);
build(rs, mid+1, r);
push_up(k);
}

// 区间加：对 [l, r] 增加 val
void add(int k,int l,int r,int val)
{
// 完全覆盖当前节点
if(l <= t[k].l && t[k].r <= r)
{
// 1. 更新当前增量标记
t[k].sumtag += val;
// 2. 更新当前最大值（所有值同时增加 val，最大值也增加 val）
t[k].sum += val;
// 3. 用新的 sum 更新历史最大值
t[k].hismax = max(t[k].hismax, t[k].sum);
// 4. 用新的 sumtag 更新历史增量标记
t[k].hismaxtag = max(t[k].hismaxtag, t[k].sumtag);
return;
}

// 部分覆盖：下传标记，递归更新孩子
int mid = (t[k].l + t[k].r) >> 1;
push_down(k);
if(l <= mid) add(ls, l, r, val);
if(r > mid) add(rs, l, r, val);
// 回溯更新当前节点
push_up(k);
}

// 区间查询：返回 [l, r] 的历史最大值
int query(int k,int l,int r)
{
// 完全覆盖：直接返回该节点的历史最大值
if(l <= t[k].l && t[k].r <= r)
return t[k].hismax;

int ans = 0; // 因为答案至少为0（空子段）
int mid = (t[k].l + t[k].r) >> 1;
push_down(k); // 查询前必须下传标记，保证孩子值最新
if(l <= mid) ans = max(ans, query(ls, l, r));
if(r > mid) ans = max(ans, query(rs, l, r));
return ans;
}

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

// 读入数组并预处理 pre[i]
cin >> n;
for(int i=1; i<=n; i++)
{
cin >> a[i];
pre[i] = lst[a[i]]; // 记录上次出现位置（默认0）
lst[a[i]] = i; // 更新为当前位置
}

// 读入询问
cin >> m;
for(int i=1; i<=m; i++)
{
int l, r;
cin >> l >> r;
q[i] = {i, l, r};
}

// 按右端点排序（离线处理）
sort(q+1, q+1+m, cmp);

// 建树（所有节点初始为0）
build(1, 1, n);

vector<int> ans(m+1, 0);
int idx = 1; // 当前待处理的询问下标

// 扫描右端点 i 从 1 到 n
for(int i=1; i<=n; i++)
{
// 加入 a[i]：区间 [pre[i]+1, i] 增加 a[i]
// 这表示所有以 pos (pre[i]+1 <= pos <= i) 为左端点的子段，
// 其去重和都增加 a[i]
if(pre[i] + 1 <= i)
add(1, pre[i]+1, i, a[i]);

// 处理所有右端点恰好为 i 的询问
while(idx <= m && q[idx].r == i)
{
ans[q[idx].tid] = query(1, q[idx].l, i);
idx++;
}
}

// 按原顺序输出答案
for(int i=1; i<=m; i++)
cout << ans[i] << "\\n";

return 0;
}

结束！

这里做个补充说明：本题线段树中，由于在动态扩大上界，所以节点

$k$ 的含义/实际存的东西为：维护从当前节点

$k$ 的左端点到达已知上界

$i$ 的数据。当然，如果当前的

$i$ 已经大于等于建树时给节点

$k$ 分配的右端点时，就只更新到

$k$ 的右端点就可以了。更新范围就是从上次a[i]出现位置更新到

$i$ 。 ↩︎

Can you answer these queries II 做题随笔题解