题目描述
\(T\) 组数据，给定长为 \(n\) 的字符串 \(s\) ，\(q\) 次询问，给定 \(i,r\) ，求有多少个 \(l\) 满足：
- \(1\le l\le r\) 。
- \(s[i:i+l-1]\) 字典序小于 \(R(s[i+l:i+2l-1])\) 。
数据范围
- \(1\le T\le 5,1\le n,q\le 10^5,1\le i+2r-1\le n\) 。
时间限制 \(\texttt{1s}\) ，空间限制 \(\texttt{512MB}\) 。
分析
先考虑如何比较这两个字符串的字典序，容易发现这是后缀数组的拿手好戏。具体的，对 \(s+R(s)\) 建立后缀数组，产生贡献当且仅当下面两个条件同时成立：
- \(rk_i\lt rk_{2n+2-i-2l}\) 。
- \(\texttt{lcp}(i,2n+2-i-2l)\lt l\) 。
先只考虑第一个条件并进行计数，算上 \(1\le l\le r\) 的限制，本质上是一个二维数点问题。
将 \((j,rk_j)\) 看成平面上的点，我们需要求出 \(2n+2-i-2r\le x\le 2n-i,y\gt rk_i\) 中的点数，询问离线后按 \(rk\) 倒序枚举 \(i\) ，注意需要对奇偶分别开树状数组。
再考虑第二个条件，我们多算了满足以下条件的 \(l\) ，需要减去：
- \(1\le l\le r\) 。
- \(rk_i\lt rk_{2n+2-i-2l}\) 。
- \(\texttt{lcp}(i,2n+2-i-2l)\ge l\)，即 \(s[i:i+l-1]=R(s[i+l,i+2l-1])\) 。
对于第三个条件，先跑 \(\texttt{manacher}\) 算法，枚举回文中心 \(j=i+l-1\)，则其等价于 \(l\le o_j\) 。这里 \(o_i\) 表示以第 \(i\) 和第 \(i+1\) 个字符中间为中心，最长非 # 回文半径。
对于第二个条件，由于第 \(i\) 个后缀和第 \(2n+2-i-2l\) 个后缀的前 \(l\) 个字符相同，根据字典序的比较规则，我们直接忽略掉这 \(l\) 个字符，所以其等价于 \(rk_{j+1}\lt rk_{2n+1-j}\) 。
现在这个条件只与 \(j\) 有关，它会贡献到满足以下条件的询问：
- \(1\le j-i+1\le\min(r,o_j)\) 。
这个条件等价于：
- \(i\le j\le i+r-1\) 。
- \(j-o_j+1\le i\) 。
再来一遍二维数点即可。
时间复杂度 \(\mathcal O((n+q)\log n)\) 。
#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+5;
int m,n,q,t;
int c[maxn],x[maxn],y[maxn];
int rk[maxn],sa[maxn];
int p[maxn],res[maxn];
char s[maxn];
struct node
{
int x,id,op;
};
vector<node> v1[maxn],v2[maxn];
void get_sa()
{
for(int i=1;i<=n;i++) s[2*n+1-i]=s[i];
memset(c,0,sizeof(c));
memset(y,0,sizeof(y));
int m=122,n=2*::n;
for(int i=1;i<=n;i++) c[x[i]=s[i]]++;
for(int i=1;i<=m;i++) c[i]+=c[i-1];
for(int i=n;i>=1;i--) sa[c[x[i]]--]=i;
for(int k=1;k<=n;k<<=1)
{
int num=0;
for(int i=n-k+1;i<=n;i++) y[++num]=i;
for(int i=1;i<=n;i++) if(sa[i]>k) y[++num]=sa[i]-k;
for(int i=1;i<=m;i++) c[i]=0;
for(int i=1;i<=n;i++) c[x[i]]++;
for(int i=1;i<=m;i++) c[i]+=c[i-1];
for(int i=n;i>=1;i--) sa[c[x[y[i]]]--]=y[i];
for(int i=1;i<=n;i++) y[i]=x[i],x[i]=0;
x[sa[1]]=num=1;
for(int i=2;i<=n;i++)
x[sa[i]]=y[sa[i]]==y[sa[i-1]]&&y[sa[i]+k]==y[sa[i-1]+k]?num:++num;
if(num==n) break;
m=num;
}
for(int i=1;i<=n;i++) rk[sa[i]]=i;
}
void manacher()
{
static char t[maxn];
int m=2*n+1;
for(int i=m;i>=1;i--) p[i]=0,t[i]=i&1?'#':s[i>>1];
for(int i=1,pos=0,mxr=0;i<=m;i++)
{
if(i<=mxr) p[i]=min(p[2*pos-i],mxr-i+1);
while(i+p[i]<=m&&t[i-p[i]]==t[i+p[i]]) p[i]++;
if(i+p[i]-1>mxr) pos=i,mxr=i+p[i]-1;
}
}
struct bit
{
int n,op,c[maxn];
void clean(int _n,int _op)
{
n=_n,op=_op,memset(c,0,4*n);
}
void add(int x,int v)
{
if(!op) while(x) c[x]+=v,x-=x&(-x);
else while(x<=n) c[x]+=v,x+=x&(-x);
}
int query(int x)
{
int res=0;
if(!op) while(x<=n) res+=c[x],x+=x&(-x);
else while(x) res+=c[x],x-=x&(-x);
return res;
}
}b[3];
int main()
{
for(scanf("%*d%d",&t);t--;)
{
scanf("%d%d%s",&n,&q,s+1),m=2*n;
get_sa(),manacher();
b[0].clean(m,0),b[1].clean(m,0),b[2].clean(m,1);
for(int i=1;i<=m;i++) v1[i].clear(),v2[i].clear();
for(int j=1,i=0,r=0;j<=q;j++)
{
scanf("%d%d",&i,&r),res[j]=0;
v1[2*n-i].push_back({rk[i]+1,j,1});
v1[2*n-i-2*r].push_back({rk[i]+1,j,-1});
v2[i+r-1].push_back({i,j,1});
v2[i-1].push_back({i,j,-1});
}
for(int i=1;i<=m;i++)
{
b[i&1].add(rk[i],1);
for(auto u:v1[i]) res[u.id]+=u.op*b[i&1].query(u.x);
}
for(int i=1;i<=n;i++)
{
if(rk[i+1]<rk[2*n+1-i]) b[2].add(i-(p[2*i+1]>>1)+1,1);
for(auto u:v2[i]) res[u.id]-=u.op*b[2].query(u.x);
}
for(int i=1;i<=q;i++) printf("%d\n",res[i]);
}
return 0;
}
总结
- 数点条件不好刻画时可以利用字典序的性质进行转化，笔者考场上就差这一步没想到最终 \(72pts\) 含恨回家。