这题的关键思路点:
把n个串插入到字典树上后，对于一个串t，与其前缀k个相同的在字典树的字符串为： 从根节点沿着t走k步后到达的节点tk，其子树节点满足这个条件。
然后自然而然就能想到字典树上dfs序建立主席树，求l-r字符串中，符合条件的字符串个数。(主席树的经典操作了，求[l，r]范围内值为x-y,的数的个数。)
即建立n棵树，每棵树i，的位置j，维护的是：1-i字符串中，dfs序为j的字符串的个数。
由于要支持修改操作，我们可以用树状数组套权值线段树：
具体操作见代码:
(写了个空间回收机制，当内存不够用时可以加上!!!)
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define re register #define pb push_back typedef pair<int,int> pii; const double PI= acos(-1.0); const int M = 4e5+7; char s[M]; int ti[M][26],CNT=1; vector<int> mp[M];//当前字典树节点，是哪些字符串结尾节点 int id[M]; void in(char *s,int tp){//插入到字典树中 int n=strlen(s),p=1; for(int i=0;i<n;i++){ int ch=s[i]-'a'; if(!ti[p][ch])ti[p][ch]=++CNT; p=ti[p][ch]; } mp[p].pb(tp);//以当前节点结尾的字符串的 } int st[M],ed[M],sz; void dfs(int x){ st[x]=++sz; int l=mp[x].size(); // cout<<x<<" - - "<<l<<" "<<CNT<<endl; if(l){ id[mp[x][0]]=sz; for(int i=1;i<l;i++)id[mp[x][i]]=++sz; } for(int i=0;i<26;i++){ //cout<<x<<" "<<ti[x][i]<<endl; if(ti[x][i])dfs(ti[x][i]); } ed[x]=sz; } int rt[M],tr[M*50],ls[M*50],rs[M*50],cnt,n; /* vector<int>rb;//垃圾桶 void gb(int o){ tr[o]=0;//把节点丢掉的同时也要把节点里的值给清空 rb.pb(o); if(ls[o])gb(ls[o]),ls[o]=0; if(rs[o])gb(rs[o]),rs[o]=0; }*/ void up(int &o,int l,int r,int w,int op){ if(!o)o=++cnt; tr[o]+=op; //垃圾回收机制，当卡空间，而不卡时间时可以加上下面的操作 /*if(!o){ if(rb.size())o=rb[rb.size()-1],rb.pop_back(); else o=++cnt; } tr[o]+=op; if(tr[o]==0){//当前节点所维护的区间值为0，即"无用"可以当垃圾扔掉 gb(o);o=0; return ;///后面就不用操作了，反正区间和都是0 }*/ if(l==r)return; int m=(l+r)/2; if(w<=m)up(ls[o],l,m,w,op); else up(rs[o],m+1,r,w,op); }// void ADD(int pos,int w,int op){ for(int i=pos;i<=n;i+=(i&-i))//第一维树状数组对应的是n个位置 up(rt[i],1,sz,w,op); } int qu(int o,int l,int r,int x,int y){ if(!o||tr[o]==0) return 0; if(x<=l&&r<=y) return tr[o]; int m=(l+r)>>1,res=0; if(x<=m) res+=qu(ls[o],l,m,x,y); if(y>m) res+=qu(rs[o],m+1,r,x,y); return res; } int QU(int l,int r,int x,int y){ int ans=0; for(int i=r;i;i-=(i&-i))ans+=qu(rt[i],1,sz,x,y); for(int i=l-1;i;i-=(i&-i))ans-=qu(rt[i],1,sz,x,y); return ans; } int main() { ios::sync_with_stdio(false); cin.tie(0); int q; cin>>n>>q; for(int i=1;i<=n;i++){ cin>>s; in(s,i); } dfs(1); for(int i=1;i<=n;i++)//单点加 ADD(i,id[i],1); //cout<<i<<" "<<id[i]<<endl;; while(q--){ int opt,k,l,r; cin>>opt; if(opt==1){ cin>>l>>r;//交换i，j字符串 ADD(l,id[l],-1);ADD(r,id[r],-1); ADD(l,id[r],1);ADD(r,id[l],1); swap(id[l],id[r]); } else{ cin>>s; cin>>k>>l>>r;//查询id 为l,r字符串中与 s的公共前缀至少为k的个数 int p=1; for(int i=0;i<k;i++) p=ti[p][s[i]-'a']; if(p==0) cout<<0<<endl; else{ int ans=QU(l,r,st[p],ed[p]); cout<<ans<<endl; } } } return 0; }
