题目分析

我们需要处理一个 N×N 的网格，每个格子是一个糖袋。有 Q 次操作，每次操作给一个矩形区域内的所有糖袋添加 k 颗颜色为 c 的糖果。最后对每个糖袋，判断是否存在某种颜色的糖果数量严格超过其他所有颜色糖果数量之和，如果有则输出该颜色，否则输出 -1。

---

核心思路

1. 问题难点

直接模拟不可行：Q 可达 50 万，N 可达 1000，颜色种类最多 Q 种。

关键观察：对于每个糖袋，要成为压倒性颜色，必须满足：

count[c] > total - count[c]  
=> 2 * count[c] > total

其中 total 是该糖袋中所有颜色糖果总数。

---

2. 算法设计

2.1 总体流程

1. 计算每个格子的总糖果数 ova[i][j]
2. 逐位判断候选颜色：对每个二进制位，计算该位为 1 的颜色在该格子的总糖果数
3. 验证候选颜色：对每个可能成为答案的颜色，验证是否真的满足压倒性条件

---

2.2 步骤详解

步骤 1：计算总糖果数

使用二维差分数组快速处理矩形区间加：

void add(ll a[N][N], int xl, int xr, int yl, int yr, int w) {
    a[xl][yl] += w, a[xr + 1][yr + 1] += w;
    a[xr + 1][yl] -= w, a[xl][yr + 1] -= w;
}

然后通过前缀和还原每个格子的实际值。

步骤 2：逐位筛选候选颜色

对每个二进制位 w (0 ≤ w < 20)：

• 统计该位为 1 的所有颜色在格子 (i,j) 中的糖果总数 cnt[i][j]
• 如果 2 * cnt[i][j] > ova[i][j]，则候选颜色 ans[i][j] 的第 w 位设为 1

原理：如果颜色 c 是压倒性颜色，那么对于 c 的每个为 1 的二进制位，该位为 1 的所有颜色在格子中的糖果总数必然满足 2 * cnt > total。

步骤 3：验证候选颜色

对每个颜色 col：

• 收集所有涉及该颜色的操作和候选格子
• 使用树状数组按行处理，计算每个候选格子中颜色 col 的实际数量
• 验证是否真的满足 2 * count[col] > total

---

3. 复杂度分析

• 步骤 1：O(Q + N²)
• 步骤 2：O(W × (Q + N²))，W=20
• 步骤 3：O(Q log N + N²)

总复杂度：O(W × Q + W × N² + Q log N)，对于 N=1000, Q=5e5 可接受。

---

4. 样例验证

样例 1

输入：

5 3
1 3 5 5 3 3
2 2 4 4 1 5  
1 1 3 5 1 3

处理过程：

1. 计算总糖果数 ova
2. 逐位筛选得到候选颜色
3. 验证后输出：

1  1 -1 -1 -1
1  1  1  1 -1  
1  1  1  1 -1
-1 1  1  1  3
-1 -1 3  3  3

与样例输出一致。

---

5. 关键优化

5.1 二维差分

快速处理矩形区间加操作，将每次操作的复杂度从 O(矩形大小) 降为 O(1)。

5.2 逐位筛选

将颜色判断分解为二进制位判断，避免直接枚举所有颜色。

5.3 树状数组验证

按颜色分组处理，用树状数组高效计算特定颜色在某个格子的数量。

---

算法标签

• 二维差分 (2D Difference Array)
• 位运算技巧 (Bit Manipulation)
• 树状数组 (Fenwick Tree)
• 离线处理 (Offline Processing)

---

总结

本题通过巧妙的位运算分解和分层验证，在合理时间内解决了大规模数据下的颜色统计问题。核心在于将压倒性颜色的判断条件转化为二进制位上的局部条件，再通过高效的数据结构进行验证。