看到区间推平就想到珂朵莉树。 由于相对暴力，可以实现很多操作。
对于排序操作，观察到值域非常小，所以可以桶排。
代码： 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
using namespace std;
const int N = 5e4;
int n,m;
char a[N + 10];
struct node
{
int l,r;
mutable char val;
inline bool operator<(const node &a) const
{
return l < a.l;
}
};
set<node> tree;
typedef set<node>::iterator IT;
IT split(int x)
{
IT it = tree.lower_bound((node){x,0,0});
if(it != tree.end() && it->l == x)
return it;
--it;
int l = it->l,r = it->r;
char v = it->val;
tree.erase(it);
tree.insert((node){l,x - 1,v});
return tree.insert((node){x,r,v}).first;
}
inline void assign(int l,int r,char val)
{
IT itr = split(r + 1),itl = split(l);
tree.erase(itl,itr);
tree.insert((node){l,r,val});
}
inline void sort_val(int l,int r)
{
IT itr = split(r + 1),itl = split(l);
int buc[30];
memset(buc,0,sizeof buc);
IT it = itl;
for(;itl != itr;++itl)
buc[itl->val - 'A'] += itl->r - itl->l + 1;
tree.erase(it,itr);
for(register int i = 0;i < 26;++i)
if(buc[i])
tree.insert((node){l,l + buc[i] - 1,'A' + i}),l += buc[i];
}
inline int count_val(int l,int r,char val)
{
IT itr = split(r + 1),itl = split(l);
int ret = 0;
for(;itl != itr;++itl)
if(itl->val == val)
ret += itl->r - itl->l + 1;
return ret;
}
int main()
{
scanf("%d%d",&n,&m);
scanf("%s",a + 1);
char last = toupper(a[1]);
int cnt = 1;
for(register int i = 2;i <= n;++i)
if(toupper(a[i]) == last)
++cnt;
else
{
tree.insert((node){i - cnt,i - 1,last});
last = toupper(a[i]);
cnt = 1;
}
tree.insert((node){n - cnt + 1,n,last});
int op,l,r;
char x;
while(m--)
{
scanf("%d%d%d",&op,&l,&r);
if(op == 1)
{
scanf(" %c",&x);
printf("%d\n",count_val(l,r,toupper(x)));
}
else if(op == 2)
{
scanf(" %c",&x);
assign(l,r,toupper(x));
}
else
sort_val(l,r);
}
}