思路与算法

为每个原编号保存Xi。顺序统计线段树的叶子表示猴子是否仍在，内部节点保存存活人数；根据秩可在O(log N)内找到并删除某只猴子。维护当前轮起点的存活秩rank和原编号start，本轮删除秩为(rank+X[start]-1) mod remaining。删除后下一起点秩就是该删除秩在新人数下取模。为直接取得下一起点的原编号，再用只向右连的后继并查集跳过已删除编号，到N末尾后从1查找。最后剩下的start即大王。

正确性说明

对每轮归纳，rank与start共同表示当前存活环中从1开始报数的那只猴子。计数包含起点，所以报到X[start]的偏移是X[start]-1，模人数后得到准确的被删除者存活秩。顺序统计树各子树人数始终等于其中活猴数，下降时根据左子树人数选择第k只，故找到的原编号正确；沿路径减1仅删除此猴。下一轮必须从其下一位活猴开始，后继结构恰跳过全部已删编号并在末尾回绕，与新秩removedRank mod remaining一致。不变量由此保持，直到仅余一只，输出正确。N=1无需删除。

复杂度

读入、顺序树与后继数组初始化均O(N)，N-1次删除各O(log N)，只用路径压缩的后继查询取保守总界O(N log N)，加上顺序树删除，总O(N log N)，空间O(N)。顺序树补齐到不小于N的最小2次幂，容量仍小于4N个内部/叶子单元。

易错点

Xi取每轮开始报数者的原编号对应值，不取上一位离开者的Xi、不始终用X1。起点从1开始报数，偏移要减1；人数变小后必须取模。删除最后一个秩时下一轮回到首个存活者。后继数组保留N+1哨兵，不能递归遍历百万级删除链。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
struct Successor {
    vector<int> p;
    Successor(int n) : p(n + 2) {
        iota(p.begin(), p.end(), 0);
    }
    int find(int x) {
        int y = x;
        while (p[y] != y)
            y = p[y];
        while (p[x] != x) {
            int next = p[x];
            p[x] = y;
            x = next;
        }
        return y;
    }
};
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    if (!(cin >> n))
        return 0;
    vector<int> x(n + 1);
    for (int i = 1; i <= n; i++)
        cin >> x[i];
    int base = 1;
    while (base < n)
        base *= 2;
    vector<int> count(2 * base);
    for (int i = 0; i < n; i++)
        count[base + i] = 1;
    for (int i = base - 1; i; i--)
        count[i] = count[i * 2] + count[i * 2 + 1];
    Successor alive(n);
    int remaining = n, start = 1, rank = 0;
    while (remaining > 1) {
        int removedRank = (rank + x[start] - 1) % remaining, k = removedRank + 1, p = 1;
        count[p]--;
        while (p < base) {
            if (k <= count[p * 2])
                p *= 2;
            else {
                k -= count[p * 2];
                p = p * 2 + 1;
            }
            count[p]--;
        }
        int removed = p - base + 1;
        alive.p[removed] = alive.find(removed + 1);
        start = alive.find(removed + 1);
        if (start == n + 1)
            start = alive.find(1);
        remaining--;
        rank = removedRank % remaining;
    }
    cout << start << '\n';
}