题意：
给定你一个长度为\(n\)的字符串\(s\)，\(m\)个询问，每次询问给定\(x,y\)，问你\(s[1,x]\)和\(s[n-y+1,n]\)这两个前缀后缀串拼接形成的字符串\(s‘\)在主串\(s\)中出现了几次。

思路：
首先解决这道题目前，如果大家没做过P5829，强烈推荐先做一下，\(border\)树的模板题，做过之后更好理解\(border\)应用的含义。
看到前缀和后缀，我们可以考虑一些字符串的特殊搞题方法，这里就是通过\(border\)完成一个转化。
假设拼接后子串出现在\(s\)的某个区间\([l,r]\)内，那么我们可以得到\(s_{1...x} = s_{l...l+x-1}\)，\(s_{n-y+1....n} = s_{r-y+1....r}\)这两个等式，并且\((l + x - 1) + 1 = r - y +1\)，这样才能保证两个子串恰好拼接。

所以现在我们的问题可以理解为，每次询问\(x,y\)后，\(s\)串有多少个位置\(a\)，使得\(s_{1...x}=s_{a-x+1...a}\)，即多少个位置的长度为\(x\)的后缀和前缀相等，这不就是我们对于一个串中的\(border\)的定义嘛，考虑对每个位置\(i\)由它的\(fail_i\)向\(i\)连边，构造\(border\)树，那么\(x\)的子树内的点是不是都是符合条件的点，即一定存在一个长度为\(x\)的公共前后缀。

再考虑s的后缀，即找到\(s_{r-y+1...r} = s_{n-y+1...n}\)，我们只需要倒序遍历\(s\)，即可把后缀转化为前缀，对称来看的话（且为了保持树中节点编号大小的单调性），失配指针默认从\(n+1\)而不是\(0\)开始。倒序对每个位置\(i\)同样也是由\(fail_i\)向\(i\)连边，那么满足条件的所有位置\(r-y+1\)记为\(b\)，一定存在于\(n-y+1\)这个点的子树中

这样问题就变成了，每次询问分别给出两棵树上的两个点，求出这两个数中，有多少个节点\(u,v\)（\(u\)属于前缀\(border\)树，\(v\)属于后缀）满足\(u + 1 = v\)，即可看做求两个子树中节点值相同的点有多少个。

考虑\(dfs\)序转化成线性结构，然后主席树查询操作，把一棵数看做区间，一棵树看做值域，二维数点问题嘛。

我们对前缀的\(border\)树按照其\(dfs\)序的编号顺序建树，保证查询区间代表第一棵树的某个子树的范围。
之后类似于二维数点顺着\(x\)坐标更新\(y\)范围内的值，顺着第一棵树的节点顺序，在第二棵树代表的\(dfs\)序范围内更新信息。
那么我们对值域进行插入的时候考虑就应该是是后缀\(border\)树的\(dfs\)序了。
即我们找到\(dfn1[tim1] + 1\)(\(+1\)因为是找\(a+1=b\))这个值在后缀\(border\)树中的时间戳位置(即\(in2[dfn[tim1]+1]\))更新一下，那么我们查询的时候就查询\(y\)子树对应的时间戳的内值即可。

#include <bits/stdc++.h>

using namespace std;

#define pb push_back
#define eb emplace_back
#define MP make_pair
#define pii pair<int,int>
#define pll pair<ll,ll>
#define lson rt<<1
#define rson rt<<1|1
#define CLOSE std::ios::sync_with_stdio(false)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef double db;
const int INF = 0x3f3f3f3f;
const db eps = 1e-6;
const int N = 2e5 + 10;
char s[N];
int nex[N],renex[N],n,m;
std::vector<int>G1[N],G2[N];

void getborder() {
	nex[0] = 0,nex[1] = 0;
	for(int i = 2,j = 0;i <= n;i ++) {
		while(j != 0 && s[j+1] != s[i]) j = nex[j];
		if(s[j+1] == s[i]) ++j;
		nex[i] = j;
	}
	//倒着做 r - y + 1 一定在 n - y + 1的子树中 y为后缀长度 否则无法保证连续
	renex[n+1] = renex[n] = n + 1;
	for(int i = n - 1,j = n + 1;i >= 1;i --) {
		while(j != n + 1 && s[j-1] != s[i]) j = renex[j];
		if(s[j-1] == s[i]) --j;
		renex[i] = j;
	}
}

int dfn1[N],dfn2[N],in1[N],in2[N],siz1[N],siz2[N],tim1,tim2;
void dfs1(int u) {
	siz1[u] = 1;
	in1[u] = ++tim1;
	dfn1[tim1] = u;
	for(auto v : G1[u]) {
		dfs1(v);
		siz1[u] += siz1[v];
	}
}
void dfs2(int u) {
	siz2[u] = 1;
	in2[u] = ++tim2;
	dfn2[tim2] = u;
	for(auto v : G2[u]) {
		dfs2(v);
		siz2[u] += siz2[v];
	}
}

int tr[N*25],lc[N*25],rc[N*25],root[N],tot;
void build(int &now,int l,int r) {
	now = ++tot;
	if(l == r) { tr[now] = 0; return ;}
	int mid = (l + r) >> 1;
	build(lc[now],l,mid); build(rc[now],mid+1,r);
	tr[now] = tr[lc[now]] + tr[rc[now]];
}
void modify(int &now,int pre,int l,int r,int p) {
	tr[now = ++tot] = tr[pre],lc[now] = lc[pre],rc[now] = rc[pre];
	if(l == r) { tr[now]++; return ; }
	int mid = (l + r) >> 1;
	if(p <= mid) modify(lc[now],lc[pre],l,mid,p);
	else modify(rc[now],rc[pre],mid+1,r,p);
	tr[now] = tr[lc[now]] + tr[rc[now]]; 
}
int query(int now,int pre,int l,int r,int L,int R) {
	if(l >= L && r <= R) return tr[now] - tr[pre];
	int mid = (l + r) >> 1,ans = 0;
	if(L <= mid) ans += query(lc[now],lc[pre],l,mid,L,R);
	if(R > mid) ans += query(rc[now],rc[pre],mid+1,r,L,R);
	return ans;
}
void solve() {
	scanf("%d%d",&n,&m);
	for(int i = 0;i <= n + 1;i ++) G1[i].clear(),G2[i].clear();
	scanf("%s",s+1);
	getborder();
	// for(int i = 1;i <= n;i ++) cout << i << ": " << nex[i] << ‘\n‘;
	// for(int i = n;i >= 1;i --) cout << i << ": " << renex[i] << ‘\n‘;
	for(int i = 1;i <= n;i ++) G1[nex[i]].pb(i);
	for(int i = n;i >= 1;i --) G2[renex[i]].pb(i);
	tim1 = tim2 = 0;
	dfs1(0);
	dfs2(n+1);
	tot = 0;
	build(root[0],1,tim2);
	for(int i = 1;i <= tim1;i ++) {
		// cout << dfn1[i] << ‘ ‘ << in2[dfn1[i]+1] << "***\n";
		modify(root[i],root[i-1],1,tim2,in2[dfn1[i]+1]);
	}
	int x,y;
	// for(int i = 1;i <= tim1;i ++) cout << i << ": " << in1[i] << ‘\n‘;
	while(m--) {
		scanf("%d%d",&x,&y);
		int l = in1[x],r = in1[x] + siz1[x] - 1;
		y = n - y + 1;
		int ans = query(root[r],root[l-1],1,tim2,in2[y],in2[y]+siz2[y]-1);
		printf("%d\n",ans);
	}
}

int main() {
	int T;scanf("%d",&T);
	while(T--) solve();
	return 0;
}

2021“MINIEYE杯”中国大学生算法设计超级联赛（10）Pty loves string （border树应用 + 主席树 + dfs序）