问题深入分析

我们有一个动态变化的评测队列，需要支持两种操作：

1. 查询操作：找到当前队列中位置$l_i$到$r_i$的测试点的原始编号
2. 删除操作：删除这些位置上的测试点（每隔一个删除一个）

关键难点：

• $m$可达$10^{18}$，无法直接存储整个队列
• $n$可达$10^5$，需要高效算法
• 删除操作会改变后续位置对应的测试点

核心思路：线段树+懒标记

1. 问题转化

将问题转化为维护一个动态序列，支持：

• 查找第k大：找到当前序列中第$k$个位置的原始值
• 区间删除：删除指定区间内每隔一个的元素

2. 数据结构设计

使用动态开点线段树，每个节点维护：

• sz：当前区间剩余的测试点数量
• c, d：懒标记，用于批量处理删除操作

懒标记的含义：

• c：删除的起始偏移量
• d：删除的间隔（每次删除$2^d$个元素中的1个）

3. 算法原理

查找操作

il int find(int i, int l, int r, int k) {
    if (l == r) return l;
    // 下推懒标记
    pushdown(i, l, r);
    int mid = (l + r) >> 1;
    int sl = ls ? t[ls].sz : mid - l + 1;
    if (sl >= k) {
        return find(ls, l, mid, k);
    } else {
        return find(rs, mid + 1, r, k - sl);
    }
}

原理：在动态开点线段树中查找第$k$个剩余元素的位置。

删除操作

il void update(int i, int l, int r, int L, int R) {
    if (L > r || R < l || !t[i].sz) return;
    
    if (L <= l && r <= R) {
        int s = t[i].sz;
        add(i, C, D);  // 应用删除
        if (s & 1) C = 3 - C;  // 调整偏移量
        return;
    }
    // 递归处理子区间
    // ...
}

删除模式：在区间$[L,R]$内，删除位置为$L, L+2, L+4, \ldots, R$的元素。

详细算法步骤

步骤1：初始化

n = rd(); m = rd();
t.tot = 1;
t.t[1].sz = m;
t.t[1].c = 1;

创建根节点，初始包含$m$个测试点。

步骤2：处理每个操作

对于每个操作$(l_i, r_i)$：

1. 查找端点：

   int posl = t.find(1, 1, m, l);
   int posr = t.find(1, 1, m, r);
   

   找到当前队列中位置$l$和$r$对应的原始编号。

2. 输出结果：

   wr(posl), put(' '), wr(posr), put('\n');
   

   输出最小值和最大值（由于是等差数列，端点即为极值）。

3. 执行删除：

   C = 2; D = 1;
   t.update(1, 1, m, posl, posr);
   

   删除区间内每隔一个的测试点。

步骤3：懒标记处理

il void add(int i, int c, int d) {
    if (!t[i].sz) return;
    
    t[i].c += (c - 1) * (1ll << t[i].d);
    t[i].d = min(t[i].d + d, 63ll);
    
    if (t[i].sz >= c)
        t[i].sz = (1 + ((t[i].sz - c) >> d));
    else
        t[i].sz = 0;
}

数学原理：

• 初始区间长度为$sz$
• 删除模式：从第$c$个开始，每隔$2^d$个删除1个
• 剩余数量：$\lfloor \frac{sz - c}{2^d} \rfloor + 1$

正确性证明

定理1：查找操作正确性

对于任意剩余测试点集合，find操作能正确返回第$k$个剩余测试点的原始编号。

证明：

• 基础：当区间长度为1时，直接返回位置
• 归纳：根据左右子树的剩余数量决定搜索方向
• 维护：懒标记正确传递了删除信息

定理2：删除操作正确性

删除操作正确移除指定区间内每隔一个的测试点。

证明： 设区间$[L,R]$长度为$len = R-L+1$，要删除的位置为：

$$L, L+2, L+4, \ldots, R$$

删除数量为：

$$\left\lceil \frac{len}{2} \right\rceil$$

懒标记(c,d)正确编码了这种删除模式。

定理3：复杂度正确性

算法在$O(n \log m)$时间内完成所有操作。

证明：

• 每次查找：$O(\log m)$
• 每次更新：$O(\log m)$
• 总操作数：$2n$
• 总复杂度：$O(n \log m)$

样例验证

样例1详细分析

输入：

2 10
2 8
1 3

初始状态：队列 = $[1,2,3,4,5,6,7,8,9,10]$

操作1：$l=2, r=8$

• 查找：位置2→原始2，位置8→原始8
• 输出：2 8
• 删除：位置2,4,6,8 → 删除测试点2,4,6,8
• 新队列：$[1,3,5,7,9,10]$

操作2：$l=1, r=3$

• 查找：位置1→原始1，位置3→原始5
• 输出：1 5
• 删除：位置1,3 → 删除测试点1,5
• 新队列：$[3,7,9,10]$

样例2验证

输入：

4 6
1 1
1 1  
1 1
2 2

逐步验证输出符合预期，证明算法正确性。

复杂度分析

时间复杂度

• 查找操作：每次$O(\log m)$，共$2n$次 → $O(n \log m)$
• 更新操作：每次$O(\log m)$，共$n$次 → $O(n \log m)$
• 总复杂度：$O(n \log m)$

空间复杂度

• 动态开点线段树：$O(n \log m)$个节点
• 每个节点常数空间
• 总空间：$O(n \log m)$

算法优势

1. 处理大规模数据

• 支持$m = 10^{18}$的极端情况
• 仅使用$O(n \log m)$空间

2. 高效更新

• 懒标记实现批量删除
• 避免逐个操作的低效性

3. 数学优化

• 利用等差数列性质快速找到极值
• 通过位运算加速删除计算

扩展应用

该算法可推广到其他类似问题：

1. 动态序列维护：支持查找和间隔删除
2. 资源调度：按规则释放资源并查询状态
3. 数据压缩：按模式选择性删除数据

总结

本题通过巧妙的动态开点线段树结合懒标记技术，高效解决了大规模动态序列的查询和删除问题。核心创新点包括：

1. 懒标记编码：用(c,d)对编码复杂的删除模式
2. 动态开点：支持极端大规模数据范围
3. 数学优化：利用位运算加速计算

算法在$O(n \log m)$的时间复杂度内解决问题，适用于竞赛中的极端数据规模，体现了高级数据结构在解决复杂动态问题中的强大能力。