12.CF558E A Simple Task 线段树维护字符串区间排序

12.CF558E A Simple Task 线段树维护字符串区间排序

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

要求对于给定的字符串，对给定的区间进行排序

线段树经典应用，维护26棵线段树，实现区间覆盖和查询即可。

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

CF传送门：E. A Simple Task (codeforces.com)

题目分析

要求对于给定的字符串，对给定的区间进行排序。

我们维护 26 26 26棵线段树，每颗线段树上记录对应字母所在的位置(叶节点 0 − 1 0-1 0−1表示有没有，然后维护区间和表示区间字母个数)。对于区间排序，我们只需要取出区间在 26 26 26棵线段树上的信息，然后按照升序或降序覆盖即可。

因为要维护区间覆盖，因此也需要打 L a z y Lazy Lazy标记。

Code

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

const int N = 2e2 + 10, MOD = 1e9 + 7;

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);
    }
}


inline void solve(){
    int n, q; cin >> n >> q;
    cin >> s, s = '@' + s;
    for(int i = 0; i > l >> r >> k;
        vector cnt;
        for(int i = 0; i