题解 P2787 【语文1（chin1）- 理理思维】
做法：分块
对于查询和修改1都是分块的基本操作，这里不再赘述。
关键是修改2令人很头疼，看起来好像只能暴力排序，这样时间复杂度会是O(mnlogn)，铁定炸。
接着我们可以发现修改2的操作可以拆成查询和修改1来完成：
把排序拆成统计区间内每个字母的个数，然后再在区间内从A到Z依次填入相应数量的字母即可。
每次修改2的时间复杂度O(√n)
其余和普通的分块一样，总时间复杂度O(n√n)。
(另:注意将字母全转为大写或全转为小写）
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#include<cstdlib>
#include<cctype>
#include<cmath>
#include<stack>
#define mem(a) memset(a, 0, sizeof(a))
using namespace std;
typedef long long LL;
typedef int T;
const int M = 1000000009;
const int N = 100009;
int n, m, num;
int head[409], tail[409], pos[N];
int ct[309][30];
char s1[N], lazy[409];
T _read();
void init();
void solve();
int idx(char);
int query(int, int, char);
void maintain(int);
void change_1(int, int, char);
void change_2(int, int);
int main() {
init();
solve();
return 0;
}
void init() {
n = _read();
m = _read();
int szq = (int) sqrt(n);
scanf("%s", s1 + 1);
int cnt = 0;
for(int i = 1; i <= n; i++) {
s1[i] = toupper(s1[i]); //这里一定要注意! 字母全转化为大写!
cnt++;
if(cnt == 1) {
head[++num] = i;
}
pos[i] = num;
if(cnt == szq || i == n) {
tail[num] = i;
lazy[num] = '#';
cnt = 0;
}
}
for(int i = 1; i <= n; i++) {
int c = idx(s1[i]);
ct[pos[i]][c]++;
}
}
void solve() {
for(int i = 1; i <= m; i++) {
int q = _read();
if(q == 1) {
int a = _read(), b = _read();
if(a > b) swap(a, b);
char c[10];
scanf("%s", c);
c[0] = toupper(c[0]);
printf("%d\n", query(a, b, c[0]));
}
else if(q == 2) {
int a = _read(), b = _read();
if(a > b) swap(a, b);
char c[10];
scanf("%s", c);
c[0] = toupper(c[0]);
change_1(a, b, c[0]);
}
else {
int a = _read(), b = _read();
if(a > b) swap(a, b);
change_2(a, b);
}
}
}
int idx(char c) {
return c - 'A';
}
int query(int l, int r, char s) { //询问
int posl = pos[l], posr = pos[r];
int c = idx(s);
int ans = 0;
if(posl == posr) {
maintain(posl);
for(int i = l; i <= r; i++)
if(s1[i] == s) ans++;
return ans;
}
maintain(posl);
for(int i = l; i <= tail[posl]; i++)
if(s1[i] == s) ans++;
for(int i = posl + 1; i <= posr - 1; i++)
ans += ct[i][c];
maintain(posr);
for(int i = head[posr]; i <= r; i++)
if(s1[i] == s) ans++;
return ans;
}
void change_1(int l, int r, char s) { //修改1
if(l > r) return;
int posl = pos[l], posr = pos[r];
int c = idx(s);
if(posl == posr) {
maintain(posl);
for(int i = l; i <= r; i++) {
int c1 = idx(s1[i]);
ct[posl][c1]--;
ct[posl][c]++;
s1[i] = s;
}
return;
}
maintain(posl);
for(int i = l; i <= tail[posl]; i++) {
int c1 = idx(s1[i]);
ct[posl][c1]--;
ct[posl][c]++;
s1[i] = s;
}
for(int i = posl + 1; i <= posr - 1; i++) {
lazy[i] = s;
for(int j = 0; j <= 26; j++)
ct[i][j] = 0;
ct[i][c] = tail[i] - head[i] + 1;
}
maintain(posr);
for(int i = head[posr]; i <= r; i++) {
int c1 = idx(s1[i]);
ct[posr][c1]--;
ct[posr][c]++;
s1[i] = s;
}
}
void change_2(int l, int r) { //修改2
int zct[26];
for(int i = 0; i <= 26; i++) { //查询各种字母数量
zct[i] = query(l, r, (char) ('A' + i));
}
int now = l;
for(int i = 0; i <= 26; i++) { //根据字母数量依次填充
change_1(now, now + zct[i] - 1, (char) ('A' + i));
now += zct[i];
}
}
void maintain(int posx) {
if(lazy[posx] == '#') return;
int l = head[posx], r = tail[posx];
for(int i = l; i <= r; i++)
s1[i] = lazy[posx];
lazy[posx] = '#';
}
T _read() {
T a = 0, f = 1;
char c = getchar();
while(c < '0' || c > '9') {
if(c == '-')
f *= -1;
c = getchar();
}
while(c <= '9' && c >= '0') {
a *= 10;
a += c - '0';
c = getchar();
}
return a * f;
}