240-F 题目大意

给定一个长为\(n\)的字符串，由小写字母组成。由\(m\)次操作，每次操作给定一个区间\([l,r]\)，要求你把区间中的字符进行重新排列，要求重排后的子串是字典序最小的回文串，如果无法得到回文串则忽略这次操作。

输出\(m\)次操作之后的字符串。

Solution

涉及区间操作，考虑用线段树来处理。建\(26\)棵线段树，每棵线段树维护其对应字符在各个位置上的出现情况。

对于每次操作的区间\([l,r]\)，对\(26\)棵线段树求和得到这个区间中各个字符的出现次数，先排除掉无法构造出回文串的情况。如果区间长为奇数，则需要把出现次数为奇数的那个字符单独放在中间的位置上，剩余的字符各自的数量都是偶数，按字典序从小到大来放置字符。设当前放置的字符\(ch\)的数量为\(cnt\)，则需要把前面一段长为\(cnt/2\)后面对应一段长为\(cnt/2\)的区间赋值为字符\(ch\)，即在\(ch\)对应的线段树上推平这两个区间。

线段树要支持区间推平和区间求和的操作，加上懒标记即可，时间复杂度\(O((n+m)logn·C)\)，\(C\)是字符集的大小。

#include<bits/stdc++.h>
using namespace std;
using ll=long long;

const int N=1e5+10;
struct node{
    int l,r,tag,sum;
}tr[26][N<<2];

void pushup(int p,int u){
    tr[p][u].sum=tr[p][u<<1].sum+tr[p][u<<1|1].sum;
}

void pushdown(int p,int u){
    if(tr[p][u].tag!=-1){
        tr[p][u<<1].tag=tr[p][u<<1|1].tag=tr[p][u].tag;
        tr[p][u<<1].sum=(tr[p][u<<1].r-tr[p][u<<1].l+1)*tr[p][u].tag;
        tr[p][u<<1|1].sum=(tr[p][u<<1|1].r-tr[p][u<<1|1].l+1)*tr[p][u].tag;
        tr[p][u].tag=-1;
    }
}

void build(int p,int u,int l,int r){
    tr[p][u]={l,r,-1,0};
    if(l==r) return;
    int m=(l+r)>>1;
    build(p,u<<1,l,m);
    build(p,u<<1|1,m+1,r);
    pushup(p,u);
}

void modify(int p,int u,int l,int r,int k){
    if(l<=tr[p][u].l&&tr[p][u].r<=r){
        tr[p][u].tag=k;
        tr[p][u].sum=(tr[p][u].r-tr[p][u].l+1)*k;
        return;
    }
    pushdown(p,u);
    int m=(tr[p][u].l+tr[p][u].r)>>1;
    if(l<=m) modify(p,u<<1,l,r,k);
    if(r>m) modify(p,u<<1|1,l,r,k);
    pushup(p,u);
}

int query(int p,int u,int l,int r){
    if(l<=tr[p][u].l&&tr[p][u].r<=r){
        return tr[p][u].sum;
    }
    pushdown(p,u);
    int m=(tr[p][u].l+tr[p][u].r)>>1;
    int res=0;
    if(l<=m) res+=query(p,u<<1,l,r);
    if(r>m) res+=query(p,u<<1|1,l,r);
    return res;
}

void solve(){
    int n,m;
    cin>>n>>m;
    for(int i=0;i<26;i++) build(i,1,1,n);
    string s;
    cin>>s;
    for(int i=0;i<n;i++){
        modify(s[i]-'a',1,i+1,i+1,1);
    }
    while(m--){
        int l,r;
        cin>>l>>r;
        vector<int> cnt(26);
        int odd=0,ch=0;
        for(int i=0;i<26;i++){
            cnt[i]=query(i,1,l,r);
            if(cnt[i]&1){
                odd++;
                ch=i;
            }
        }
        if(odd>1) continue;
        for(int i=0;i<26;i++){
            modify(i,1,l,r,0);
        }
        if(odd){
            cnt[ch]--;
            modify(ch,1,(l+r)>>1,(l+r)>>1,1);
        }
        for(int i=0;i<26;i++){
            if(cnt[i]){
                modify(i,1,l,l+cnt[i]/2-1,1);
                l+=cnt[i]/2;
                modify(i,1,r-cnt[i]/2+1,r,1);
                r-=cnt[i]/2;
            }
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=0;j<26;j++){
            if(query(j,1,i,i)){
                cout<<char(j+'a');
                break;
            }
        }
    }
}

int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    freopen("input.txt","r",stdin);
	freopen("output.txt","w",stdout);
    int T=1;
    //cin>>T;
    while(T--){
        solve();
    }
    return 0;
}