记录编号	571739	评测结果	AAAAAAAAAA
题目名称	[SYOI 2022 R2]苍空下的乐章	最终得分	100
用户昵称	yrtiop	是否通过	通过
代码语言	C++	运行时间	3.583 s
提交时间	2022-06-17 13:00:23	内存使用	6.36 MiB

#include <bits/stdc++.h>
#define SIT set<node>::iterator
#define pb emplace_back
using namespace std;
const int maxn = 1e5 + 5;
struct node {
    int l,r;
    mutable int v;
    node() {
        l = r = v;
    }
    node(int l,int r = 0,int v = 0):l(l),r(r),v(v){}
    bool operator < (const node& p)const {
        return l < p.l;
    }
};
set<node> s;
char t[maxn];
int n,Q;
SIT split(int pos) {
    SIT it = s.lower_bound(node(pos));
    if(it != s.end()&&it -> l == pos)return it;
    -- it;
    if(it -> r < pos)return s.end();
    int l = it -> l;
    int r = it -> r;
    int v = it -> v;
    s.erase(it);
    s.insert(node(l , pos - 1 , v));
    return s.insert(node(pos , r , v)).first;
}
void assign(int l,int r,int k) {
    SIT itr = split(r + 1),itl = split(l);
    s.erase(itl , itr);
    s.insert(node(l , r , k));
    return ;
}
void Sort(int l,int r) {
    int cnt[26] = {0};
    SIT itr = split(r + 1),itl = split(l);
    for(SIT it = itl;it != itr;++ it) {
        cnt[it -> v] += it -> r - it -> l + 1;
    }
    s.erase(itl , itr);
    int cur = l;
    for(int i = 0;i < 26;++ i)
        if(cnt[i])s.insert(node(cur , cur + cnt[i] - 1 , i)),cur += cnt[i];
    return ;
} 
int main() {
    freopen("Carillon.in","r",stdin);
    freopen("Carillon.out","w",stdout);
    scanf("%d%d%s",&n,&Q,t + 1);
    for(int i = 1;i <= n;++ i)s.insert(node(i , i , t[i] - 'a'));
    while(Q --) {
        int op,l,r;
        char c;
        scanf("%d%d%d",&op,&l,&r);
        if(op & 1) {
            scanf(" %c",&c);
            assign(l , r , c - 'a');
        }
        else {
            Sort(l , r);
        }
    }
    for(auto k : s) 
        for(int i = 1;i + k.l <= k.r + 1;++ i)printf("%c",k.v + 'a');
    return 0;
}