BZOJ 2002 [HNOI2010] Bounce 彈飛綿羊：Link-Cut Tree / Splay 動態維護路徑跳躍

問題建模

n 個裝置排成一排，第 i 個彈力係數 k_i，綿羊從 i 跳到 i+k_i，超出邊界即彈飛。兩類操作：
① 查詢：從 j 出發彈幾次彈飛？
② 修改：將第 j 個裝置係數改為 k。
n ≤ 200,000, m ≤ 100,000。

Link-Cut Tree 核心思想

將每個裝置視為節點，邊指向跳躍目標（i → i+k_i），形成一棵森林（指向超出邊界的節點無出邊）。查詢「彈飛次數」即路徑長度，修改係數即 cut 舊邊 + link 新邊。LCT 支援動態樹的路徑聚合查詢與連接/切斷，均攤 O(log n)。

Splay 實現關鍵點

• 每節點維護 sum：以該節點為根的 Splay 子樹大小（即路徑長度）。
• access(x)：將 x 到根的路徑掛為右鏈，斷開原右子樹並存入虛樹父指針 bef[]。
• query(x)：access(x); splay(x); 返回左子樹 sum + 1（含自身）。
• join(x, y)：若 y=0 則 cut(x)；否則檢查是否同樹（避免成環），不同樹則 cut(x); bef[x]=y;。

AC 代碼精簡版

struct LCT {
    int bef[N], pre[N], ch[N][2], sum[N], key[N];
    void pushup(int x) { sum[x] = key[x] + sum[ch[x][0]] + sum[ch[x][1]]; }
    void rotate(int x, int d) { ... } // 標準 Splay 旋轉
    void splay(int x) { ... }         // 伸展到虛樹根
    void access(int x) { ... }        // 訪問路徑構建優先路徑
    int query(int x) { access(x); splay(x); return sum[ch[x][0]] + 1; }
    void cut(int x) { access(x); splay(x); bef[ch[x][0]] = bef[x]; pre[ch[x][0]] = 0; ch[x][0] = 0; }
    void join(int x, int y) { if (!y) cut(x); else { access(y); splay(y); int tmp=x; while(pre[tmp]) tmp=pre[tmp]; if(tmp!=y) { cut(x); bef[x]=y; } } }
} lct;

int main() {
    int n; while(scanf("%d",&n)!=EOF) {
        lct.init();
        for(int i=1;i<=n;++i) {
            scanf("%d",&a[i]);
            lct.bef[i] = (a[i]+i>n) ? 0 : a[i]+i;
            lct.key[i] = lct.sum[i] = 1;
        }
        int m; scanf("%d",&m);
        while(m--) {
            int op; scanf("%d",&op);
            if(op==1) { int x; scanf("%d",&x); printf("%d\n", lct.query(x+1)); }
            else { int x,y; scanf("%d%d",&x,&y); x++; a[x]=y; lct.join(x, (x+y>n)?0:x+y); }
        }
    }
}

複雜度與優勢

每操作均攤 O(log n)，總複雜度 O((n+m) log n)，完美應對動態修改與路徑查詢混合場景，是動態樹問題的經典利器。