题目理解

我们有 $N$ 张卡片，每张卡片有一个值 $A_i$。对于每个查询区间 $[L,R]$，从 $0$ 开始，依次对每个卡片选择加或减操作，要求过程中黑板上的数字始终非负。目标是最大化减操作的次数（吃外郎饼的数量）。

关键观察

1. 问题转化

这实际上是一个带非负约束的符号分配问题。我们需要给每个卡片分配 $+$ 或 $-$ 号，使得：

• 前缀和始终 $\geq 0$
• 最大化 $-$ 号的数量

2. 贪心策略

从后往前考虑，优先给大数值分配 $-$ 号，但要保证前缀和非负。

算法核心

按值域分层处理

代码的核心思想是按数值从大到小处理：

for (int i = 1; i <= maxV; i++) {  // 从1到最大值处理
    // 处理所有数值为i的卡片
}

算法流程

步骤1：预处理

// 计算前缀和
for (int i = 1; i <= n; i++) {
    D[0][i] = D[0][i - 1] + a[i];
    maxV = max(maxV, a[i]);
}

步骤2：按值处理

对于每个数值 $i$：

1. 标记和计数：

if (a[j] == i) {
    a[j] = -i;  // 暂时标记为负
    cnt[j]++;   // 计数
}
D[i][j] = a[j] + D[i][j - 1];  // 新的前缀和

2. 构建ST表：

for (int len = 1; (1 << len) <= n; len++)
    for (int j = 1; j + (1 << len) - 1 <= n; j++)
        st[len][j] = min(st[len - 1][j], st[len - 1][j + (1 << (len - 1))]);

3. 二分查找分界点：

while (l < r) {
    int mid = (l + r) >> 1;
    int itpre = sum[j] + D[i - 1][mid] - D[i - 1][ql[j]];
    int rmin = query(mid + 1, qr[j]) - D[i][mid];
    
    if (itpre + rmin >= 0)
        r = mid;
    else
        l = mid + 1;
}

步骤3：更新答案

ans[j] += cnt[qr[j]] - cnt[l];  // 可以取负号的数量
sum[j] += D[i - 1][l] - D[i - 1][ql[j]];  // 更新当前和
ql[j] = l;  // 更新左边界

算法正确性

1. 贪心选择原理

从大到小处理数值，优先让大数值取负号：

• 大数值取负号对前缀和的"伤害"更大
• 但如果我们能承受这种伤害，就应该优先选择

2. 二分查找的意义

对于每个数值 $i$，找到最大的位置 $l$，使得：

• $[l+1, R]$ 区间内的所有前缀和都满足非负约束
• 这样 $[l+1, R]$ 区间内所有数值 $i$ 的卡片都可以安全地取负号

3. 非负约束检查

itpre + rmin >= 0

这里：

• itpre：当前位置的前缀和
• rmin：右边区间的最小前缀和（考虑当前数值取负的影响）
• 检查整个区间是否都能保持非负

时间复杂度

• 预处理：$O(N \log N)$
• 每个数值处理：$O(N \log N + Q \log N)$
• 总复杂度：$O(V \cdot (N + Q) \log N)$，其中 $V \leq 100$

由于 $V$ 很小，在 $N, Q \leq 2\times 10^5$ 的限制下可行。

关键数据结构

1. 前缀和数组：D[i][j] 存储考虑前 $i$ 种数值时的前缀和
2. ST表：快速查询区间最小值
3. 计数器：cnt[j] 统计数值出现次数

算法优势

1. 值域分解：将复杂问题按数值分层处理
2. 贪心优化：优先处理大数值，最大化收益
3. 二分效率：快速定位安全的分界点
4. 预处理加速：ST表支持快速区间查询

算法标签

• 贪心算法
• 值域分解
• 二分查找
• 前缀和
• ST表
• 区间查询

总结

该算法通过巧妙的值域分层和贪心二分策略，解决了带约束的符号分配问题。核心思想是从大到小处理数值，对每个数值二分找到能安全取负号的最大范围，利用ST表快速验证非负约束。算法设计精妙，在严格的时间限制下高效解决了大规模查询问题。