BZOJ 3878 [AHOI2014] 奇怪的計算器：線段樹區間線性變換

題目大意

有 q 個初始數值，依次進行 n 次操作（+x, -x, *x, @x 取模），每次操作後將超出 [L, R] 範圍的值截斷至邊界。求最終 q 個數值（按原順序輸出）。

核心洞察

1. 單調性保持： 四種操作均為單調函數，若初始 x ≤ y，操作後仍保持 x' ≤ y'。因此可將 q 個數排序，構建線段樹維護有序序列。
2. 區間線性變換： 每次操作等價於對區間應用 `f(x) = a*x + b`。
   • +x: a=1, b=x
   • -x: a=1, b=-x
   • *x: a=x, b=0
   • @x: 非線性，但可拆解為：先對整個區間應用 f(x)=x，再將超出範圍的部分單獨處理（見下）。
3. 截斷處理： 維護節點的 `min`、`max`。若 `max ≤ R` 且 `min ≥ L` 無需截斷。否則遞歸下推，對超出部分賦值為邊界常數（等價於 a=0, b=L/R）。

線段樹節點設計

struct Node {
    Node *ls, *rs;
    long long a, b;     // 懶標記：f(x) = a*x + b
    long long mn, mx;   // 區間最小/最大值
    Node(): ls(nullptr), rs(nullptr), a(1), b(0), mn(0), mx(0) {}
    
    void apply(long long na, long long nb) { // 應用線性變換
        mn = na * mn + nb;
        mx = na * mx + nb;
        if (na < 0) swap(mn, mx); // 斜率為負時翻轉
        a = na * a;
        b = na * b + nb;
    }
    
    void pushdown() {
        if (a != 1 || b != 0) {
            ls->apply(a, b);
            rs->apply(a, b);
            a = 1; b = 0;
        }
    }
};

關鍵操作

• 建樹： 對排序後的數組建樹，葉子節點存初始值。
• 區間加法/乘法： 標準懶標記區間更新。
• 取模 @x： 對於線段樹中 `mx - mn < x` 的節點，`@x` 等價於不變；否則遞歸到葉子單點修改。利用 `mx - mn` 剪枝。
• 截斷 L/R： 若 `mn < L`，遞歸將左側 `< L` 部分賦值為 L；`mx > R` 同理。
• 查詢： 按原順序查找每個值在排序數組中的位置，下推標記查詢葉子值。

複雜度

• 建樹：O(q log q)
• 每次操作：均攤 O(log q)（截斷和取模利用單調性剪枝）
• 總體：O((n+q) log q)