题目分析

这是一个需要高效处理大量价格更新操作的问题。有两种操作：

• INFLATION x：所有价格增加 $x$
• SET x y：将所有价格为 $x$ 的菜品改为 $y$

直接模拟每次操作会超时，需要设计更高效的算法。

算法思路

核心思想

使用偏移量技巧 + 频率统计来优化操作：

1. 偏移量 tag：记录累计的通胀值，避免频繁更新所有价格
2. 频率映射 p：用 map 记录每个"基准价格"出现的次数
3. 总和维护 su：维护当前总价格和，每次操作增量更新

关键观察

• INFLATION 操作只需更新偏移量和总和，时间复杂度 $O(1)$
• SET 操作通过映射找到对应价格的数量，时间复杂度 $O(\log n)$

代码详解

数据结构定义

map<int,int> p;  // 记录基准价格 -> 出现次数
int tag;         // 累计通胀偏移量
int su;          // 当前总价格和
int n, q;        // 菜品数量和操作次数

初始化

n = r();
for(ri i = 1; i <= n; ++i){
    int a = r();
    su += a;
    ++p[a];  // 记录初始价格分布
}

处理操作

while(q--){
    string op = gs();
    if(op[0] == 'S'){  // SET操作
        int x = r(), y = r();
        // 计算基准价格（考虑偏移量）
        int base_price = x - tag;
        // 获取该价格的数量
        int cnt = p[base_price];
        // 更新映射
        p[base_price] = 0;
        p[y - tag] += cnt;
        // 更新总和：数量 × (新价格 - 原价格)
        su += cnt * (y - x);
    } else {  // INFLATION操作
        int x = r();
        su += x * n;  // 总和增加 x × 菜品数量
        tag += x;     // 记录累计通胀
    }
    wln(su);  // 输出当前总和
}

算法原理

偏移量技巧

实际价格 = 基准价格 + 偏移量 tag

• 初始时：tag = 0，基准价格就是实际价格
• INFLATION x：tag += x，所有实际价格隐式增加 $x$
• SET x y：需要找到基准价格 = x - tag 的菜品

复杂度分析

时间复杂度

• 初始化：$O(n \log n)$
• 每个 SET 操作：$O(\log n)$
• 每个 INFLATION 操作：$O(1)$
• 总复杂度：$O((n + q) \log n)$

空间复杂度

• $O(n)$ 存储价格分布