题目详解：K. Kingdom of Criticism

问题重述

有 $N$ 座建筑，初始高度为 $A_i$。支持三种操作：

1. 修改：将第 $k$ 座建筑的高度改为 $w$
2. 查询：输出第 $k$ 座建筑的当前高度
3. 批评：给定区间 $[l, r]$（$r-l$ 为奇数），要求用最短时间将所有高度在 $[l, r]$ 内的建筑移出该区间，每次操作可将任意建筑高度 $\pm 1$（结果必须为正整数）。移动方式唯一，需要模拟这个过程。

关键性质

由于 $r-l$ 是奇数，区间 $[l, r]$ 的长度为偶数。设区间内有 $total$ 座建筑，则：

• $total$ 一定是偶数吗？不一定。$total$ 是指实际落在区间内的建筑数量，与区间长度无关。

但题目保证移动方式唯一：将区间内的建筑按高度排序后，较小的一半移动到 $l-1$，较大的一半移动到 $r+1$。

为什么这样是最优且唯一的？

• 对于高度 $h \in [l, r]$，移动到 $l-1$ 的距离为 $h - (l-1)$，移动到 $r+1$ 的距离为 $(r+1) - h$
• 总移动距离 = $\sum (h_i - (l-1)) + \sum ((r+1) - h_j)$
• 要最小化总距离，应该让较小的 $h$ 去左边，较大的 $h$ 去右边
• 如果 $total$ 是奇数，中间那个建筑去左边或右边距离相等，但题目用 $r-l$ 为奇数保证区间长度偶数，结合输入约束，实际 $total$ 处理时按 $\lfloor total/2 \rfloor$ 和 $\lceil total/2 \rceil$ 分配即可

---

核心数据结构设计

我们需要高效支持：

• 按高度快速找到区间 $[l, r]$ 内的所有建筑
• 批量修改这些建筑的高度
• 单点修改和查询

选择两个互补的数据结构：

1. cnt：map<ll, int>

• 键：高度
• 值：该高度的建筑数量
• 用途：快速找到所有高度在 $[l, r]$ 的种类，批量处理

2. positions：set<pair<ll, int>>

• 每个元素：(高度, 建筑编号)
• 按高度排序，同高度按编号排序
• 用途：快速找到区间内所有具体建筑，用于更新 $A$ 数组

---

操作详解

初始化

for (int i = 1; i <= N; i++) {
    cnt[A[i]]++;
    positions.insert({A[i], i});
}

操作 1：修改 modify(k, w)

void modify(int k, ll w) {
    ll old_h = A[k];
    if (old_h == w) return;
    
    remove_height(old_h, k);  // 从两个结构中删除
    add_height(w, k);         // 添加到两个结构中
    A[k] = w;                 // 更新数组
}

remove_height 实现细节：

• 从 cnt 中减少计数，若减到 $0$ 则删除该键
• 从 positions 中删除 (old_h, k)

add_height 实现细节：

• cnt[w]++
• positions.insert({w, k})

复杂度：$O(\log M)$，$M$ 为不同高度的数量

操作 2：查询 query(k)

直接返回 $A[k]$，$O(1)$

操作 3：批评 criticize(l, r)

这是核心操作，分四个步骤：

步骤 1：收集区间内的所有高度种类

auto it_low = cnt.lower_bound(l);   // 第一个 >= l 的高度
auto it_high = cnt.upper_bound(r);  // 第一个 > r 的高度

vector<pair<ll, int>> to_process;  // (高度, 数量)
ll total = 0;

for (auto it = it_low; it != it_high; ++it) {
    to_process.push_back({it->first, it->second});
    total += it->second;
}

步骤 2：从 cnt 中删除这些高度段

cnt.erase(it_low, it_high);  // 批量删除

步骤 3：计算新高度并分配到 cnt

ll left_count = total / 2;   // 去左边的建筑数量
ll right_count = total - left_count;  // 去右边的数量
ll new_left = l - 1;
ll new_right = r + 1;

ll idx = 0;  // 已分配的建筑数
for (auto [h, c] : to_process) {  // 遍历时高度递增
    if (idx + c <= left_count) {
        // 这批建筑全部去左边
        cnt[new_left] += c;
        idx += c;
    } else if (idx >= left_count) {
        // 这批建筑全部去右边
        cnt[new_right] += c;
        idx += c;
    } else {
        // 部分去左边，部分去右边
        ll left_part = left_count - idx;
        ll right_part = c - left_part;
        if (left_part > 0) cnt[new_left] += left_part;
        if (right_part > 0) cnt[new_right] += right_part;
        idx += c;
    }
}

为什么这样分配：

• to_process 按高度递增顺序遍历
• 前 left_count 个建筑去左边，其余去右边
• 由于同一高度的建筑高度相同，可能需要拆分

步骤 4：更新 positions 和 $A$ 数组

// 收集区间内所有受影响的建筑（已按高度排序）
vector<pair<ll, int>> to_update;
for (auto it = positions.lower_bound({l, -1}); 
     it != positions.end() && it->first <= r; ) {
    to_update.push_back(*it);
    it = positions.erase(it);  // 边遍历边删除
}

// to_update 已经按高度排序（因为 set 是有序的）

// 重新分配新高度
for (int i = 0; i < (int)to_update.size(); i++) {
    ll new_h;
    if (i < left_count) {
        new_h = new_left;
    } else {
        new_h = new_right;
    }
    positions.insert({new_h, to_update[i].second});
    A[to_update[i].second] = new_h;  // 更新数组
}

---

正确性证明

唯一性

对于区间 $[l, r]$（$r-l$ 为奇数），最小化总移动距离的分配方式是唯一的：

设区间内有 $m$ 个建筑，高度为 $h_1 \le h_2 \le \dots \le h_m$。

移动方案：

• 对 $i = 1, \dots, \lfloor m/2 \rfloor$：将 $h_i$ 移到 $l-1$
• 对 $i = \lfloor m/2 \rfloor + 1, \dots, m$：将 $h_i$ 移到 $r+1$

当 $m$ 为奇数时，中间那个建筑移到 $l-1$ 或 $r+1$ 距离相等，但题目通过 $r-l$ 为奇数（区间长度为偶数）确保在输入约束下，所有建筑可以对称分配。

时间复杂度

• modify：$O(\log N)$
• query：$O(1)$
• criticize：$O(K \log N)$，其中 $K$ 是区间内的建筑数量

最坏情况下 $K = O(N)$，但每个建筑被批评后高度会变成区间端点，之后不会再进入新区间（除非新区间包含这些端点），实际运行效率较高。

---

示例模拟

以题目样例为例，跟踪 criticize(3, 6) 时发生了什么：

初始状态（第3次查询后）：

• 建筑：$[3, 6, 5, 6, 10]$
• $cnt$：$\{3:1, 5:1, 6:2, 10:1\}$
• $positions$：$(3,1), (5,3), (6,2), (6,4), (10,5)$

处理区间 $[3,6]$：

1. 收集：高度 $3,5,6$，共 $4$ 座建筑
2. $left\_count = 2$，$right\_count = 2$
3. 分配：
   • 高度 $3$ 和 $5$（较小的）去 $l-1=2$
   • 高度 $6,6$（较大的）去 $r+1=7$
4. 更新后：
   • 建筑 $1$：$3 \to 2$
   • 建筑 $3$：$5 \to 2$
   • 建筑 $2,4$：$6 \to 7$
5. 最终：$[2,7,2,7,10]$

这就是题目说明中的结果。

---

总结

本题的核心技巧：

1. 理解批评的唯一最优策略：按高度排序后，较小的一半向左，较大的一半向右
2. 数据结构选择：
   • map 维护高度到数量的映射，用于批量处理
   • set 维护高度到位置的映射，用于更新具体建筑
3. 批量操作优化：使用迭代器范围删除和插入，避免逐个操作
4. 保持数据一致性：cnt、positions 和 $A$ 数组三者同步更新

这个解法充分利用了 C++ STL 的有序容器，在 $O(K \log N)$ 的时间内完成批评操作，其中 $K$ 是受影响的建筑数量，总复杂度可接受。