脚本宝典收集整理的这篇文章主要介绍了CF240F 题解，脚本宝典觉得挺不错的，现在分享给大家，也给大家做个参考。

数据范围 (10^5) ，显然可以使用分块。

显然构成回文串的字符串必须要满足每种字符都要出现偶数次或者只有一种字符出现奇数次。

如果能构成回文串，最优方案就是从外到内以 (ato z) 的顺序插入，如果有出现次数为奇数的字符，那么把它填在中间。

所以实际上我们只要维护两个操作：

• 区间赋值
• 查询区间内每种字母出现次数

于是使用分块，开一个桶维护一个块内字母出现次数，区间赋值就把 (mathtt{tag}) 打上去，边角暴力修改。

查询的时候把 (mathtt{tag}) 给 (mathtt{pushdown}) 下传即可。

常数较小，比线段树不知道小到那里去了。

#include <bits/stdc++.h>
namespace mystd {
    inline int read() {
        int w = 1, q = 0;
        char ch = ' ';
        while (ch != '-' && (ch < '0' || ch > '9')) ch = getchar();
        if (ch == '-') w = -1, ch = getchar();
        while (ch >= '0' && ch <= '9') q = q * 10 + ch - '0', ch = getchar();
        return w * q;
    }
    inline void write(int ls) {
        if (ls < 0) {
            ls = ~(ls - 1);
            putchar('-');
        }
        if (ls > 9) write(ls / 10);
        putchar(ls % 10 + '0');
    }
}
using namespace std;
using namespace mystd;

const int maxb = 440;
const int maxn = 1e5 + 100;

char ch[maxn];
int l[maxb], r[maxb], pos[maxn], tag[maxb], c[maxb][26];
int n, m, b, s[maxn], g[26];

void pushdown(int ls) {// 下传标记
    if (tag[ls] < 0) return;
    for (int i = l[ls]; i <= r[ls]; i++) s[i] = tag[ls];
    for (int i = 0; i < 26; i++) c[ls][i] = 0;
    c[ls][tag[ls]] = r[ls] - l[ls] + 1, tag[ls] = -1;
}

void update(int ls, int rs, int k) {// 更新
    if (ls > rs) return;
    int p = pos[ls], q = pos[rs];
    if (p == q) {
        pushdown(p);
        for (int i = ls; i <= rs; i++) c[p][s[i]]--, c[p][k]++, s[i] = k;
    } else {
        pushdown(p);
        pushdown(q);
        for (int i = ls; i <= r[p]; i++) c[p][s[i]]--, c[p][k]++, s[i] = k;
        for (int i = l[q]; i <= rs; i++) c[q][s[i]]--, c[q][k]++, s[i] = k;
        for (int i = p + 1; i <= q - 1; i++) tag[i] = k; 
    }
}

void work(int ls, int rs) { 
    if (ls > rs) return;
    int p = pos[ls], q = pos[rs];
    if (p == q) {
        pushdown(p);
        for (int i = ls; i <= rs; i++) g[s[i]]++;
    } else {
        pushdown(p);
        pushdown(q);
        for (int i = ls; i <= r[p]; i++) g[s[i]]++;
        for (int i = l[q]; i <= rs; i++) g[s[i]]++;
        for (int i = p + 1; i < q; i++) {
            if (tag[i] >= 0) g[tag[i]] += r[i] - l[i] + 1;
            else for (int j = 0; j < 26; j++) g[j] += c[i][j];
        }
    }
    
}

int main() {
    freopen("input.txt", "r", stdin); 
    freopen("output.txt", "w", stdout);
    n = read();
    m = read();
    scanf("%s", ch + 1);
    for (int i = 1; i <= n; i++) s[i] = ch[i] - 'a';
    b = sqrt(n);
    int cnt = 0;
    for (int i = 1; i <= n; i++) pos[i] = (i - 1) / b + 1, c[pos[i]][s[i]]++;
    for (int i = 1; i <= n; i += b) l[++cnt] = i, r[cnt] = min(i + b - 1, n), tag[cnt] = -1;
    for (int i = 1, p, q, fl = 0, id = -1; i <= m; i++, fl = 0, id = -1) {
        p = read();
        q = read();
        work(p, q);
        for (int i = 0; i < 26; i++) if (g[i] & 1) id = i, fl++;
        if (fl > 1) {
            memset(g, 0, sizeof(g));
            continue;
        }
        int t1 = p, t2 = q;
        for (int i = 0; i < 26; i++) {
            update(t1, t1 + g[i] / 2 - 1, i), t1 += g[i] / 2;
            update(t2 - g[i] / 2 + 1, t2, i), t2 -= g[i] / 2;
            g[i] = 0;
        }
        if (id >= 0) update(t1, t1, id);
    }
    for (int i = 1; i <= b; i++) pushdown(i);
    for (int i = 1; i <= n; i++) putchar(s[i] + 'a');
    return 0;
}

脚本宝典总结

以上是脚本宝典为你收集整理的CF240F 题解全部内容，希望文章能够帮你解决CF240F 题解所遇到的问题。

如果觉得脚本宝典网站内容还不错，欢迎将脚本宝典推荐好友。

本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。