1.CF240F TorCoder 线段树区间覆盖(区间排序回文构造)

1.CF240F TorCoder 线段树区间覆盖(区间排序/回文构造)

个人Limitの线段树题单题解主目录：Limitの线段树题单 题解目录_HeartFireY的博客-CSDN博客

给定字符串，对于每次给定的区间，将区间置为最小字典序的回文串，不能操作就不操作。

线段树维护区间覆盖。

洛谷传送门：CF240F TorCoder - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

CF传送门：F. TorCoder (codeforces.com)

题目分析

给定字符串，对于每次给定的区间，将区间置为最小字典序的回文串，不能操作就不操作。

可以构成回文串的条件：至多出现一个奇数个字母；

那么我们就得到了检查合法性的依据：维护 26 26 26棵线段树，对每个区间的字母分开维护，对区间内取出所有字母的出现次数，如果有一个字母不符合要求就直接跳过。

最小字典序的回文串可以通过按字典序构造实现(两端向中间覆盖)。实现区间覆盖和区间查询功能即可

Code

#include 
#pragma gcc optimize("O2")
#pragma g++ optimize("O2")
#define int long long
#define endl '\n'
using namespace std;

const int N = 1e5 + 10;

string s;

char ans[N];

namespace SegTree{
    #define ls rt  1;
        if(mid >= L) update(lson, L, R, val);
        if(mid = L && r > 1, ans = 0;
        if(mid >= L) ans += query(lson, L, R);
        if(mid > 1;
        getans(lson), getans(rson);
    }
}

 // namespace SegTree


void solve(){
    int n, m; cin >> n >> m >> s; s = '@' + s;
    for(int i = 0; i > r;
        vector cnt;
        for(int i = 0; i  1) continue;
        int prel = l, prer = l, sufl = r, sufr = r;
        for(int i = 0; i > 1) - 1;
            sufl = sufr - (cnt[i] >> 1) + 1;
            SegTree::update(1, i, 1, n, l, r, 0);
            SegTree::update(1, i, 1, n, prel, prer, 1);
            SegTree::update(1, i, 1, n, sufl, sufr, 1);
            if(cnt[i] & 1){
                SegTree::update(1, i, 1, n, (l + r >> 1), (l + r >> 1), 1);
            }
            prel = prer + 1, sufr = sufl - 1;
        }
    }
    for(int i = 0; i