Problem Link

题目大意

给定长度为 $n$ 的字符串 $S$，$q$ 次询问给定 $x,k$，求有多少 $i\in[1,k]$ 满足 $S[x,x+i-1]<\mathrm{rev}(S[x+i,x+2i-1])$，$<$ 表示字典序比较。

数据范围：$n,q\le 10^5$。

思路分析

考虑如何判定一组 $(x,i)$ 合法，首先可以比较后缀 $S[x,n]$ 和前缀 $S[1,x+2i-1]$，可以对 $S+\mathrm{rev}(S)$ 建后缀数组处理出每个后缀 $S[i,n]$ 的排名 $R_i$ 和前缀的排名 $L_{x+2i-1}$。

那么一组 $(x,i)$ 合法当且仅当 $R_x<L_{x+2i-1}$ 并且 $S[x,x+2i-1]$ 不是回文串。

先考虑怎么对满足第一个条件的点计数，对 $L$ 降序扫描线，相当于求 $[x,x+2k)$ 中有多少被已插入的元素和 $x$ 奇偶性不同，对奇数和偶数分别建树状数组维护即可。

然后我们要去掉 $R_x<L_{x+2i-1}$ 且 $S[x,x+2i-1]$ 回文的情况，设以 $(i,i+1)$ 为回文中心的最长回文半径为 $d_i$，那么第二个条件就是 $d_{i+x-1}\ge i$。

第一个条件不好处理，但我们发现 $S[x,x+i-1]=S[x+i,x+2i-1]$ 时一定有 $[R_x<L_{x+2i-1}]=[R_{i+x}<L_{i+x-1}]$，事实上就是给两个串的开头删去相等的一段字符。

那么我们只要把不满足 $R_{i+1}<L_i$ 的 $d_i$ 设成 $-\infty$，然后只要数 $i\in [x,x+k-1]$ 中有多少 $i-d_i+1\le x$，注意到 $i< x$ 的时候只要 $d_i\ne-\infty$ 恒成立，因此可以预处理前缀和解决一半。

时间复杂度 $\mathcal O((n+q)\log n)$。

代码呈现

#include<bits/stdc++.h>
#define ull unsigned long long
using namespace std;
const int MAXN=2e5+5;
mt19937_64 rnd(time(0));
char str[MAXN];
int sa[MAXN],rk[MAXN],wt[MAXN],len[MAXN],ht[MAXN][20];
int bit(int x) { return 1<<x; }
void init(int n) {
	iota(sa+1,sa+n+1,1);
	sort(sa+1,sa+n+1,[&](int x,int y){ return str[x]<str[y]; });
	for(int i=1,j;i<=n;) {
		for(j=i;j<n&&str[sa[j+1]]==str[sa[i]];++j);
		len[i]=j-i+1;
		while(i<=j) rk[sa[i++]]=j;
	}
	for(int k=1;k<n;k<<=1) {
		for(int l=1,r;l<=n;++l) if(len[l]>1) {
			r=l+len[l]-1;
			for(int i=l;i<=r;++i) wt[sa[i]]=(sa[i]+k>n?0:rk[sa[i]+k]);
			sort(sa+l,sa+r+1,[&](int x,int y){ return wt[x]<wt[y]; });
			for(int i=l,j;i<=r;) {
				for(j=i;j<r&&wt[sa[j+1]]==wt[sa[i]];++j);
				len[i]=j-i+1;
				while(i<=j) rk[sa[i++]]=j;
			}
			l=r;
		}
	}
	for(int i=1,k=0;i<=n;++i) {
		k=max(k-1,0);
		while(str[i+k]==str[sa[rk[i]-1]+k]) ++k;
		ht[rk[i]][0]=k;
	}
	for(int k=1;k<20;++k) for(int i=1;i+bit(k)-1<=n;++i) {
		ht[i][k]=min(ht[i][k-1],ht[i+bit(k-1)][k-1]);
	}
}
int lcp(int x,int y) {
	int l=min(rk[x],rk[y])+1,r=max(rk[x],rk[y]),k=__lg(r-l+1);
	return min(ht[l][k],ht[r-bit(k)+1][k]);
}
int n,q,L[MAXN],R[MAXN],id[MAXN],ans[MAXN],d[MAXN],cnt[MAXN];
bool mk[MAXN];
vector <array<int,3>> Q1[MAXN],Q2[MAXN];
struct FenwickTree {
	int tr[MAXN],s;
	void init() { memset(tr,0,sizeof(tr)); }
	void add(int x) { for(;x<=n;x+=x&-x) ++tr[x]; }
	int qry(int x) { for(s=0;x;x&=x-1) s+=tr[x]; return s; }
}	T[2];
void solve() {
	scanf("%d%d%s",&n,&q,str+1);
	str[n+1]='#',str[2*n+2]='|';
	for(int i=1;i<=n;++i) str[2*n+2-i]=str[i];
	init(2*n+2);
	for(int i=1;i<=n;++i) R[i]=rk[i],L[i]=rk[2*n+2-i];
	for(int i=1;i<n;++i) {
		d[i]=lcp(i+1,2*n+2-i);
		mk[i]=(R[i+1]<L[i]),cnt[i]=cnt[i-1]+mk[i];
	}
	iota(id+1,id+n+1,1);
	sort(id+1,id+n+1,[&](int x,int y){ return L[x]<L[y]; });
	for(int i=1,x,k;i<=q;++i) {
		scanf("%d%d",&x,&k),ans[i]=0;
		int l=1,r=n,p=n+1;
		while(l<=r) {
			int m=(l+r)>>1;
			if(R[x]<L[id[m]]) p=m,r=m-1;
			else l=m+1;
		}
		if(p<=n) {
			Q1[p].push_back({x,k,i});
			ans[i]+=cnt[x-1];
			Q2[x+k-1].push_back({x,k,i});
		}
	}
	T[0].init(),T[1].init();
	for(int i=n;i>=1;--i) {
		T[id[i]&1].add(id[i]);
		for(auto z:Q1[i]) {
			int x=z[0],k=z[1],r=(x^1)&1;
			ans[z[2]]+=T[r].qry(x+2*k-1)-T[r].qry(x-1);
		}
	}
	T[0].init();
	for(int i=1;i<=n;++i) {
		if(mk[i]) T[0].add(i-d[i]+1);
		for(auto z:Q2[i]) ans[z[2]]-=T[0].qry(z[0]);
	}
	for(int i=1;i<=q;++i) printf("%d\n",ans[i]);
	for(int i=1;i<=n;++i) Q1[i].clear(),Q2[i].clear();
}
signed main() {
	int C,O; scanf("%d%d",&C,&O);
	while(O--) solve();
	return 0;
}