算法标签

$线段树$、$动态第k元素查询$、$模拟销牌发牌$、$O(N\log N)$高效查询

简要题解

核心问题是模拟“销牌+发牌”过程，本质是动态查找剩余牌库中第k个元素并删除。

1. 问题转化：每次销牌$R_i$次后取顶牌，等价于在当前剩余$cur$张牌中，找到第$(上一次发牌位置 + R_i) \mod cur$个元素（模为0时取第$cur$个）。
2. 线段树作用：维护每个区间的剩余牌数，支持$O(\log N)$时间查询第k个元素，并在查询后更新区间（删除该元素，减少对应区间牌数）。
3. 复杂度：线段树构建$O(N)$，每次查询+更新$O(\log N)$，总复杂度$O(N\log N)$，适配$N$达$7\times10^5$的大数据量。

带详细注解的代码

#include <iostream>
using namespace std;

int n;                  // 牌的总数量
int nodes[2097149];     // 线段树数组，大小为2^21（足够容纳7e5的两倍，避免越界）

// 构建线段树：id=当前节点编号，l=当前区间左边界，r=当前区间右边界
// 线段树每个节点存储对应区间内"剩余牌的数量"
void build(const int id, const int l, const int r) {
    nodes[id] = r - l + 1;  // 初始化：区间[l,r]有r-l+1张牌（未被发牌）

    if (l == r)  // 叶子节点：区间只有一张牌，无需递归
        return;

    int mid = (l + r) >> 1;  // 计算区间中点（等价于(l+r)/2，位运算更快）
    build(id << 1, l, mid);  // 递归构建左子树（id*2，区间[l,mid]）
    build(id << 1 | 1, mid + 1, r);  // 递归构建右子树（id*2+1，区间[mid+1,r]）
}

// 线段树查询：找到当前剩余牌中第k个元素的编号，并删除该元素（更新线段树）
inline int query(int k) {
    int id = 1;  // 从线段树根节点（编号1）开始查询
    int l = 1, r = n;  // 初始查询区间为[1,n]（所有牌的编号范围）

    while (true) {
        --nodes[id];  // 当前节点对应的区间少一张牌（即将删除查询到的牌）

        if (l == r)  // 找到目标牌（叶子节点，区间只有一张牌），返回其编号
            return l;

        id <<= 1;  // 进入左子树（先查左子树是否有足够的牌）
        int mid = (l + r) >> 1;  // 当前区间中点

        if (k <= nodes[id]) {  // 左子树剩余牌数 >= k，目标在左子树
            r = mid;  // 缩小查询区间为左子树[1,mid]
        } else {  // 左子树剩余牌数 < k，目标在右子树
            k -= nodes[id];  // 调整k：右子树中第k - 左子树牌数的位置
            id |= 1;  // 切换到右子树（id*2+1）
            l = mid + 1;  // 缩小查询区间为右子树[mid+1,r]
        }
    }
}

int main() {
    // 关闭输入输出同步，解除cin/cout绑定，加速大数据量读写
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);

    cin >> n;  // 读入牌的总数量
    build(1, 1, n);  // 构建线段树，维护[1,n]区间的牌数

    int cur = n;     // 当前剩余牌的数量（初始为n）
    int las = 1;     // 上一次发牌的位置（初始为1，即第一张牌的相对位置）
    int x;           // 存储每次的销牌次数R_i

    do {
        cin >> x;  // 读入第i次发牌前的销牌次数R_i
        // 计算当前要发的牌在剩余牌中的位置：(上一次位置 + 销牌次数) mod 当前牌数
        las = (las + x) % cur;
        if (!las)  // 若mod结果为0，说明是当前剩余牌的最后一张（位置为cur）
            las = cur;

        cout << query(las) << '\n';  // 查询第las张牌并输出，同时删除该牌
    } while (--cur);  // 剩余牌数减1，直到发完所有牌（cur从n减到1）

    return 0;
}