F. Paper Grading
题意：
有 2 e 5 2e5 2e5个字符串和 2 e 5 2e5 2e5个操作；
第一种操作是 交换两个字符串；
第二种是 给你 l , r , k l,r,k l,r,k 和一个字符串 s s s ，询问 区间 l 到 r l到r l到r 中有多少个字符串的前 k k k个字符 和 s s s的前 k k k个字符相同。
思路：
先将所有字符串建成一颗 t r i e trie trie树，在字符串的结尾位置打个标记。
然后 询问下标 l 到 r l到r l到r之间有多少个字符串 和 s s s的前 k k k 个字符相同，就转换成了 询问 t r i e trie trie树的一颗子树中 有多少个结束点 在 l 到 r l到r l到r之间，询问一颗子树 可以用 d f s dfs dfs序 转换成询问区间的问题：那么操作二就转换成了经典的 求 L 到 R L到R L到R 中 l 到 r l到r l到r 的和。还有操作一的修改操作，可以用树套树实现，就 O K OK OK 啦~
当然当然CDQ分治肯定也是没问题的啦~
o p s : ops: ops:数据结构没学好，每次遇到这种题，都会去想 带修可持久化，后来发现这个东西好像 子虚乌有；一般带修可持久化是用树套树来实现，即树状数组套动态开点线段树，支持的是单点修改。
代码：
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll mod=1e9+7;int n,m;
int trie[200060][26];int tot=1,cnt=0;
int ed[200060],dfn[200050],id[200050];
char s[200050];
struct node{
int ls,rs,num;
}tr[30000050];
int siz[200050],root[200050];void insert(int i){
int now=1;int len=strlen(s);for(int i=0;i<len;i++){
if(trie[now][s[i]-'a']);else {
trie[now][s[i]-'a']=++tot;}now=trie[now][s[i]-'a'];}ed[i]=now;
}void dfs1(int i){
dfn[++cnt]=i;id[i]=cnt;siz[i]=1;for(int j=0;j<26;j++){
if(trie[i][j])dfs1(trie[i][j]),siz[i]+=siz[trie[i][j]];}
}void update(int &rt,int l,int r,int x,int w){
if(!rt)rt=++tot;tr[rt].num+=w;if(l==r)return;int mid=l+r>>1;if(x<=mid)update(tr[rt].ls,l,mid,x,w);else update(tr[rt].rs,mid+1,r,x,w);
}int query(int rt,int l,int r,int x,int y){
if(!rt)return 0;if(x<=l&&r<=y)return tr[rt].num;int mid=l+r>>1,ans=0;if(x<=mid)ans+=query(tr[rt].ls,l,mid,x,y);if(mid<y)ans+=query(tr[rt].rs,mid+1,r,x,y);return ans;
}int lowbit(int x){
return x&(-x);
}void add(int x,int pos,int w){
while(x<=n){
update(root[x],1,cnt,pos,w);x+=lowbit(x);}
}int ask(int x,int l,int r){
int ans=0;while(x){
ans+=query(root[x],1,cnt,l,r);x-=lowbit(x);}return ans;
}int get(int k){
int now=1;for(int i=0;i<k;i++){
if(trie[now][s[i]-'a'])now=trie[now][s[i]-'a'];else return 0;}return now;
}
int main(){
scanf("%d%d",&n,&m);for(int i=1;i<=n;i++){
scanf("%s",s);insert(i);}dfs1(1);tot=0;for(int i=1;i<=n;i++){
add(i,id[ed[i]],1);}while(m--){
int op;scanf("%d",&op);if(op==1){
int a,b;scanf("%d%d",&a,&b);add(a,id[ed[a]],-1);add(a,id[ed[b]],1);add(b,id[ed[a]],1);add(b,id[ed[b]],-1);swap(ed[a],ed[b]);}else{
int a,b,k;scanf("%s%d%d%d",s,&k,&a,&b);k=get(k);if(k==0)printf("0\n");else{
printf("%d\n",ask(b,id[k],id[k]+siz[k]-1)-ask(a-1,id[k],id[k]+siz[k]-1));}}}return 0;
}