POJ 2886 Who Gets the Most Candies?：線段樹動態求第 k 大 (Josephus 變體)

問題描述

n 個小孩圍成一圈，每人持一數字 v_i。從第 k 個孩子開始出局。之後，若剛出局孩子的數字為 v，則下一個出局的是順時針（v>0）或逆時針（v<0）第 |v| 個未出局孩子。重複直到全員出局。第 p 個出局的孩子得 f(p) 分（f(p) 為 p 的因子個數）。求得分最高的孩子姓名及分數。

解題思路：線段樹維護「剩餘孩子」

1. 預計算分數：f(p) 為因數個數，篩法 O(n log n) 預處理 1..n 的因數數，記錄最大分數對應的出局順序 ids。
2. 線段樹結構：葉子節點對應初始位置 1..n，值為 1（在場）或 0（出局）。內部節點維護區間和（在場人數）。
3. 模擬出局過程：
   • 當前指針 pos（上一個出局者位置），當前圈內人數 mod。
   • 根據 v[pos] 計算下一個出局者在「剩餘孩子」中的順位 k：

     if (v[pos] > 0) k = ((k + v[pos] - 2) % mod + mod) % mod + 1;
     else            k = ((k + v[pos] - 1) % mod + mod) % mod + 1;
     

   • 線段樹查詢第 k 個 1 的位置 → 得到下一個出局者原始下標 pos。
   • 更新線段樹將該位置設 0，mod--，重複直到 mod=0。
4. 輸出：第 ids 個出局的孩子姓名及其分數。

關鍵代碼片段 (C++)

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 500010;

struct Child { char name[16]; int v; } child[MAXN];
int seg[MAXN<<2];  // 區間和
int score[MAXN];   // 因數個數

void build(int l, int r, int rt) {
    seg[rt] = r - l + 1;
    if (l == r) return;
    int mid = (l+r)>>1;
    build(l, mid, rt<<1);
    build(mid+1, r, rt<<1|1);
}

// 查詢並刪除第 k 個 1，返回原始下標
int query_del(int k, int rt) {
    seg[rt]--;
    if (seg[rt<<1] >= k) return query_del(k, rt<<1);
    else return query_del(k - seg[rt<<1], rt<<1|1);
}

int main() {
    int n, k;
    while (scanf("%d%d", &n, &k) == 2) {
        // 預處理因數個數
        fill(score, score+n+1, 0);
        for (int i = 1; i <= n; ++i)
            for (int j = i; j <= n; j += i)
                ++score[j];
        int best = 1;
        for (int i = 2; i <= n; ++i)
            if (score[i] > score[best]) best = i;

        for (int i = 1; i <= n; ++i)
            scanf("%s%d", child[i].name, &child[i].v);
        child[0].v = 0;

        build(1, n, 1);
        int mod = n;
        int pos = 0;  // 上一個出局者，初始為 0（虛擬）
        int target = best;  // 我們只關心第 best 個出局的是誰
        int ansPos = -1;

        for (int out = 1; out <= n; ++out) {
            int v = child[pos].v;
            if (v > 0) k = ((k + v - 2) % mod + mod) % mod + 1;
            else       k = ((k + v - 1) % mod + mod) % mod + 1;
            pos = query_del(k, 1);
            mod--;
            if (out == target) { ansPos = pos; break; }
        }
        printf("%s %d\n", child[ansPos].name, score[best]);
    }
    return 0;
}

複雜度分析

• 因數預處理：O(n log n)。
• 線段樹建樹：O(n)。
• 每次出局：查詢+更新 O(log n)，共 n 次 → O(n log n)。
• 總時間 O(n log n)，n ≤ 500,000 完全足夠。

總結

POJ 2886 是經典的「動態第 k 大」問題，利用線段樹維護剩餘元素的順序統計量。關鍵難點在於根據正負步長正確推導下一個出局者的排名公式，並處理循環取模。預先計算目標出局順序 best，模擬到該步即可停止，避免無用計算。代碼結構清晰，是線段樹應用的優秀範例。