日记和编辑器
\(n\) 个操作，5类：
- 在某个位置后插入一个字符串。
- 区间删除。
- 区间修改为一个字符串（长度可以不等）。
- 查询一段区间某种字符的出现次数
- 查询一段区间匹配模式串 \(P\) 的次数（\(P\) 固定）
\(1\le n\le 10^5,|s|\le 10^5,\sum|s|\le 10n,|P|\le 20\)。
对于前4个操作，考虑 fhq-treap。
- 按照 \(siz\) 分裂，对于插入串建好树，然后缝合。
- 先分裂出 \(1\sim r\)，再分裂出 \(1\sim l-1,l\sim r\)，直接合并需要的两段。
- 先2后1
- 记录在节点信息中，每个节点的字母26种信息，首先是子树内的，自己再额外增加一个字符。
- 不太懂，考虑将树分裂出来，然后中序遍历转换成序列，然后跑KMP。
可以得到 \(22/25\)。
#include<iostream>
#include<random>
#include<cstring>
using namespace std;
random_device rnd;
mt19937 rd(rnd());
const int N=100010,M=30,K=10*N;
int n,rt,l[K],r[K],sz[K],idx,pri[K],cnt[K][M],cur,ne[M],plen;
char s[K],op[10],v[K],p[M];
void up(int p){
for(int i=0;i<26;++i)cnt[p][i]=cnt[l[p]][i]+cnt[r[p]][i];
cnt[p][v[p]-'a']++;
sz[p]=sz[l[p]]+sz[r[p]]+1;
}
void split(int p,int &x,int &y,int k){
if(!p){
x=y=0;
return;
}
if(sz[l[p]]+1<=k){
x=p;
split(r[p],r[p],y,k-sz[l[p]]-1);
}
else{
y=p;
split(l[p],x,l[p],k);
}
up(p);
}
int merge(int x,int y){
if(!x|!y)return x|y;
if(pri[x]>=pri[y]){
r[x]=merge(r[x],y);
up(x);
return x;
}
else{
l[y]=merge(x,l[y]);
up(y);
return y;
}
}
int node(int k){
v[++idx]=k;
sz[idx]=1;
pri[idx]=rd();
cnt[idx][k-'a']++;
return idx;
}
int build(int L,int R){
if(L>R)return 0;
// cout<<L<<' '<<R<<' '<<s[L+R>>1]<<"\n";
if(L==R)return node(s[L]);
int mid=L+R>>1,now=node(s[mid]);
l[now]=build(L,mid-1);
r[now]=build(mid+1,R);
up(now);
// printf("sz[%d]=%d,cnta=%d,cntb=%d\n",now,sz[now],cnt[now][0],cnt[now][1]);
return now;
}
void ins(int p){
int x,y,len=strlen(s+1);
split(rt,x,y,p);
int z=build(1,len);
// printf("z=%d,x=%d,y=%d\n",z,x,y);
rt=merge(merge(x,z),y);
}
struct sy{
int x,y,z;
};
sy sp(int l,int r){
int x,y;
split(rt,x,y,r);
int z;
split(x,x,z,l-1);
// cout<<x<<' '<<y<<' '<<z<<'\n';
return {x,y,z};
}
void del(int l,int r){
sy sys=sp(l,r);
rt=merge(sys.x,sys.y);
}
void me(sy A){
rt=merge(merge(A.x,A.z),A.y);
}
void expand(int p){
if(l[p])expand(l[p]);
s[++cur]=v[p];
if(r[p])expand(r[p]);
}
void print(int p){
// if(l[p])print(l[p]);
// // up(p);
// printf("#%d:sz=%d,v=%c\n",p,sz[p],v[p]);
// for(int i=0;i<26;++i)
// if(cnt[p][i])printf("letter %c:%d\n",i+'a',cnt[p][i]);
// puts("\n");
// if(r[p])print(r[p]);
}
void init(){
plen=strlen(p+1);
for(int i=2,j=0;i<=plen;++i){
while(j&&p[j+1]!=p[i])j=ne[j];
if(p[j+1]==p[i])++j;
ne[i]=j;
// printf("ne[%d]=%d\n",i,j);
}
}
void KMP(){
// cout<<"plen="<<plen<<'\n';
int ans=0;
for(int i=1,j=0;i<=cur;++i){
while(j&&p[j+1]!=s[i])j=ne[j];
if(p[j+1]==s[i]){
++j;
// cout<<"up to "<<j<<'\n';
if(j==plen)++ans,j=ne[j];
}
}
cout<<ans<<'\n';
}
int main(){
#ifndef ONLINE_JUDGE
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
#endif
cin>>n>>p+1;
init();
while(n--){
cin>>op;
int l,r,p;
if(*op=='I'){
cin>>p>>s+1;
ins(p);
print(rt);
}
else if(*op=='D'){
cin>>l>>r;
del(l,r);
}
else if(*op=='R'){
cin>>l>>r>>s+1;
del(l,r);
ins(l-1);
}
else if(*op=='C'){
cin>>l>>r>>s+1;
sy syn=sp(l,r);
cout<<cnt[syn.z][s[1]-'a']<<'\n';
me(syn);
print(rt);
}
else{
cin>>l>>r;
cur=0;
sy syn=sp(l,r);
expand(syn.z);
s[cur+1]=0;
// cout<<s+1<<'&'<<::p+1<<'\n';
KMP();
me(syn);
}
}
return 0;
}