问题分析

我们需要动态维护 $n$ 名司机的驾驶公里数，并回答能否用 $c$ 辆卡车完成 $s$ 公里的行程。

关键约束：

• 司机可以随时换车
• 卡车可以载任意多乘客
• 每个司机有最大驾驶公里数 $a_i$
• 需要 $c$ 辆卡车，行程 $s$ 公里

核心转化

问题转化

设我们有 $c$ 辆卡车，每辆卡车需要完成 $s$ 公里的驾驶。由于司机可以随时换车，问题等价于：

能否选择 $c$ 名司机，使得他们的驾驶公里数之和至少为 $c \times s$？

证明

设选择的 $c$ 名司机驾驶公里数为 $a_1, a_2, \ldots, a_c$。

充分性： 如果 $\sum_{i=1}^c a_i \geq c \times s$，我们可以这样安排：

1. 每名司机一开始驾驶一辆卡车
2. 当某司机达到其极限时，停车换人
3. 由于总驾驶能力足够，可以完成行程

必要性： 如果 $\sum_{i=1}^c a_i < c \times s$，总驾驶能力不足，无法完成。

进一步转化

从所有司机中选择 $c$ 名司机，使得他们的驾驶公里数之和最大。这等价于：

选择驾驶公里数最大的 $c$ 名司机，检查他们的和是否 $\geq c \times s$

算法设计

数据结构需求

我们需要支持：

1. 更新某个司机的驾驶公里数
2. 查询最大的 $c$ 个值的和

树状数组 + 离散化

使用两个树状数组：

• indx：记录每个值有多少司机
• val：记录每个值的司机驾驶公里数总和

离散化： 由于 $a_i \leq 10^9$，但只有 $m$ 次更新，我们将所有出现的 $y$ 值离散化。

特殊处理： 将值按从大到小排序，这样查询时可以快速找到前 $c$ 大的值。

代码详解

数据结构

template <typename T>
struct BIT {
    T c[MAXN];
    static int lowbit(const int &x) {
        return x & -x;
    }
    void update(int pos, const int &val) {
        while (pos <= tot) {
            c[pos] += val;
            pos += lowbit(pos);
        }
    }
    T query(int pos) const {
        T rv = 0;
        while (pos) {
            rv += c[pos];
            pos -= lowbit(pos);
        }
        return rv;
    }
};

BIT<int> indx;        // 数量统计
BIT<long long> val;   // 值统计

预处理

int n, q;
rd(n), rd(q);

// 读取所有查询，同时收集所有y值用于离散化
for (int i = 1; i <= q; ++i)
    rd(qur[i].op), rd(qur[i].x), rd(qur[i].y), b[i] = qur[i].y;

// 从大到小排序并去重
sort(b + 1, b + q + 1, greater<int>());
tot = (int)(unique(b + 1, b + q + 1) - b - 1);

主循环

long long cursm = 0;  // 所有司机驾驶公里数总和

for (int i = 1, x, y, rnky; i <= q; ++i) {
    x = qur[i].x, y = qur[i].y;
    // 在离散化数组中查找y的排名（从大到小）
    rnky = (int)(lower_bound(b + 1, b + tot + 1, y, greater<int>()) - b);
    
    if (qur[i].op == 'U') {  // 更新操作
        if (rnka[x])  // 如果该司机已有记录，先删除
            indx.update(rnka[x], -1), val.update(rnka[x], -a[x]);
        
        // 添加新记录
        indx.update(rnky, 1), val.update(rnky, y);
        cursm += y - a[x], a[x] = y, rnka[x] = rnky;
    } else {  // 查询操作
        // 关键公式：检查能否完成
        puts((long long)(x - indx.query(rnky)) * y + val.query(rnky) <= cursm ? "TAK" : "NIE");
    }
}

关键公式解析

(long long)(x - indx.query(rnky)) * y + val.query(rnky) <= cursm

变量解释：

• x：需要的卡车数 $c$
• y：行程公里数 $s$
• rnky：值 $y$ 在离散化数组中的排名
• indx.query(rnky)：驾驶公里数 $\geq y$ 的司机数量
• val.query(rnky)：驾驶公里数 $\geq y$ 的司机驾驶公里数总和
• cursm：所有司机驾驶公里数总和

公式意义：

1. 驾驶公里数 $\geq y$ 的司机可以直接使用
2. 还需要 $x - \text{indx.query(rnky)}$ 名司机
3. 这些司机的驾驶公里数至少为 $y$（否则就不是前 $c$ 大了）
4. 因此所需的最小总驾驶能力为： [ \text{val.query(rnky)} + (x - \text{indx.query(rnky)}) \times y ]
5. 如果这个值 $\leq \text{cursm}$，则可行

为什么正确？

• 如果所有司机的驾驶公里数都 $\geq y$，那么直接选最大的 $c$ 个即可
• 如果有些司机驾驶公里数 $< y$，我们需要用多个司机接力完成一辆卡车的行程
• 最坏情况下，每个驾驶公里数 $< y$ 的司机只能贡献 $a_i$ 公里
• 但我们可以用驾驶公里数 $\geq y$ 的司机填补缺口

复杂度分析

时间复杂度

• 预处理：$O(m \log m)$ 排序
• 每个操作：$O(\log m)$ 树状数组操作
• 总复杂度：$O(m \log m)$

空间复杂度

• $O(m)$ 存储离散化数组
• $O(m)$ 树状数组

正确性证明

定理

对于查询 $(c, s)$，答案是 TAK 当且仅当： [ \text{最大的 } c \text{ 个驾驶公里数之和} \geq c \times s ]

证明

设 $a_1 \geq a_2 \geq \cdots \geq a_n$ 为所有司机的驾驶公里数。

情况1：$a_c \geq s$

• 前 $c$ 名司机每人至少能驾驶 $s$ 公里
• 总驾驶能力 $\geq c \times s$
• 公式中 indx.query(rnky) >= c，成立

情况2：$a_c < s$

• 前 $k$ 名司机驾驶公里数 $\geq s$，$k < c$
• 需要 $c-k$ 名额外司机，每名至少贡献 $a_i$
• 所需最小总能力为： [ \sum_{i=1}^k a_i + (c-k) \times s ]
• 这正是公式计算的值

示例分析

样例输入

3 8
U 1 5    # 司机1: 5公里
U 2 7    # 司机2: 7公里
Z 2 6    # 查询: 2辆车, 6公里

第一次查询时：

• 司机驾驶公里数：5, 7
• 最大的2个值：7, 5，和=12
• 需要：2×6=12
• 正好相等，但公式检查时会发现不足（因为需要至少6公里的司机）

实际计算：

• rnky 对应值6的排名
• indx.query(rnky) = 1（只有司机2≥6）
• val.query(rnky) = 7
• 需要的最小总能力：7 + (2-1)×6 = 13
• 实际总能力：5+7=12 < 13
• 输出 NIE

算法优势

1. 高效：$O(m \log m)$ 处理百万级数据
2. 简洁：核心公式简单易懂
3. 正确：基于严格的数学推导
4. 实用：使用离散化处理大值域