题解 P2787 【语文1（chin1）- 理理思维】
kradcigam
2020-04-05 20:40:40
[题面](https://www.luogu.com.cn/problem/P2787)
这道题我的做法是线段树，由于只有26个字母，所有我们可以建 $26$ 个线段树。
对于操作 `1`
> 我们维护一下区间和就可以了。
对于操作 `2`
> 我们用 $lazy\_tag$ 就可以了
对于操作 `3`
> 我们发现就是操作 `1` 和操作 `2` 的结合
值得一提的是，有一个剪枝优化能是程序快很多
```cpp
int query(int num,int l,int r){
if(t[num].sum==0)return 0;//剪枝
if(t[num].l>=l&&t[num].r<=r)return t[num].sum;
pushdown(num);
if(t[ls].r<l)return query(rs,l,r);
if(t[rs].l>r)return query(ls,l,r);
return query(ls,l,r)+query(rs,l,r);
}
void change(int num,int l,int r,int f){
if(t[num].tag==f)return;//剪枝
if(t[num].l>=l&&t[num].r<=r){
dwn(num,f);
return;
}pushdown(num);
if(t[ls].r>=l)change(ls,l,r,f);
if(t[rs].l<=r)change(rs,l,r,f);
pushup(num);
}
```
这 $2$ 个剪枝虽然非常显然，但可以使程序快很多
代码:
```cpp
#include <bits/stdc++.h>
#define ls num<<1
#define rs num<<1|1
using namespace std;
typedef long long ll;
namespace io {//CYjian的快读模板
const int __SIZE = (1 << 21) + 1;
char ibuf[__SIZE], *iS, *iT, obuf[__SIZE], *oS = obuf, *oT = oS + __SIZE - 1, __c, qu[55]; int __f, qr, _eof;
#define Gc() (iS == iT ? (iT = (iS = ibuf) + fread (ibuf, 1, __SIZE, stdin), (iS == iT ? EOF : *iS ++)) : *iS ++)
inline void flush () { fwrite (obuf, 1, oS - obuf, stdout), oS = obuf; }
inline void gc (char &x) { x = Gc(); }
inline void pc (char x) { *oS ++ = x; if (oS == oT) flush (); }
inline void pstr (const char *s) { int __len = strlen(s); for (__f = 0; __f < __len; ++__f) pc (s[__f]); }
inline void gstr (char *s) { for(__c = Gc(); __c < 32 || __c > 126 || __c == ' ';) __c = Gc();
for(; __c > 31 && __c < 127 && __c != ' '; ++s, __c = Gc()) *s = __c; *s = 0; }
template <class I> inline bool gi (I &x) { _eof = 0;
for (__f = 1, __c = Gc(); (__c < '0' || __c > '9') && !_eof; __c = Gc()) { if (__c == '-') __f = -1; _eof |= __c == EOF; }
for (x = 0; __c <= '9' && __c >= '0' && !_eof; __c = Gc()) x = x * 10 + (__c & 15), _eof |= __c == EOF; x *= __f; return !_eof; }
template <class I> inline void print (I x) { if (!x) pc ('0'); if (x < 0) pc ('-'), x = -x;
while (x) qu[++ qr] = x % 10 + '0', x /= 10; while (qr) pc (qu[qr --]); }
struct Flusher_ {~Flusher_(){flush();}}io_flusher_;
} using io::pc; using io::gc; using io::pstr; using io::gstr; using io::gi; using io::print;
inline void rech(char &ch){
gc(ch);
for(;!isupper(ch)&&!islower(ch);gc(ch));
}
const int N=1e5+10;
int n,m,F[305];
char a[N];
struct node{
struct Tree{
int l,r,sum,tag,len;
}t[N<<2];
void pushup(int num){
t[num].sum=t[ls].sum+t[rs].sum;
}
void dwn(int num,int f){
t[num].tag=f;
if(t[num].tag==1)t[num].sum=t[num].len;
if(t[num].tag==2)t[num].sum=0;
}
void pushdown(int num){
if(t[num].tag==0)return;
dwn(ls,t[num].tag);
dwn(rs,t[num].tag);
t[num].tag=0;
}
void build(int l,int r,int num,char ch){
t[num].tag=0;
t[num].l=l;t[num].r=r;
t[num].len=r-l+1;
if(l==r){
t[num].sum=a[l]==ch;
return;
}int mid=(l+r)>>1;
build(l,mid,ls,ch);
build(mid+1,r,rs,ch);
pushup(num);
}
int query(int num,int l,int r){
if(t[num].sum==0)return 0;//剪枝
if(t[num].l>=l&&t[num].r<=r)return t[num].sum;
pushdown(num);
if(t[ls].r<l)return query(rs,l,r);
if(t[rs].l>r)return query(ls,l,r);
return query(ls,l,r)+query(rs,l,r);
}
void change(int num,int l,int r,int f){
if(t[num].tag==f)return;//剪枝
if(t[num].l>=l&&t[num].r<=r){
dwn(num,f);
return;
}pushdown(num);
if(t[ls].r>=l)change(ls,l,r,f);
if(t[rs].l<=r)change(rs,l,r,f);
pushup(num);
}
}T[110];
int main(){
gi(n);gi(m);
for(int i=1;i<=n;i++)rech(a[i]),a[i]=toupper(a[i]);
for(char i='A';i<='Z';i++)T[i].build(1,n,1,i);
while(m--){
int f,x,y;char k;
gi(f);gi(x);gi(y);
if(f==1){
rech(k);
k=toupper(k);
print(T[k].query(1,x,y));
pstr("\n");
}
if(f==2){
rech(k);
k=toupper(k);
for(char i='A';i<='Z';i++)
if(i==k)T[i].change(1,x,y,1);
else T[i].change(1,x,y,2);
}
if(f==3){
for(char i='A';i<='Z';i++){
F[i]=T[i].query(1,x,y);
T[i].change(1,x,y,2);
}
for(char i='A';i<='Z';i++)
if(F[i])T[i].change(1,x,x+F[i]-1,1),x+=F[i];
}
}
return 0;
}
```