记录编号	571716	评测结果	AAAAAAAAAA
题目名称	[SYOI 2022 R2]苍空下的乐章	最终得分	100
用户昵称	梦那边的美好ET	是否通过	通过
代码语言	C++	运行时间	3.606 s
提交时间	2022-06-15 21:33:09	内存使用	6.31 MiB

#include<bits/stdc++.h>
#define IT set<node>::iterator
#define maxn 100010
using namespace std;
struct node{
    int l,r;
    mutable int v;
    node (int l,int r=-1,int v=0):l(l),r(r),v(v) {}
    bool operator <(const node &rhs) const{
        return l<rhs.l;
    }
};
set<node>s;
IT split(int k){
    IT it=s.lower_bound(node(k));
    if(it!=s.end()&&it->l==k)return it;
    --it;
    int l=it->l,r=it->r;
    int v=it->v;
    s.erase(it);
    s.insert(node(l,k-1,v));
    return s.insert(node(k,r,v)).first;
}
void solve1(int _l,int _r,int v){
    IT r=split(_r+1),l=split(_l);
    s.erase(l,r);
    s.insert(node(_l,_r,v));
    return;
}
void solve2(int _l,int _r){
    IT r=split(_r+1),l=split(_l);
    int mp[30],L=_l;memset(mp,0,sizeof(mp));
    for(;l!=r;l++)mp[l->v]+=((l->r)-(l->l)+1);
    l=split(_l);s.erase(l,r);
    for(int i=1;i<=26;i++){
    	if(mp[i])s.insert(node(L,L+mp[i]-1,i));
    	L+=mp[i];
	}
    return;
}
void solve3(int _l,int _r){
	IT r=split(_r+1),l=split(_l);
	for(;l!=r;l++)
		for(int j=(l->l);j<=(l->r);j++)
		    printf("%c",((l->v)+'a'-1));
	printf("\n");
	return;
}
int n,m;
char S[maxn],a1[10];
int main(){
	freopen("Carillon.in","r",stdin);
	freopen("Carillon.out","w",stdout);
    scanf("%d%d",&n,&m);scanf("%s",S+1);
    for(int i=1;i<=n;i++)s.insert(node(i,i,S[i]-'a'+1));
    s.insert(node(n+1,n+1,0));
    for(int i=1;i<=m;i++){
        int op,l,r;
        scanf("%d%d%d",&op,&l,&r);
        if(op==1)scanf("%s",a1),solve1(l,r,a1[0]-'a'+1);
        else solve2(l,r);
    }
    solve3(1,n);
    return 0;
}