Codeforces 240F TorCoder：線段樹維護字母統計構造回文

問題描述

長度 n（≤1e5）字符串，m（≤1e5）次操作。每次給區間 [l, r]，重排該區間字符使其成為字典序最小的回文串（若無法構成回文則忽略）。最終輸出字符串。

線段樹設計

• 每個節點維護 26 個字母在該區間的計數 sum[26]。
• 懶標記 add：-1 表示無，0~25 表示該區間統一設置為某字母（用於構造回文時批量賦值）。
• push_down 將懶標記下推給子節點，更新其 sum。

操作流程

1. query(l, r) 統計區間內各字母計數 cs[26]。
2. 判斷能否成回文：至多一個字母計數為奇數。若超過 1 個奇數，跳過。
3. 構造字典序最小回文：
   • 從 'a' 到 'z' 遍歷，對每字母 c，取一半 cs[c]/2 放左側，一半放右側（對稱位置）。
   • 若有奇數字母，放中間。
   • 用 update(char, L, R) 批量設置區間字符。

關鍵代碼片段

void update(int id, int L, int R, int l, int r, int rt) {
    if (L<=l && r<=R) { cls(rt); add[rt]=id; sum[id][rt]=r-l+1; return; }
    push_down(l,r,rt);
    int m=(l+r)/2;
    if (L<=m) update(id,L,R,lson);
    if (R>m) update(id,L,R,rson);
    push_up(rt);
}
void solve(int L, int R) {
    memset(cs,0,sizeof(cs));
    query(L,R,1,n,1);
    int odd=0, midChar=-1;
    for(int i=0;i<26;i++) if(cs[i]%2){ odd++; midChar=i; }
    if(odd>1) return;
    int st=L, en=R, mid=L+(R-L+1)/2;
    for(int i=0;i<26;i++) if(cs[i]) {
        if(cs[i]/2) {
            update(i, st, st+cs[i]/2-1, 1,n,1);
            update(i, en-cs[i]/2+1, en, 1,n,1);
            st += cs[i]/2; en -= cs[i]/2;
        }
        if(cs[i]%2) update(i, mid, mid, 1,n,1);
    }
}

複雜度

每次操作 query + 26 次 update，均為 O(log n)。總 O(m * 26 log n) ≈ 5e6 操作，3s 內輕鬆通過。