Codeforces 312E A Simple Task：26 線段樹 + 延遲標記處理區間排序

題目大意

長度 n (≤10^5) 的小寫字母字符串，q (≤5×10^4) 次操作：區間 [l, r] 升序 (k=1) 或降序 (k=0) 排列。輸出最終字符串。

核心數據結構

建立 26 棵線段樹，每棵維護一個字母在區間內的出現次數。節點存 sum（區間計數）與 cover（延遲標記：-1 無標記，0 全 0，1 全 1）。

操作流程

1. 查詢：對 26 棵樹查詢 [l, r] 區間各字母計數 cnt[0..25]。
2. 清零：將 [l, r] 區間 26 棵樹計數全部設為 0（延遲標記 cover=0）。
3. 重建：按 k 決定順序。設 pos = l。遍歷字母 c：若 cnt[c]>0，將 [pos, pos+cnt[c]-1] 在第 c 棵樹設為 1（cover=1），pos += cnt[c]。

複雜度

單次操作：26 次查詢 + 26 次清零 + 至多 26 次重建 = 78 次線段樹操作。
總時間 O(26 q log n) ≈ 10^7，5 秒時限下 C++ 輕鬆通過。

關鍵代碼片段