题目理解

我们有一个长度为 $n$ 的序列 $a$，初始全为 $0$。

有 $n$ 个操作 $(x_i, y_i)$，表示将 $a_1$ 到 $a_{x_i}$ 都加上 $y_i$。

有 $q$ 次查询，每次给出 $[l, r]$，问依次执行第 $l$ 到第 $r$ 个操作后，序列的最大值是多少。

---

问题分析

关键观察

执行操作 $(x, y)$ 后，序列的前缀和变化：

• 位置 $1$ 到 $x$：$+y$
• 位置 $x+1$ 到 $n$：不变

因此，最终 $a_i$ 的值等于所有覆盖了位置 $i$ 的操作的 $y$ 值之和。

即：

$$a_i = \sum_{j=l}^{r} [x_j \ge i] \cdot y_j$$

我们要找：

$$\max_{i=1}^n a_i = \max_{i=1}^n \sum_{j=l}^{r} [x_j \ge i] \cdot y_j $$

---

核心思路

1. 问题转化

令 $S_i = \sum_{j=l}^{r} [x_j \ge i] \cdot y_j$，则：

• $S_1$ 包含所有操作（因为 $x_j \ge 1$ 对所有 $j$ 成立）
• $S_{i+1} = S_i - \sum_{j=l}^{r} [x_j = i] \cdot y_j$

所以 $S_i$ 是一个前缀和递减的序列。

我们要找的就是 $\max_{i=1}^n S_i$。

2. 数据结构设计

struct info_t {
    ll mx, sum;
};

• mx：该区间操作序列产生的最大值
• sum：该区间操作序列对 $S_1$ 的贡献（即所有 $y$ 之和）

合并规则：

info_t unite(const info_t &lhs, const info_t &rhs) {
    return {max(lhs.mx + rhs.sum, rhs.mx), lhs.sum + rhs.sum};
}

这表示：

• 总最大值 = max(左区间最大值 + 右区间总和, 右区间最大值)
• 总和 = 左区间总和 + 右区间总和

3. 分块处理

代码将操作序列分成大小为 $512$ 的块，对每个块预处理信息。

对于每个块：

• 按 $x_i$ 排序操作
• 预处理出对于任意区间 $[l, r]$ 在该块内的答案

---

算法流程详解

1. 预处理阶段

sort(id + 1, id + n + 1, [](int p, int q) {
    return a[p] < a[q] || (a[p] == a[q] && b[p] > b[q]);
});

按 $x_i$ 排序，$x_i$ 相同时按 $y_i$ 降序排列。

2. 线段树构建

void build(int p, int l, int r) {
    info[p].assign(r - l + 2, vector<info_t>(r - l + 2, {-infll, 0}));
    // 为每个节点分配存储空间
}

3. 关键操作：pushup

void pushup(int p) {
    int lp = ls(p), rp = rs(p);
    // 合并左右子节点的关键点（x值）
    mp[p].resize(mp[lp].size() + mp[rp].size() - 1);
    merge(mp[lp].begin(), mp[lp].end() - 1,
          mp[rp].begin(), mp[rp].end() - 1, mp[p].begin());
    
    // 预处理指针数组，用于快速查找
    for (int i = 0, li = 0, ri = 0; i < (int)mp[p].size(); ++i) {
        while (li < (int)mp[lp].size() && mp[lp][li] < mp[p][i]) ++li;
        while (ri < (int)mp[rp].size() && mp[rp][ri] < mp[p][i]) ++ri;
        psl[i] = li, psr[i] = ri;
    }
    
    // 预处理所有区间组合的答案
    for (int i = 0; i < (int)mp[p].size(); ++i) {
        for (int j = i + 1; j < (int)mp[p].size(); ++j) {
            info[p][i][j] = unite(info[lp][psl[i]][psl[j]],
                                  info[rp][psr[i]][psr[j]]);
        }
    }
}

4. 查询处理

对于每个查询 $[l, r]$：

for (int i = 1; i <= n; i += 512) {
    update(i);  // 更新当前块的信息
    for (int j = 1; j <= q; ++j) {
        ans[j] = unite(ans[j], info[1][pos[l]][pos[r + 1]]);
    }
}

---

样例分析

对于样例输入：

6 5
6 4
2 6  
5 -5
3 6
1 2
3 6
1 6
1 6
2 6
2 6
5 6

操作序列：

1. (6,4)
2. (2,6)
3. (5,-5)
4. (3,6)
5. (1,2)
6. (3,6)

查询 [1,6] 的计算：

• $S_1 = 4+6+(-5)+6+2+6 = 19$
• $S_2 = 19 - 0 = 19$（没有$x=1$的操作）
• $S_3 = 19 - 6 = 13$（操作2的$x=2$）
• $S_4 = 13 - 6 = 7$（操作4,6的$x=3$）
• $S_5 = 7 - (-5) = 12$（操作3的$x=5$）
• $S_6 = 12 - 4 = 8$（操作1的$x=6$）

最大值为 $19$，与输出一致。

---

复杂度分析

• 预处理：$O(n \log n + \frac{n}{B} \cdot B^2) = O(nB)$，其中 $B=512$
• 查询：$O(q \cdot \frac{n}{B})$
• 总复杂度：$O(nB + \frac{nq}{B})$，取 $B=\sqrt{n}$ 时为 $O(n\sqrt{n})$

对于 $n,q \le 5\times 10^5$，可接受。

---

算法标签

• 分块
• 线段树
• 离线查询
• 前缀和优化
• 区间最值

---

总结

这道题的解法核心是：

1. 问题转化：发现序列最大值等于某个前缀和序列的最大值
2. 分块处理：将操作序列分块，预处理每个块的信息
3. 高效合并：设计合适的数据结构支持区间信息快速合并
4. 边界处理：正确处理不完整块的情况

通过分块平衡了预处理和查询的复杂度，实现了高效求解。