题解 P7046 【「MCOI-03」诗韵】
万弘
2020-11-03 19:46:25
在[我的博客](https://oierwanhong.cc/2020/11/03/Luogu%20P7046%20%E3%80%8CMCOI-03%E3%80%8D%E8%AF%97%E9%9F%B5/)中查看
给一个串 $ T $ ,和一个大小为 $ m $ 的子串集合 $ \{T[l_i,r_i]|1\le i\le m\} $ ,记为 $ S $ .和一个定值 $ K $ .
定义 $ \text{CS}(A) $ 表示 $ A $ 中所有串的 CS(公共后缀)的集合。
求 $ |{\bigcup_{A\subset S,|A|>K}}\ \text{CS(A)}| $ 和 $ \max_{A\subset S,|A|>K}\max(\text{CS(A)}) $ .
$ |T|\le 5\times 10^5,m\le 5\times 10^5,0\le K\le m. $ 可能形式化之后反而不太清楚了,可以去看看原题面。
这里介绍一种重工业做法。
先建 T 的 SAM。对于每个 $ T[l_i,r_i] $ 我们找到其在SAM上的对应节点(最浅的满足 $ maxlen\ge r_i-l_i+1 $ 的点)。如果这个串的长度恰好等于该点的 $ maxlen $ ,那么其贡献就是该点到根的路径上所有点出现次数+1;否则对这个点来说,长度 $ \le r_i-l_i+1 $ 的串出现次数+1,然后祖先的出现次数+1.一个点表示的不同串的出现次数不同很难搞,干脆直接给这个子串新建一个点,放在原本的点和原本的父亲中间,就能保证每个点表示的所有串出现次数都相同(这样加点后我们仍然保留了parent 树最重要的性质,即祖先表示的串都是当前串的后缀)
那么现在我们就要支持三种操作:
0. 在一条链上找到一个最浅的点满足 $ maxlen\ge r-l+1 $ .同时可能要在这个点和其父亲中加入一个点
1. 链上所有点出现次数+1
2. 询问整棵树上所有满足出现次数 $ >k $ 的子串的数量和最大长度。
~~什么毒瘤~~
对于操作0,由于要动态加点,倍增没法维护,那就用 LCT 维护,并令 splay 上每个点维护一下子树中最大len值,找一个最浅的满足 $ maxlen\ge r-l+1 $ 的点就先`access`然后在 splay 上二分找。
此外可以发现我们先做完所有0操作再去做1和2不会对答案产生任何影响,即对于操作1,2,树是静态的。
但还是不太可做,强行做可能会出现树剖然后树套树的诡异东西。转而考虑离线,对加点后的 SAM 上每个点求其出现次数 $ >k $ 的最早时间。这东西我们可以整体二分,然后链加变成单点修改询问子树和,就可以在dfs序上建树状数组维护了。
令加点后的 parent 树点数为 $ n $ ,则复杂度分析如下:
0操作的总复杂度是 $ \mathcal O(m\log n) $ ,log 是 LCT 的 log。LCT 只要用有根树 LCT,所以常数也不太大。
1和2操作的总复杂度 $ \mathcal O((n+m)\log^ 2n) $ .由于树状数组常数爆小,所以能过。
```cpp
/**********/
#define MAXN 2000011
int n,m,k,dfn[MAXN],edn[MAXN],cur;
namespace BIT
{
int t[MAXN];
#define lowb (i&-i)
void modify(int i,int k)
{
while(i<=cur)t[i]+=k,i+=lowb;
}
int Qsum(int i)
{
int res=0;
while(i)res+=t[i],i-=lowb;
return res;
}
int Qsum(int l,int r){ return Qsum(r)-Qsum(l-1);}
}
namespace SAM
{
int t[MAXN/2][26],pre[MAXN],len[MAXN];
int last=1,tot=1;
void extend(int w)
{
int pos=last,cur=++tot;
len[cur]=len[pos]+1,last=cur;
while(pos&&!t[pos][w])t[pos][w]=cur,pos=pre[pos];
if(!pos){pre[cur]=1;return;}
int nxt=t[pos][w];
if(len[nxt]==len[pos]+1)pre[cur]=nxt;
else
{
int tmp=++tot;
len[tmp]=len[pos]+1,memcpy(t[tmp],t[nxt],sizeof t[nxt]);
pre[tmp]=pre[nxt],pre[cur]=pre[nxt]=tmp;
while(pos&&t[pos][w]==nxt)t[pos][w]=tmp,pos=pre[pos];
}
}
}
struct LCT
{
int fa[MAXN],son[MAXN][2],mx[MAXN];
void init(){for(int i=2;i<=SAM::tot;++i)fa[i]=SAM::pre[i];}
bool not_root(int x){return son[fa[x]][0]==x||son[fa[x]][1]==x;}
void pushup(int x){mx[x]=max(SAM::len[x],max(mx[son[x][0]],mx[son[x][1]]));}
void rotate(int x)
{
int y=fa[x],z=fa[y],k=(son[y][1]==x);
if(not_root(y))son[z][son[z][1]==y]=x;
fa[x]=z;
son[y][k]=son[x][!k],fa[son[x][!k]]=y;
son[x][!k]=y,fa[y]=x;
pushup(y);
}
void splay(int x)
{
while(not_root(x))
{
int y=fa[x];
if(not_root(y))rotate((son[y][1]==x)==(son[fa[y]][1]==y)?y:x);
rotate(x);
}
pushup(x);
}
void access(int x)
{
for(int y=0;x;y=x,x=fa[x])
splay(x),son[x][1]=y;
}
void link(int x,int y){access(x),splay(x),fa[x]=y;}
void cutfa(int x){access(x),splay(x), fa[son[x][0]]=0,son[x][0]=0,pushup(x);}
int find(int x,int len)
{
access(x),splay(x);
while(1)
{
if(mx[son[x][0]]>=len)x=son[x][0];
if(SAM::len[x]>=len)break;
x=son[x][1];
}
return splay(x),x;
}
}lct;
struct edge{int v,nxt;}e[MAXN<<1|1];
int cnt=0,last[MAXN];
void adde(int u,int v){e[++cnt].v=v,e[cnt].nxt=last[u],last[u]=cnt;}
void dfs(int u)
{
dfn[u]=++cur;
for(int i=last[u];i;i=e[i].nxt)
{
int v=e[i].v;
if(v!=SAM::pre[u])dfs(v);
}
edn[u]=cur;
}
int ed[MAXN];
char ss[MAXN];
struct one{int u,r;}a[MAXN],la[MAXN],ra[MAXN];
int res[MAXN],node[MAXN];
ll c[MAXN],mx[MAXN];
void solve(int begin,int end,int dep,int l,int r)
{
if(begin>end)return;
if(l==r)
{
for(int i=begin;i<=end;++i)res[a[i].u]=l;
return;
}
int mid=(l+r)>>1,itl=0,itr=0;
for(int i=l;i<=mid;++i)
if(node[i])BIT::modify(dfn[node[i]],1);
for(int i=begin;i<=end;++i)
{
int c=BIT::Qsum(dfn[a[i].u],edn[a[i].u]);
if(a[i].r<=c)la[++itl]=a[i];
else a[i].r-=c,ra[++itr]=a[i];
}
for(int i=l;i<=mid;++i)
if(node[i])BIT::modify(dfn[node[i]],-1);
for(int i=1;i<=itl;++i)a[begin+i-1]=la[i];
for(int i=1;i<=itr;++i)a[begin+itl+i-1]=ra[i];
solve(begin,begin+itl-1,dep+1,l,mid),solve(begin+itl,end,dep+1,mid+1,r);
}
bool vis[MAXN];
int main()
{
n=read(),m=read(),k=read();
scanf("%s",ss+1);
for(int i=1;i<=n;++i)SAM::extend(ss[i]-'a'),ed[i]=SAM::last;
lct.init();
for(int i=1;i<=m;++i)
{
int l=read(),r=read();
int p=lct.find(ed[r],r-l+1);
if(SAM::len[p]==r-l+1)node[i]=vis[p]?0:p;
else{SAM::len[++SAM::tot]=r-l+1,SAM::pre[SAM::tot]=SAM::pre[p],SAM::pre[p]=SAM::tot,lct.cutfa(p),lct.link(SAM::tot,SAM::pre[SAM::tot]),lct.link(p,SAM::tot);node[i]=SAM::tot;}
vis[node[i]]=1;
}
for(int i=1;i<=SAM::tot;++i)a[i]=one{i,k+1},adde(SAM::pre[i],i);
dfs(1);
SAM::len[0]=-1;
solve(1,SAM::tot,0,1,m+1);
for(int i=1;i<=SAM::tot;++i)c[res[i]]+=SAM::len[i]-SAM::len[SAM::pre[i]],umax(mx[res[i]],SAM::len[i]);
for(int i=1;i<=m;++i)c[i]+=c[i-1],umax(mx[i],mx[i-1]),printf("%lld %lld\n",c[i],mx[i]);
return 0;
}
```