题解 CF1098F 【Ж-function】

· · 题解

题意 ： 给出一个字符串 S。

定义函数 f(l,r) 为 S[l,r] 的每个后缀与 S[l,r] 的 \mathrm{lcp} 之和。

询问 q 次，每次给出 l,r，请输出 f(l,r)。

------------ 后缀 $i,j$ 的 $\rm lcp$ 即为后缀树上 $i,j$ 两点 $\rm lca$ 的 $dep$ 。 那么， $lcp(S[l,r],S[i,r])=\min(lcadep(i,l),r-i+1)$。 $f(l,r)=\sum\limits_{i=l}^r\min(lcadep(i,l),r-i+1)

先不考虑 \min ，单看 \sum\limits_{i=l}^rlcadep(i,l) ,这就是 P4211 [LNOI2014]LCA。

这对本题有启示。

考虑 l 的一个祖先 u ，其返祖边的贡献系数。

在 P4211 中，贡献系数是 u 子树内 [l,r] 内的点数。

也即 \sum\limits_{i=l}^rlcadep(i,l)=\sum\limits_{\text{u是l的祖先}}\sum\limits_{\text{v是u的子孙}}\big[v\in[l,r]\big]

而在本题中，r-i+1\geq lcadep(i,l)\Rightarrow i\leq r-lcadep(i,l)+1

贡献系数是 u 子树内 [l,r-dep[u]+1] 内的点数。

也即 \sum\limits_{i=l}^r\min(lcadep(i,l),r-i+1)=\sum\limits_{\text{u是l的祖先}}\sum\limits_{\text{v是u的子孙}}\big[v\in[l,r-dep[u]+1]\big]

注意这里考虑的是未压缩的后缀树。

注意到有 \big[x\in[l,r]\big]=\Big(\big[v\leq r\big]-\big[v<l\big]\Big)\big[l\leq r\big]

{\rm Ans}=\sum\limits_{\text{u是l的祖先}}\sum\limits_{\text{v是u的子孙}}\Big(\big[v\leq r-dep[u]+1\big]-\big[v<l\big]\Big)\big[l\leq r-dep[u]+1\big]

可以拆成 [1,l),[1,r-dep[u]+1] 分别计算。

$\sum\limits_{\text{u是l的祖先}}\big[dep[u]\leq r-l+1\big]\sum\limits_{\text{v是u的子孙}}[v<l\big]

模仿 P4211 将点 [1,l) 到根的链上加一，然后查询 l 到根的链上，深度不超过 r-l+1 的点权和。

转到压缩后缀树上计算时有一些细节。

使用树链剖分，复杂度是 O(n\log^2n) 的。

后者可以看作计算 l 到根的链上深度不超过 r-l+1 的部分每个点 u 子树中 [1,r-dep[u]+1] 内的点数。

把树重链剖分，一个询问中符合条件的 u 会被分到 O(\log) 条重链上计算。

对于一条重链，参与贡献的 v 在重链顶的子树中，而重链顶子树大小和是 O(n\log n) 的。

对于询问 [l,r] ，考虑一对 u,v 能贡献的条件。

我们把满足条件 ① 的点对 u,v 变成二维平面上的点 (dep[u],v+dep[u])。

对于询问 [l,r] ,就是要计算矩阵 \big[1,min(dep[t_2],r-l+1)\big]\big[1,r+1\big] 以内的点数。这就是二维偏序了。

然而，满足 ① 的点对 u,v 可能很多，不能暴力加入，考虑观察这些点对的性质。

对于一个 v ，满足条件的 u 是一个前缀（dep[u]\leq dep[t_1]）

转化成 (dep[u],v+dep[u]) 之后，则是一条斜线（上连续的若干整点）。

而前面说了，v 的总规模是 O(n\log n) 的，那么需要加入的斜线条数也是这个量级。

问题完全转化成了这些“斜线”的二维偏序，如图。

把斜线段拆成两条斜射线的差。我们可以断言，一条斜射线必然穿过限制矩形的右侧(蓝色)或者上侧(绿色)，如图。

对于穿过右侧的斜射线，其在矩形内的长度为起始点 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)。

代码实现较为复杂，我写了整整一天……

#include<algorithm>
#include<cstring>
#include<cstdio>
#include<vector>
#define pb push_back
#define ll long long
#define MaxN 200500
using namespace std;
struct Node{int t[26],f,len,p,tf;}a[MaxN<<1];
int tn,las;
void ins(int c)
{
  int p=las,np=++tn;las=np;
  a[np].len=a[p].len+1;
  for (;p&&!a[p].t[c];p=a[p].f)a[p].t[c]=np;
  if (!p)a[np].f=1;
  else {
    int v=a[p].t[c];
    if (a[v].len==a[p].len+1)a[np].f=v;
    else {
      int nv=++tn;a[nv]=a[v];
      a[nv].len=a[p].len+1;
      for (;p&&a[p].t[c]==v;p=a[p].f)a[p].t[c]=nv;
      a[np].f=a[v].f=nv;
    }
  }
}
vector<int> g[MaxN<<1];
int ed[MaxN<<1],td[MaxN],
    in[MaxN<<1],tim,siz[MaxN<<1];
void pfs1(int u)
{
  siz[u]=1;
  for (int i=0,v;i<g[u].size();i++){
    pfs1(v=g[u][i]);
    siz[u]+=siz[v];
    if (siz[v]>siz[a[u].p])
      a[u].p=v;
  }
}
void pfs2(int u,int tf)
{
  a[u].tf=tf;in[u]=++tim;
  if (a[u].p){
    pfs2(a[u].p,tf);
    for (int i=0;i<g[u].size();i++)
      if (a[u].p!=g[u][i])
          pfs2(g[u][i],g[u][i]);
  }
}
int wfl,wfr,wfd;
struct SGT{
  struct SGT_Node{
    ll s,len;int tg;
    inline void ladd(int t)
    {tg+=t;s+=len*t;}
  }a[MaxN<<3];
  int dl[MaxN<<1],dr[MaxN<<1];
  void build(int l,int r,int u)
  {
    if (l==r){a[u].len=dr[l]-dl[l]+1;return ;}
    int mid=(l+r)>>1;
    build(l,mid,u<<1);
    build(mid+1,r,u<<1|1);
    a[u].len=a[u<<1].len+a[u<<1|1].len;
  }
  inline void ladd(int u){
    if (a[u].tg){
      a[u<<1].ladd(a[u].tg);
      a[u<<1|1].ladd(a[u].tg);
      a[u].tg=0;
    }
  }
  void add(int l,int r,int u)
  {
    if (wfl<=l&&r<=wfr){a[u].ladd(1);return ;}
    int mid=(l+r)>>1;ladd(u);
    if (wfl<=mid)add(l,mid,u<<1);
    if (mid<wfr)add(mid+1,r,u<<1|1);
    a[u].s=a[u<<1].s+a[u<<1|1].s;
  }
  int qryp(int l,int r,int u)
  {
    if (l==r)return l;
    int mid=(l+r)>>1;ladd(u);
    if (wfr<=mid)return qryp(l,mid,u<<1);
    if (mid<wfl)return qryp(mid+1,r,u<<1|1);
    if (wfd>=dl[mid+1])return qryp(mid+1,r,u<<1|1);
    return qryp(l,mid,u<<1);
  }
  ll qrys(int l,int r,int u)
  {
    if (wfl<=l&&r<=wfr)return a[u].s;
    int mid=(l+r)>>1;ll ret=0;ladd(u);
    if (wfl<=mid)ret=qrys(l,mid,u<<1);
    if (mid<wfr)ret+=qrys(mid+1,r,u<<1|1);
    return ret;
  }
  void add(int l,int r)
  {wfl=l;wfr=r;add(1,tn,1);}
  int qryp(int l,int r)
  {wfl=l;wfr=r;return qryp(1,tn,1);}
  ll qrys(int l,int r)
  {wfl=l;wfr=r;return qrys(1,tn,1);}
}S;
void padd(int u){
  while(u){
    S.add(in[a[u].tf],in[u]);
    u=a[a[u].tf].f;
  }
}
ll pqry(int u)
{
  ll ret=0;
  while(u){
    if (a[a[a[u].tf].f].len<wfd){
      if (a[u].len<=wfd)
        ret+=S.qrys(in[a[u].tf],in[u]);
      else {
        int p=S.qryp(in[a[u].tf],in[u]);
        ll s0=0,s1=0;
        if (in[a[u].tf]<p)
          s0=S.qrys(in[a[u].tf],p-1);
        s1=S.qrys(p,p);
        ret+=s0+s1/(S.dr[p]-S.dl[p]+1)*max(0,min(S.dr[p],wfd)-S.dl[p]+1);
      }
    }u=a[a[u].tf].f;
  }return ret;
}
struct BIT{
  #define lbit(x) ((x)&-(x))
  ll t[MaxN<<2];int l,n;
  void add(int p,int x){
    p-=l;
    while(p<=n){t[p]+=x;p+=lbit(p);}
  }
  ll qry(int p){
    ll ret=0;p-=l;
    while(p){ret+=t[p];p^=lbit(p);}
    return ret;
  }
}Tc,Tx;
struct Data{int x,y,p;}p[MaxN<<1];
bool cmp(const Data A,const Data B)
{return A.x<B.x;}
vector<Data> b[MaxN<<1],b2[MaxN];
void adq(int u,int r,int i,int lim){
  while(u){
    b[a[u].tf].pb((Data){min(a[u].len,lim)+1,r+1,i});
    u=a[a[u].tf].f;
  }
}
int n,tot,fl,fl2;
void dfs(int u)
{
  if (ed[u]){
    p[++tot]=(Data){fl+1,ed[u]+fl+1,-1};
    p[++tot]=(Data){fl2+1,ed[u]+fl2+1,1};
  }for (int i=0;i<g[u].size();i++)dfs(g[u][i]);
}
ll ans[MaxN];
void calc(vector<Data> &b)
{
  int tp=1;
  for (int i=0;i<b.size();i++){
    Data q=b[i];
    while(tp<=tot&&p[tp].x<=q.x){
      int to=p[tp].y-p[tp].x;
      Tx.add(to,p[tp].p*p[tp].x);
      Tc.add(to,p[tp].p);tp++;
    }
    int l=-n*2,r=q.y-q.x;
    ans[q.p]+=1ll*(Tc.qry(r)-Tc.qry(l-1))*q.x
                 -(Tx.qry(r)-Tx.qry(l-1));
  }
  for (int i=1;i<tp;i++){
    int to=p[i].y-p[i].x;
    Tx.add(to,-p[i].p*p[i].x);
    Tc.add(to,-p[i].p);
  }
}
void solve(int u)
{
  int v=u;
  fl2=a[a[u].f].len;tot=0;
  while(v){
    fl=a[v].len;
    if (ed[v]){
      p[++tot]=(Data){fl+1,ed[v]+fl+1,-1};
      p[++tot]=(Data){fl2+1,ed[v]+fl2+1,1};
    }
    for (int i=0;i<g[v].size();i++)
      if (g[v][i]!=a[v].p)
        dfs(g[v][i]);
    v=a[v].p;
  }sort(p+1,p+tot+1,cmp);
  sort(b[u].begin(),b[u].end(),cmp);
  calc(b[u]);
  for (int i=1;i<=tot;i++)swap(p[i].x,p[i].y);
  for (int i=0;i<b[u].size();i++){
    swap(b[u][i].x,b[u][i].y);
    b[u][i].y--;
  }sort(p+1,p+tot+1,cmp);
  sort(b[u].begin(),b[u].end(),cmp);
  calc(b[u]);
}
int q,lf[MaxN];
char str[MaxN];
int main()
{
  scanf("%s",str+1);
  n=strlen(str+1);
  las=tn=1;
  for (int i=n;i;i--)ins(str[i]-'a');
  for (int i=n,p=1;i;i--){
    p=a[p].t[str[i]-'a'];
    ed[td[i]=p]=i;
  }
  for (int i=2;i<=tn;i++)
    g[a[i].f].pb(i);
  pfs1(1);pfs2(1,1);
  scanf("%d",&q);
  for (int i=1,l,r;i<=q;i++){
    scanf("%d%d",&l,&r);
    adq(td[l],r+1,i,r-l+1);
    b2[l].pb((Data){l,r,i});
  }
  Tc.l=Tx.l=-n*2-1;
  Tc.n=Tx.n=n*4+1;
  for (int i=1;i<=tn;i++)
    if (a[i].tf==i)solve(i);
  for (int i=1;i<=tn;i++){
    S.dl[in[i]]=a[a[i].f].len+1;
    S.dr[in[i]]=a[i].len;
  }S.build(1,tn,1);
  for (int i=1;i<=n;i++){
    for (int j=0;j<b2[i].size();j++){
      wfd=b2[i][j].y-i+1; 
      ans[b2[i][j].p]-=pqry(td[i]);
    }padd(td[i]);
  }
  for (int i=1;i<=q;i++)
    printf("%lld\n",ans[i]);
  return 0;
}