题解 P6629 【[ZJOI2020] 字符串】
command_block
·
·
题解
题意 ： 若存在字符串 t 使得 s=tt ，则称 s 是优美的。
给出字符串 s ，q 次询问一个子串 s[l,r] 的本质不同的优美子串个数。
------------
配合 [Blog : Lyndon & Runs](https://www.luogu.com.cn/article/d4y3zqqv) 食用。
- **定理** ：位置不同的本原平方串共 $O(n\log n)$ 个。
- **定理** ： 对于一个 ${\rm run}\ {\bf r}=(l,r,p)$ ，对于所有 $l\leq i\leq r-2p+1$ ，$[i,i+2p-1]$ 都是一个本原平方串。
求解 $\rm Runs$ 和所有本原平方串的算法在上方博文中有介绍，不再赘述。
我们选出 $s$ 的所有**位置不同**的平方串集合 $Sq_0$ ，本质相同的串可能重复出现。
令 $c[l,r]=\big[s[l,r]\in Sq_0\big]$。
若询问 $s[L,R]$ ，相当于对矩形区域 $\begin{cases}L\leq l\\r\leq R\end{cases}$ 求和。
接下来消去重复贡献，对于本质相同的平方串 $s[l_1,r_1],s[l_2,r_2],...,s[l_m,r_m]\ (l_1<l_2<...<l_m)$ ，令 $c[l_1,r_2],c[l_2,r_3],...,c[l_{m-1},r_m]$ 减去 $1$。
如图，红色点代表本质相同的平方串，灰色部分是询问区域，蓝色点是修正。
不难发现，若有 $n$ 个红色点在询问区域内，则必有 $n-1$ 个蓝色点也在询问区域内，所以一个本质相同的平方串贡献总是 $1$。
先来考虑如何简单地刻画 $Sq_0$。
某个普通平方串一定能表示成一个本原平方串重复若干次的形式。
具体地，对于 ${\rm run}\ {\bf r}=(l,r,p)$ ，枚举 $len=2kp,k\in N^+,l\leq i\leq r-len+1$ ，则 $s[i,i+len-1]$ 是一个普通平方串。
由于周期同为 $p$ 的不同 ${\rm run}$ 交不会达到 $p$ ，上述枚举在 $Sq_0$ 中没有重复。
不难发现，$len$ 相同的一组普通平方串在 $c$ 中是条斜线。为 $(l,l+len-1),(r-len+1,r)$。
接下来考虑扣除的贡献。
同个 $\rm run$ 产生的两个普通平方串相同的充要条件是 ： $len$ 相同，且 $s[i,i+len-1],s[j,j+len-1]$ 中 $p|i-j$。
如图，红点是一组 $len$ 相同的普通平方串，蓝点则是间隔为 $p$ （ 图中 $p=3$ ）的两个普通平方串产生的重复抵消贡献。
不难发现这也是一条斜线，且为 $(l,l+len+p-1),(r-len-p+1,r)$。
可能的 $len$ 的数目显然不超过指数 $e_{\bf r}=\dfrac{r-l+1}{p}$ ，根据 $\text{The Runs Theorem}$ ，这部分产生的斜线总数为 $O(n)$。
接下来计算不同的 $\rm run$ 之间产生的重复。
用哈希表记下目前枚举出的所有本质不同的平方串。具体地，对于 ${\rm run}\ {\bf r}=(l,r,p)$ ，枚举 $l\leq i<l+p,len=2kp,k\in N^+,i+len-1\leq r)$ ，则 $s[i,i+len-1]$ 是一个在该 $\rm run$ 内某类本质不同的普通平方串的最靠左的出现。
不难发现这样的枚举量不超过本原平方串的总个数 $r-l+2-2p$ ，而后者的总和根据相关理论是 $O(n\log n)$ 的。
按照 $l$ 递增的顺序考虑 $\rm Runs$ ，当枚举到某个串发现 $\rm Hash$ 表中已经有了，则在上一个串的最右出现和这一个串的最左出现之间建立抵消贡献点（深蓝色），如图 ：
这最多产生 $O(n\log n)$ 个额外的点。
现在我们把问题转化成了 : 维护一个 $n\times n$ 的矩阵 $c$ ，支持斜线加减，单点加减，最后子矩阵查询。
单点的二维偏序是简单的，下面来看斜线的二维偏序。
把斜线段拆成两条斜射线的差。我们可以断言，一条斜射线必然穿过限制矩形的右侧(蓝色)或者上侧(绿色)，如图。
对于穿过右侧的斜射线，其在矩形内的长度为起始点 $x$ 坐标与右边界 $x$ 坐标的差。
对于穿过上边界的，则和 $y$ 坐标有关。考虑分别统计。
若矩形右上角为 $(x_L,y_L)$ 直线 $y=x+b$ 与 $x=x_L$ 的交点会是 $x_L+b$。
若 $x_L+b\leq y_L\Leftrightarrow b\leq y_l-x_l$ 则与右侧相交。区间求和即可。需要维护 $x,$ 坐标和以及起始点个数。
对于与上侧相交的情况，翻转坐标系处理即可。
总复杂度 $O(n\log^2n)$。
```cpp
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<map>
#define Pr pair<int,int>
#define mp make_pair
#define MaxN 205000
#define ll long long
using namespace std;
struct StrHash{
ll p[MaxN],h[MaxN];int mod,buf;
StrHash (int _buf,int _mod){buf=_buf;mod=_mod;}
void Init(char *s,int n)
{
p[0]=1;
for (int i=1;i<=n;i++){
p[i]=p[i-1]*buf%mod;
h[i]=(h[i-1]*buf+s[i]-'a'+1)%mod;
}
}
bool tl(int u,int v,int len)
{return (h[u]-h[v]+(h[v-len]-h[u-len])*p[len])%mod==0;}
bool tr(int u,int v,int len)
{return (h[u+len-1]-h[v+len-1]+(h[v-1]-h[u-1])*p[len])%mod==0;}
int get(int l,int r)
{return (h[r]+(mod-h[l-1])*p[r-l+1])%mod;}
}h1(10,1000000007),h2(10,1000000009);
int n;char s[MaxN];
int extl(int u,int v)
{
if (s[u]!=s[v])return 0;
int l=1,r=min(u,v),mid;
while(l<r){
mid=(l+r+1)>>1;
if (h1.tl(u,v,mid)&&h2.tl(u,v,mid))l=mid;
else r=mid-1;
}return l;
}
int extr(int u,int v)
{
if (s[u]!=s[v])return 0;
int l=1,r=n-max(u,v)+1,mid;
while(l<r){
mid=(l+r+1)>>1;
if (h1.tr(u,v,mid)&&h2.tr(u,v,mid))l=mid;
else r=mid-1;
}return l;
}
struct Runs{int l,r,p;}b[MaxN*20];
bool cmpR(const Runs &A, const Runs &B)
{return A.l==B.l ? (A.r==B.r ? A.p<B.p : A.r<B.r) : A.l<B.l;}
int tot;
int chk(int u,int v)
{
int tl=extl(u,v),tr=extr(u,v);
if (tl+tr>=v-u+1){
b[++tot]=(Runs){u-tl+1,v+tr-1,v-u};
return v+tr-1;
}return 0;
}
void getRuns()
{
for (int p=1;p<=n;p++)
for (int k=p,mx=0;k+p<=n;k+=p)
if (mx<k)
mx=max(mx,chk(k,k+p)-p);
sort(b+1,b+tot+1,cmpR);
int m=0;
for (int i=1;i<=tot;i++)
if (b[i].l!=b[i-1].l||b[i].r!=b[i-1].r)
b[++m]=b[i];
tot=m;
}
int ans[MaxN];
struct Qry{int l,r,p;}q[MaxN];
struct Point{int x,y,c;}g[MaxN*20];
int tn,m;
#define lbit(x) ((x)&-(x))
struct SumDS
{
ll t[MaxN<<1],sum;
void clr(){memset(t,0,sizeof(ll)*(n+n+1));sum=0;}
void add(int p,int c){
p+=n;sum+=c;
while(p<=n+n){t[p]+=c;p+=lbit(p);}
}
ll qry(int p){
ll ret=0;p+=n;
while(p){ret+=t[p];p^=lbit(p);}
return ret;
}
}T,Tx;
bool cmpQl(const Qry &A,const Qry &B){return A.l<B.l;}
bool cmpQr(const Qry &A,const Qry &B){return A.r<B.r;}
bool cmpP(const Point &A,const Point &B){return A.x<B.x;}
void calc0()
{
sort(q+1,q+m+1,cmpQl);
sort(g+1,g+tn+1,cmpP);
static int o[MaxN];
for (int i=1;i<=tn;i++)o[g[i].y]+=g[i].c;
for (int i=1;i<=n;i++)o[i]+=o[i-1];
for (int i=1,j=1;i<=m;i++){
for (;g[j].x<=q[i].l&&j<=tn;j++)T.add(g[j].y,g[j].c);
ans[q[i].p]+=o[q[i].r]-T.qry(q[i].r);
}
}
void calc1()
{
sort(g+1,g+tn+1,cmpP);
T.clr();
for (int i=1,j=1;i<=m;i++){
for (;g[j].x<=q[i].l&&j<=tn;j++){
T.add(g[j].y-g[j].x,g[j].c);
Tx.add(g[j].y-g[j].x,g[j].c*g[j].x);
}ll cnt=T.qry(q[i].r-1-q[i].l),sx=Tx.qry(q[i].r-1-q[i].l);
ans[q[i].p]-=cnt*(q[i].l+1)-sx;
}
for (int i=1;i<=tn;i++)swap(g[i].x,g[i].y);
sort(g+1,g+tn+1,cmpP);
sort(q+1,q+m+1,cmpQr);
T.clr();Tx.clr();
for (int i=1,j=1;i<=m;i++){
for (;g[j].x<=q[i].r&&j<=tn;j++){
T.add(g[j].y-g[j].x,g[j].c);
Tx.add(g[j].y-g[j].x,g[j].c*g[j].x);
}ll cnt=T.sum-T.qry(q[i].l-q[i].r),sx=Tx.sum-Tx.qry(q[i].l-q[i].r);
ans[q[i].p]+=cnt*(q[i].r+1)-sx;
}
}
map<Pr,int> ss;
int main()
{
scanf("%d%d%s",&n,&m,s+1);n=strlen(s+1);
h1.Init(s,n);h2.Init(s,n);
getRuns();
for (int i=1;i<=m;i++){
scanf("%d%d",&q[i].l,&q[i].r);
q[i].l--;q[i].p=i;
}
for (int t=1;t<=tot;t++){
int l=b[t].l,r=b[t].r,p=b[t].p;
for (int len=2*p;len<=r-l+1;len+=2*p){
for (int i=l;i+len-1<=r&&i<l+p;i++){
int j=i+len-1;
Pr now=mp(h1.get(i,j),h2.get(i,j));
if (ss.count(now))
g[++tn]=(Point){ss[now],j,-1};
ss[now]=(r-(i-1)%p)/p*p+(i-1)%p-len+1;
}
}
}calc0();tn=0;
for (int t=1;t<=tot;t++){
int l=b[t].l,r=b[t].r,p=b[t].p;
for (int len=2*p;len<=r-l+1;len+=2*p){
g[++tn]=(Point){l,l+len-1,1};
g[++tn]=(Point){r-len+2,r+1,-1};
if (l<=r-len-p+1){
g[++tn]=(Point){l,l+len+p-1,-1};
g[++tn]=(Point){r-len-p+2,r+1,1};
}
}
}calc1();
for (int i=1;i<=m;i++)
printf("%d\n",ans[i]);
return 0;
}
```