比赛 |
SYOI2022 Round2 |
评测结果 |
AAAAAAAAAA |
题目名称 |
苍空下的乐章 |
最终得分 |
100 |
用户昵称 |
yrtiop |
运行时间 |
0.983 s |
代码语言 |
C++ |
内存使用 |
6.44 MiB |
提交时间 |
2022-06-15 20:01:47 |
显示代码纯文本
#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;
}