POJ 2761 Feed the Dogs：區間第 K 小（Treap + 離線處理）

問題大意

n 隻狗排成一排，每隻有漂亮值（越小越漂亮）。m 次餵食，每次給區間 [i,j] 中第 k 漂亮的狗餵食。區間之間不包含關係（可相交）。求每次餵食的狗的漂亮值。n ≤ 100,000, m ≤ 50,000。

離線 + Treap 解法

區間不包含關係意味著可按左端點排序，滑動窗口維護當前區間內的狗。用 Treap（隨機化平衡二叉搜索樹）支持插入、刪除、查詢第 k 小，均攤 O(log n)。

處理流程

1. 讀入查詢，按 l 升序、r 升序排序。
2. 維護當前區間 [curL, curR]，移動邊界時對應插入/刪除 Treap 節點。
3. 每次查詢直接在 Treap 中找第 k 小值輸出。

Treap 關鍵操作

void rotateRight(int &k) { // 右旋
    int tmp = t[k].l; t[k].l = t[tmp].r; t[tmp].r = k;
    pushup(k); k = tmp;
}
void insert(int &k, int x) { // 插入
    if (!k) { k = ++tot; t[k] = {0,0,1,rand(),x,1}; return; }
    t[k].s++;
    if (t[k].v == x) t[k].w++;
    else if (t[k].v > x) { insert(t[k].l, x); if (t[t[k].l].rnd < t[k].rnd) rotateRight(k); }
    else { insert(t[k].r, x); if (t[t[k].r].rnd < t[k].rnd) rotateLeft(k); }
}
int kth(int k, int x) { // 第 x 小
    int lsz = t[t[k].l].s;
    if (x <= lsz) return kth(t[k].l, x);
    if (x <= lsz + t[k].w) return t[k].v;
    return kth(t[k].r, x - lsz - t[k].w);
}

注意事項

刪除操作需正確維護 s（子樹大小）和 w（重複計數）。調試時曾因忘記 s-- 導致 WA。