题面

思路

看到网上都写树套树？就我直观的想法是离线然后\(cdq\)吗...

发现比较麻烦的是那个交换操作，考虑对询问离线，那么每个原串对答案的贡献就被交换操作分为\(O(m)\)个在一个时间段上的贡献。把原串的时间段和询问的下标区间都分为“后减前”这两段，转化为二维偏序问题。

考虑如何处理lcp的条件限制，原本以为可以直接对原串暴力在trie树上跑一遍产生贡献，询问直接在串对应的trie树上的点的最后一个点查，然而可能存在一个很长的串\((2e5)\)被划分了很多次\((2e5)\)的情况，就gg了。

这时候考虑原串只在对应的\(trie\)树上的点的最后一个产生贡献，那么统计答案的时候要算的是子树的和，于是化成\(dfs\)序的偏序问题，那么就多了一维偏序，\(cdq\)分治+树状数组即可。

效率\(O(nlog^2n)\)，还有四倍的常数，好像有点垃圾，不过好在\(cdq\)分治和树状数组常数都不大。

吐槽

好久没写大数据结构了，感觉明明不是很难（应该说是一道中规中矩的数据结构题）却搞了半天，挺离谱的...
在调的时候主要的错误，一个是一开始没认真分析效率，TLE了还以为是被卡常，浪费了很久；然后还有诸如cdq分治最后一层忘记排序就返回之类的细节问题。

代码

#include
using namespace std;
const int N=1e6+5,M=26;
int n,m,tp,tq,fp[N],fq[N];
struct node{
	int t,x,u,d,p;
}p[N],q[N];
int to[N][M],dn[N],sz[N],pu[N],tt=1;
//trie
int dfs(int u){
	sz[u]=1; dn[u]=++tt;
	for(int i=0;i>1;
	work(l,mid); work(mid+1,r);
	int j=fp[l];
	for(int i=fq[mid+1];i=fp[r+1] || p[tl].x<=p[tr].x) ) pp[i]=p[tl++];
		else pp[i]=p[tr++];
	}
	for(int i=fp[l];i=fq[r+1] || q[tl].x<=q[tr].x) ) qq[i]=q[tl++];
		else qq[i]=q[tr++];
	}
	for(int i=fq[l];i>n>>m;
	for(int i=1;i<=n;i++){
		scanf("%s",ch);
		int l=strlen(ch),u=1;
		for(int j=0;j