题目概述

本题需要模拟 $N$ 家商店的队列操作，处理三种类型的事件：

1. 加入：在区间商店末尾加入 $K_i$ 个来自团体 $C_i$ 的顾客
2. 离开：在区间商店开头移除 $K_i$ 个顾客
3. 服务：查询某个商店队列中第 $B_i$ 个顾客的团体编号

算法思路

核心洞察

问题的关键在于如何高效处理：

• 区间操作（加入、离开）
• 单点查询（服务）
• 时间顺序维护顾客的加入顺序

双线段树解法

代码采用了两个主要的数据结构：

1. SEG_1：队列长度维护

• 使用带懒惰传播的线段树维护每个商店当前的队列长度
• 支持区间加减操作（顾客加入和离开）
• 快速查询某个商店的队列长度

关键函数：

• modify(): 处理区间加入/离开操作
• query(): 查询队列长度，并计算目标顾客在历史中的位置

2. SEG_2：时间轴维护

• 使用树状数组维护按时间顺序的顾客加入操作
• 支持快速查询第 $k$ 个顾客是在哪个时间加入的

关键函数：

• modify(): 记录每个时间点的顾客数量变化
• query(): 二分查找找到第 $k$ 个顾客的加入时间

算法流程

1. 预处理阶段：

   • 读取所有操作
   • 对于服务操作，先通过 SEG_1 确定目标顾客在历史中的位置
   • 对于加入操作，记录操作的区间、团体和人数

2. 扫描线处理：

   • 按商店编号扫描
   • 维护每个商店的历史操作时间线
   • 对于每个服务查询，在对应商店的时间线中查找目标顾客

3. 结果输出：

   • 输出每个服务操作的结果

关键技巧

1. 队列长度与历史位置转换

i64 query(int a, i64 b) {
    i64 now = query(1, 1, N, a), all = 0;
    if (now < b) return 0;  // 队列长度不足
    // 计算目标顾客在历史中的位置
    return all - now + b;
}

2. 时间轴二分查找

int query(i64 val) {
    int i = 0;
    for (int j = q_; j; j >>= 1) {
        if (i + j <= Q && s[i + j] < val) {
            val -= s[i += j];
        }
    }
    return i + 1;  // 返回操作时间
}

3. 差分优化

• 使用树状数组维护前缀和，快速计算总顾客数
• 扫描线处理避免重复计算

复杂度分析

• SEG_1：每次操作 $O(\log N)$
• SEG_2：每次操作 $O(\log Q)$
• 总复杂度：$O(Q \log N + Q \log Q)$
• 空间复杂度：$O(N + Q)$

总结

本题通过巧妙的双数据结构设计，将复杂的队列模拟问题转化为：

• 线段树维护当前状态
• 树状数组维护历史记录