Overview

Among the children remaining in the circle, the ball is passed from the current holder to the \(D_i\)-th child, after which the holder leaves. This operation is performed \(M\) times.

We use a Fenwick Tree (BIT) to efficiently manage the remaining children and quickly find “the \(q\)-th child among those remaining.”

Analysis

Let \(k\) be the number of people currently remaining in the circle, and \(x\) be the child holding the ball.

When the remaining children are arranged in order of their numbers (i.e., clockwise order), suppose \(x\) is at position \(rank\) among them.

For example, if the remaining children’s numbers are

\[ [1, 3, 4, 7, 8] \]

and the child currently holding the ball is \(4\), then \(4\) is the \(3\)rd, so \(rank = 3\).

In this case, the order of counting clockwise starting from the next child after \(x\), in terms of rank, is

\[ rank+1, rank+2, \ldots, k, 1, 2, \ldots, rank-1 \]

However, since \(x\) itself is not counted, the number of people that can be counted is \(k-1\).
Therefore, even if \(D_i\) is very large, it suffices to consider only

\[ (D_i - 1) \bmod (k - 1) \]

If we let \(q\) be the “rank among remaining children” of the recipient, then

\[ q = (rank + (D_i - 1) \bmod (k - 1)) \bmod k + 1 \]

gives us the answer.

Then, we just need to quickly find the number of the child who is \(q\)-th among the remaining children.

If we naively manage the remaining children with a list, deletion and finding the \(q\)-th element take \(O(N)\), resulting in \(O(NM)\) overall.
Since the constraints are \(N, M \leq 2 \times 10^5\), this is too slow.

Therefore, we use a Fenwick Tree to:

• Manage whether each child is remaining using \(1/0\)
• Update \(1\) to \(0\) when a child leaves
• Find the \(q\)-th remaining child using a binary search-like approach

Algorithm

On the Fenwick Tree, for each child we manage:

• \(1\) if remaining
• \(0\) if removed

In the initial state, everyone is remaining, so all values are \(1\).

We maintain the following variables:

• cur: the number of the child currently holding the ball
• rank: the position of cur among the remaining children
• k: the number of children currently remaining

For each pass, we perform the following operations:

1. Find the rank \(q\) of the child who will receive the ball next

$\( q = (rank + (D_i - 1) \bmod (k - 1)) \bmod k + 1 \)$

1. Use the Fenwick Tree to find the number of “the \(q\)-th child among those remaining”

2. Remove the current ball holder cur from the Fenwick Tree

3. Update the rank rank of the new ball holder

Before deletion, the rank of the new holder is \(q\), and the rank of the current holder being removed is rank.

• If \(q > rank\):
  The child being removed is before the new holder, so the new holder’s rank shifts back by \(1\).

  $\( rank = q - 1 \)$

• If \(q < rank\):
  The child being removed is after the new holder, so the rank does not change.

  $\( rank = q \)$

Note that since the ball is never passed to oneself, \(q = rank\) never occurs.

1. Update cur to the new holder and decrease \(k\) by \(1\)

Repeat this \(M\) times and output the final cur.

Complexity

• Time complexity: \(O(N + M \log N)\)
• Space complexity: \(O(N)\)

Implementation Notes

With a Fenwick Tree, we can use prefix sums to find “the number of remaining children with index \(i\) or less.”

Furthermore, by performing binary search on the Fenwick Tree, we can find “the \(q\)-th remaining child” in \(O(\log N)\).

Also, since all children are remaining in the initial state, the Fenwick Tree can be initialized as follows:

tree = [0] + [i & -i for i in range(1, N + 1)]

This is a method to directly construct a Fenwick Tree with \(1\) at every position.

Although \(D_i\) can be as large as \(10^9\), there is no need to actually count through multiple laps.
We always use

\[ (D_i - 1) \bmod (k - 1) \]

to reduce the movement distance around the circle.

Source Code

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    N, M, S = data[0], data[1], data[2]

    tree = [0] + [i & -i for i in range(1, N + 1)]
    high = 1 << (N.bit_length() - 1)

    cur = S
    rank = S
    k = N
    p = 3

    for _ in range(M):
        D = data[p]
        p += 1

        q = (rank + (D - 1) % (k - 1)) % k + 1

        idx = 0
        need = q
        step = high
        while step:
            nxt = idx + step
            if nxt <= N and tree[nxt] < need:
                idx = nxt
                need -= tree[nxt]
            step >>= 1
        next_cur = idx + 1

        j = cur
        while j <= N:
            tree[j] -= 1
            j += j & -j

        if q > rank:
            rank = q - 1
        else:
            rank = q

        cur = next_cur
        k -= 1

    print(cur)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.5-high.