```cpp
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
const int M=700+10;
inline int _abs(int x){if(x>0) return x;return -x;}
int tr[N][26];
int fail[N],cnt;
int pos[N],lst[N];
struct node{
int to,nxt;
}edge[N*2]; int head[N]; int _cnt;
void adde(int u,int v){
edge[++_cnt].to=v;
edge[_cnt].nxt=head[u];
head[u]=_cnt;
}
int siz[N],id[N],res;
void dfs(int u,int f){
id[u]=++res; siz[u]=1;
for(int i=head[u];i;i=edge[i].nxt){
int v=edge[i].to; if(v==f) continue;
dfs(v,u); siz[u]+=siz[v];
}
}
void insert(const string &s,int rt,int x){
int u=rt;
for(int i=0;i<s.size();i++){
int v=s[i]-'a';
if(!tr[u][v]) tr[u][v]=++cnt;
u=tr[u][v];
}
pos[u]++; lst[x]=u;
}
void build(int rt){
for(int i=0;i<26;i++) tr[0][i]=rt;
queue<int>q; q.push(rt);
while(!q.empty()){
int u=q.front(); q.pop();
for(int i=0;i<26;i++){
if(tr[u][i]){
fail[tr[u][i]]=tr[fail[u]][i];
q.push(tr[u][i]);
}else tr[u][i]=tr[fail[u]][i];
}
}
}
int nxt[N];
long long bf(const string &s,const string &t){
int n=s.size();
int m=t.size();
long long ans=0;
nxt[1]=0;
for(int i=2,p=0;i<=n;i++){
while(p>0&&s[i-1]!=s[p]) p=nxt[p];
if(s[i-1]==s[p]) p++;
nxt[i]=p;
}
for(int i=1,p=0;i<=m;i++){
while(p>0&&(p==n||t[i-1]!=s[p])) p=nxt[p];
if(t[i-1]==s[p]) p++;
if(p==n) ans++;
}
return ans;
}
struct BIT{
long long tr[N];
int lowbit(int x){
return x&(-x);
}
void modify(int pos,int val){
while(pos<N){
tr[pos]+=val;
pos+=lowbit(pos);
}
}
long long q(int pos){
long long ans=0;
while(pos){
ans+=tr[pos];
pos-=lowbit(pos);
}
return ans;
}
long long query(int l,int r){
return q(r)-q(l-1);
}
}bit,tme;
string s[N];
int a[N];
struct fenkuaier{
int pos[N],st[M],ed[M],rt[M];
long long tag[M],add[M];
int n,sz=N/M;
void init(){
for(int i=1;i<=n;i++) pos[i]=(i-1)/sz+1;
for(int i=1;i<=pos[n];i++) st[i]=(i-1)*sz+1,ed[i]=i*sz,tag[i]=add[i]=0;
ed[pos[n]]=n;
for(int i=1;i<=pos[n];i++){
rt[i]=++cnt;
for(int j=st[i];j<=ed[i];j++){
insert(s[j],rt[i],j);
}
build(rt[i]);
}
for(int i=2;i<=cnt;i++) adde(fail[i],i);
for(int i=1;i<=pos[n];i++) dfs(rt[i],0);
for(int i=1;i<=n;i++){
bit.modify(id[lst[i]],a[i]);
bit.modify(id[lst[i]]+siz[lst[i]],-a[i]);
}
for(int i=1;i<=n;i++){
tme.modify(id[lst[i]],1);
tme.modify(id[lst[i]]+siz[lst[i]],-1);
}
}
void pushtag(int b){
if(tag[b]){
for(int i=st[b];i<=ed[b];i++){
bit.modify(id[lst[i]],tag[b]-a[i]);
bit.modify(id[lst[i]]+siz[lst[i]],-tag[b]+a[i]);
a[i]=tag[b];
}
tag[b]=0;
}else if(add[b]){
for(int i=st[b];i<=ed[b];i++){
bit.modify(id[lst[i]],add[b]);
bit.modify(id[lst[i]]+siz[lst[i]],-add[b]);
a[i]+=add[b];
}
add[b]=0;
}
}
void modify1(int l,int r,int val){//add
int bl=pos[l],br=pos[r];
if(bl==br){
pushtag(bl);
for(int i=l;i<=r;i++){
a[i]+=val;
bit.modify(id[lst[i]],val);
bit.modify(id[lst[i]]+siz[lst[i]],-val);
}
return;
}
pushtag(bl); pushtag(br);
for(int i=l;i<=ed[bl];i++){
a[i]+=val;
bit.modify(id[lst[i]],val);
bit.modify(id[lst[i]]+siz[lst[i]],-val);
}
for(int i=st[br];i<=r;i++){
a[i]+=val;
bit.modify(id[lst[i]],val);
bit.modify(id[lst[i]]+siz[lst[i]],-val);
}
for(int i=bl+1;i<br;i++){
if(tag[i]){
tag[i]+=val;
}else{
add[i]+=val;
}
}
}
void modify2(int l,int r,int val){//push
int bl=pos[l],br=pos[r];
if(bl==br){
pushtag(bl);
for(int i=l;i<=r;i++){
bit.modify(id[lst[i]],val-a[i]);
bit.modify(id[lst[i]]+siz[lst[i]],-val+a[i]);
a[i]=val;
}
return;
}
pushtag(bl); pushtag(br);
for(int i=l;i<=ed[bl];i++){
bit.modify(id[lst[i]],val-a[i]);
bit.modify(id[lst[i]]+siz[lst[i]],-val+a[i]);
a[i]=val;
}
for(int i=st[br];i<=r;i++){
bit.modify(id[lst[i]],val-a[i]);
bit.modify(id[lst[i]]+siz[lst[i]],-val+a[i]);
a[i]=val;
}
for(int i=bl+1;i<br;i++){
tag[i]=val; add[i]=0;
}
}
long long query(int l,int r,const string &k){
int bl=pos[l],br=pos[r];
if(bl==br){
long long ans=0;
for(int i=l;i<=r;i++){
int t=bf(s[i],k);
if(tag[bl]) ans+=t*tag[bl];
else ans+=t*(a[i]+add[bl]);
}
return ans;
}
long long ans=0;
for(int i=l;i<=ed[bl];i++){
int t=bf(s[i],k);
if(tag[bl]) ans+=t*tag[bl];
else ans+=t*(a[i]+add[bl]);
}
for(int i=st[br];i<=r;i++){
int t=bf(s[i],k);
if(tag[br]) ans+=t*tag[br];
else ans+=t*(a[i]+add[br]);
}
for(int i=bl+1;i<br;i++){
int u=rt[i]; long long t1=0,t2=0;
for(int j=0;j<k.size();j++){
int v=k[j]-'a';
u=tr[u][v]; //cout<<u<<"\n";
if(!tag[i]) t1+=bit.q(id[u]);
t2+=tme.q(id[u]);
}
//cout<<"Q "<<i<<" "<<t1<<" "<<t2<<"\n";
if(tag[i]){
ans+=tag[i]*t2;
}else{
ans+=add[i]*t2+t1;
}
}
return ans;
}
}f;
void fake_main(){
int n,m; cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>s[i]>>a[i];
}
f.n=n; f.init();
//for(int i=1;i<=n;i++) cout<<lst[i]<<" "; cout<<"\n";
//for(int i=1;i<=cnt;i++) cout<<fail[i]<<" "; cout<<"\n";
for(int i=1;i<=m;i++){
int op; cin>>op;
if(op==1){
int l,r,k; cin>>l>>r>>k;
f.modify1(l,r,k);
}else if(op==2){
int l,r,k; cin>>l>>r>>k;
f.modify2(l,r,k);
}else{
int l,r; string k; cin>>l>>r>>k;
cout<<f.query(l,r,k)<<"\n";
}
}
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int t; t=1;
while(t--) fake_main();
}
```
by Drind @ 2024-04-19 11:34:10
过了，散块暴力做的时候，要判断一下模式串和匹配串哪个更长，不然复杂度会假。
by Drind @ 2024-04-19 12:11:49
咋让你过了？
by TernaryTree @ 2024-04-19 12:56:00
@[TernaryTree](/user/362750) 实力，哈哈
by Drind @ 2024-04-19 21:40:15
@[Drind](/user/305854) 拜谢
by TernaryTree @ 2024-04-19 21:44:23