1、先不考虑交换问题， 只考虑查询。一般公共前缀问题就往字典树上去想，那么先将所有字符串转化为字典树上的东西，那么公共前缀为k，我们先找到这个点，x，那么发现所有符合条件的都在x的子树下面，那么现在可以把整个树做一个dfs序，就可以快速的表示x的子树范围，那么x的范围设置为dfn[x] , ed[x] ,一个进入dfs序，一个退出dfs序，
2、现在我们就是要在[dfn[x] , ed[x]] 之前查找[L , R ] 的个数，现在这个求解就直接容斥一下(简单的相加减) ， [dfn[x] , r] - [dfn[x] + sz[x] - 1 , r] - ([dfn[x] , l - 1] - [dfn[x] + sz[x] - 1 , l - 1])
3、 那么我们现在就是求解[1 ， dfn[x]] 里面有多少[1 , r]
4、那么发现对于某一个dfn[x]而言，只需要比它小的dfx[y] , 对于某个r来说，只需要比它小的r‘
5、我们可以先把所有的字符串的所有dfn和编号id保存一下，那么可以用二维偏序来求出结果，只要看比dfn[x]小的有多少[1 , r],经典二维偏序问题,排序加树状数组可以解决
6、再考率交换问题，它会交换两个字符串，但是在上面的问题抽像出来之后，只关注dfs序和它的标号，标号肯定是不变的，那么只需要交换标号。但是交换肯定付出代价,因为在第5步，我们插入了所有的字符串，交换的话肯定需要将交换之前的贡献删除，将交换之后的贡献插入。
7、问题出现了，那么我们这个怎么插入，直接插入的话如何保证这个交换只会对后面的查询有影响，而不对前面的查询有影响。我们发现这个是否对前后有影响是因为时间原因，查询和修改的时间关系决定的。那么我们就再引入一维，时间戳t。那么第6步的基础上加一维时间t。经典三维偏序问题。
8、现在就是要求出来，对于某个[t , dfn[x] , r] ，有多少[t‘ , dfn[x]‘ , r‘] , 满足 t‘ <= t && dfn[x]‘ <= dfn[x] , r‘ <= r
/*
*@author spnooyseed
*/
#pragma GCC optimize("Ofast","unroll-loops","omit-frame-pointer","inline")
#pragma GCC optimize(3 , "Ofast" , "inline")
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization("unroll-loops")
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <unordered_map>
#include <vector>
#include <map>
#include <list>
#include <queue>
#include <cstring>
#include <cstdlib>
#include <ctime>
#include <cmath>
#include <stack>
#include <set>
#include <bitset>
#include <deque>
using namespace std ;
#define ios ios::sync_with_stdio(false) , cin.tie(0)
#define x first
#define y second
#define pb push_back
#define ls rt << 1
#define rs rt << 1 | 1
typedef long long ll ;
const double esp = 1e-6 , pi = acos(-1) ;
typedef pair<int , int> PII ;
const int N = 1e6 + 10 , INF = 0x3f3f3f3f , mod = 1e9 + 7;
struct node {
int t , dfn , id , val , ans , op ;
}q[N * 2] , temp[N * 2] ;
int son[N * 2][28] , dfn[N] , cnt , bel[N] , ed[N] ;
bool cmp(node a , node b) {
if(a.t != b.t) return a.t < b.t ;
if(a.dfn != b.dfn) return a.dfn < b.dfn ;
return a.id < b.id ;
}
int lowbit(int x) {
return x & -x ;
}
int c[N] ;
void add(int x , int k) {
while(x < N) c[x] += k , x += lowbit(x) ;
}
int ask(int x) {
int ans = 0 ;
while(x) ans += c[x] , x -= lowbit(x) ;
return ans ;
}
void insert(char s[] , int id) {
int len = strlen(s) ;
int p = 0 ;
for(int i = 0 ;i < len ;i ++ ) {
int u = s[i] - ‘a‘ + 1 ;
if(!son[p][u]) son[p][u] = ++ cnt ;
p = son[p][u] ;
}
bel[id] = p ;
return ;
}
void dfs(int u) {
dfn[u] = ++ cnt ;
for(int i = 1 ; i <= 26; i ++ )
if(son[u][i]) dfs(son[u][i]) ;
ed[u] = cnt ;
}
char s[N] ;
int get(int k) {
int p = 0 ;
for(int i = 0 , j = 1 ; s[i] && j <= k ;i ++ , j ++ ) {
int u = s[i] - ‘a‘ + 1 ;
if(!son[p][u]) return -1 ;
p = son[p][u] ;
}
return p ;
}
ll ans[N] ;
void cdq(int l , int r) {
if(l >= r) return ;
int mid = l + r >> 1 ;
cdq(l , mid) , cdq(mid + 1 , r) ;
int i = l , j = mid + 1 , k = 0 ;
while(i <= mid && j <= r ) {
if(q[i].dfn <= q[j].dfn) {
if(q[i].op) add(q[i].id , q[i].val) ;
temp[++ k] = q[i ++] ;
}
else {
if(!q[j].op) ans[q[j].ans] += ask(q[j].id) * q[j].val ;
temp[++ k] = q[j ++] ;
}
}
while(i <= mid) {
if(q[i].op) add(q[i].id , q[i].val) ;
temp[++ k] = q[i ++] ;
}
while(j <= r) {
if(!q[j].op) ans[q[j].ans] += ask(q[j].id) * q[j].val ;
temp[++ k] = q[j ++] ;
}
for(int i = l ;i <= mid ;i ++ ) if(q[i].op) add(q[i].id , -q[i].val) ;
for(int i = l , j = 1 ;i <= r; i ++ , j ++ ) q[i] = temp[j] ;
return ;
}
int f[N] ;
int main()
{
// freopen("C://Users//spnooyseed//Desktop//in.txt" , "r" , stdin) ;
// freopen("C://Users//spnooyseed//Desktop//out.txt" , "w" , stdout) ;
int n , m ;
scanf("%d%d" , &n , &m) ;
for(int i = 1; i <= n ;i ++ ) {
scanf("%s" , s) ;
insert(s , i) ;
}
cnt = 0 ;
dfs(0) ;
int idx = 0 ;
// t dfn id val ans op
for(int i = 1; i <= n ;i ++ )
q[++ idx] = {0 , dfn[bel[i]] , i + 1 , 1 , 0 , 1} ;
for(int i = 1; i <= m ;i ++ ) {
int op ;
scanf("%d" , &op) ;
if(op == 1) {
int a , b ;
scanf("%d%d" , &a , &b) ;
q[++ idx] = {i , dfn[bel[a]] , a + 1 , -1 , i , 1} ;
q[++ idx] = {i , dfn[bel[b]] , b + 1 , -1 , i , 1} ;
swap(bel[a] , bel[b]) ;
q[++ idx] = {i , dfn[bel[a]] , a + 1 , 1 , i , 1} ;
q[++ idx] = {i , dfn[bel[b]] , b + 1 , 1 , i , 1} ;
}else {
f[i] = 1;
int l , r , k ;
scanf("%s%d%d%d" , s , &k , &l , &r) ;
int x = get(k) ;
q[++ idx] = {i , ed[x] , r + 1 , 1 , i , 0} ;
q[++ idx] = {i , dfn[x] - 1 , r + 1 , -1 , i , 0} ;
q[++ idx] = {i , ed[x] , l , - 1 , i , 0} ;
q[++ idx] = {i , dfn[x] - 1 , l , 1 , i , 0} ;
}
}
sort(q + 1 , q + idx + 1 , cmp) ;
cdq(1 , idx) ;
for(int i = 1; i <= m ;i ++ )
if(f[i])
printf("%lld\n" , ans[i]) ;
return 0 ;
}
/*
*/
原文：https://www.cnblogs.com/spnooyseed/p/14077533.html