题解 CF240F TorCoder

发表于 分类于 阅读次数： Valine： 本文字数： 2.8k 阅读时长 ≈ 3 分钟

考虑开 26 棵线段树。每棵线段树维护它对应的字母在这个字符串中的出现情况。

然后我们考虑，什么样的区间能转换成一个回文串呢？

这个区间中，出现的任何字母的出现次数要么都为偶数，要么只有一个奇数，其余都是偶数时，这个区间可以通过字母重排变为一个回文串。所以每棵线段树都需要支持区间求和以查询区间中特定字母的出现次数。

如果可以转换，怎么让这个区间重排之后字典序最小？

思想：字典序越小的字母，我们优先把它放前面就可以了。

具体来说，如果字母的出现次数中有一个奇数，那么先把出现了奇数次的这个字母单拎出来扔到中间。然后，为了保证字典序最小，我们从 aa 到 zz ，从两边到中间放即可。对于每个字母，一边放一半。因此我们的每棵线段树需要支持区间赋值的操作。

具体见代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
using namespace std;
const int N=1e5+5;
struct Segment{
    int l,r;
    int sum,tag;
}t[26][N<<2];
int n,m;
char s[N];
void pushup(int tr,int p) {
    t[tr][p].sum=t[tr][p<<1].sum+t[tr][p<<1|1].sum;
}
void pushdown(int tr,int p) {
    if(t[tr][p].tag!=-1) {
        t[tr][p<<1].tag=t[tr][p].tag;
        t[tr][p<<1|1].tag=t[tr][p].tag;
        t[tr][p<<1].sum=(t[tr][p<<1].r-t[tr][p<<1].l+1)*t[tr][p].tag;
        t[tr][p<<1|1].sum=(t[tr][p<<1|1].r-t[tr][p<<1|1].l+1)*t[tr][p].tag;
        t[tr][p].tag=-1;
    }
}
void build(int tr,int p,int l,int r) {
    t[tr][p].l=l;t[tr][p].r=r;
    t[tr][p].sum=0;t[tr][p].tag=-1;
    if(l==r) {
        t[tr][p].sum=(s[l]-'a')==tr;
        return ;
    }
    int mid=(l+r)>>1;
    build(tr,p<<1,l,mid);
    build(tr,p<<1|1,mid+1,r);
    pushup(tr,p);
}
void modify(int tr,int p,int l,int r,int val) {
    if(l<=t[tr][p].l&&t[tr][p].r<=r) {
        t[tr][p].tag=val;
        t[tr][p].sum=(t[tr][p].r-t[tr][p].l+1)*val;
        return ;
    }
    pushdown(tr,p);
    int mid=(t[tr][p].l+t[tr][p].r)>>1;
    if(l<=mid) modify(tr,p<<1,l,r,val);
    if(mid<r) modify(tr,p<<1|1,l,r,val);
    pushup(tr,p);
}
int query(int tr,int p,int l,int r) {
    if(l<=t[tr][p].l&&t[tr][p].r<=r) return t[tr][p].sum;
    pushdown(tr,p);
    int mid=(t[tr][p].l+t[tr][p].r)>>1,ans=0;
    if(l<=mid) ans+=query(tr,p<<1,l,r);
    if(mid<r) ans+=query(tr,p<<1|1,l,r);
    return ans;
}
int main() {
    #ifdef ONLINE_JUDGE
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    #endif
    scanf("%d%d%s",&n,&m,s+1);
    rep(i,0,25) build(i,1,1,n);
    rep(i,1,m) {
        int l,r;
        scanf("%d%d",&l,&r);
        int tim[26],odd=0;
        int nedod=-1;
        rep(j,0,25) tim[j]=query(j,1,l,r);
        rep(j,0,25) if(tim[j]&1) ++odd,nedod=j;
        if(odd>1) continue;
        rep(j,0,25) modify(j,1,l,r,0);
        if(odd) --tim[nedod],modify(nedod,1,(l+r)>>1,(l+r)>>1,1);
        int nl=l,nr=r;
        rep(j,0,25) if(tim[j]) { // 从两边向中间放，一边放一半
            modify(j,1,nl,nl+tim[j]/2-1,1);
            nl+=tim[j]/2;
            modify(j,1,nr-tim[j]/2+1,nr,1);
            nr-=tim[j]/2;
        }
    }
    rep(i,1,n) {
        rep(j,0,25) if(query(j,1,i,i)) {
            printf("%c",j+'a');
        }
    }
    return 0;
}