题解 P6292 【区间本质不同子串个数】

灵梦

2020-04-13 20:16:15

Solution

为了求解这个问题,我们先考虑「静态区间不同元素种类数」的经典问题。下面是这个问题的一种常见解法: >对于一个固定的右端点 $i$,贪心地只考虑 $i$ 之前每种元素最后出现的位置。按下标从左到右扫描线,用一棵线段树维护每个位置是否在前缀 $i$ 种最后一次出现。加入第 $i$ 个元素时,在线段树中把当前位置 $+1$,把上一个相同元素的位置 $-1$。询问直接区间查询即可。 对于这道题我们采用相同的思路。把本质相同的子串看作同一种元素,那么插入位置 $i$ 时应该在线段树中加入所有以 $i$ 结尾的子串的贡献。子串是有长度的,但我们只需维护左端点即可。那么「在线段树中把当前位置 $+1$」可以直接一次区间修改来完成,而把「上一个相同元素的位置 $-1$」目前来看不太好做,因为我们还不知道每个子串上一次出现的位置。 为了解决这个问题,我们对原串建立后缀自动机。那么以 $i$ 结尾的子串就是前缀 $i$ 对应的节点在 $parent$ 树上的所有祖先节点。由同一个状态表示的子串,它们「上一次出现的位置」的右端点是相同的,而左端点是连续的一段,所以我们可以通过暴力跳 $parent$ 树上祖先并在线段树上区间修改来达到目的。同时还需要把这条链上的节点都染成 $i$ 颜色,表示把这些子串最后一次出现的位置修改为 $i$。但这样做的复杂度显然是不对的,需要寻求更优的方法。 发现颜色相同的节点的节点会连成一段,我们可以将它们一起处理。由于只有「将某一点到根节点的颜色染成一种没有出现过的颜色」这一种操作,所有需要处理的链上的总颜色数实际上是 $O(n\log n)$ 的。原因是染色操作其实对应着 LCT 的 $\text{Access}$ 操作,可以套用其复杂度证明方法。所以在实现时我们也可以直接使用 LCT 来维护,因为一条实链上的颜色一定都是相同的,直接模拟 $\text{Access}$ 的过程即可。 复杂度是 LCT 的复杂度加上线段树的复杂度,为 $O(n\log^2n+q\log n)$。如果要求在线就上可持久化吧。 下面是两道选做的题目: - [树点涂色](https://www.luogu.com.cn/problem/P3703) 这道题对最后一段的理解会有很大启发; - [事情的相似度](https://loj.ac/problem/6041) 一道可以用类似 Trick 解决的题目。 然后是这道题代码: ```cpp #include <cstdio> #include <cstring> #include <algorithm> using namespace std; typedef long long ll; const int MAXN=220000; int n, q; char s[MAXN]; namespace SAM { struct Node { int nxt[26], fail, len; } st[MAXN]; int m, root, lst; int pos[MAXN]; inline int newNode(int l) { m++; memset(st[m].nxt, 0, sizeof st[m].nxt); st[m].fail=0, st[m].len=l; return m; } void extend(int x) { int p=lst, np=newNode(st[p].len+1); lst=np; while (p&&!st[p].nxt[x]) st[p].nxt[x]=np, p=st[p].fail; if (!p) { st[np].fail=root; return; } int q=st[p].nxt[x]; if (st[q].len==st[p].len+1) { st[np].fail=q; return; } int nq=newNode(st[p].len+1); memcpy(st[nq].nxt, st[q].nxt, sizeof st[q].nxt); st[nq].fail=st[q].fail; st[np].fail=st[q].fail=nq; while (p&&st[p].nxt[x]==q) st[p].nxt[x]=nq, p=st[p].fail; } void build() { m=0; lst=root=newNode(0); for (int i=1; i<=n; i++) extend(s[i]-'a'), pos[i]=lst; } } namespace SGT { struct Node { int l, r; ll sum; int add; } tr[4*MAXN]; #define lc (o<<1) #define rc (o<<1|1) inline void pushup(int o) { tr[o].sum=tr[lc].sum+tr[rc].sum; } inline void add(int o, int k) { tr[o].sum+=1ll*k*(tr[o].r-tr[o].l+1); tr[o].add+=k; } inline void pushdown(int o) { if (tr[o].add) { add(lc, tr[o].add); add(rc, tr[o].add); tr[o].add=0; } } void build(int o, int l, int r) { tr[o].l=l, tr[o].r=r; tr[o].sum=tr[o].add=0; if (l==r) return; int mid=l+r>>1; build(lc, l, mid), build(rc, mid+1, r); } void modify(int o, int l, int r, int k) { if (tr[o].l>r||tr[o].r<l) return; if (l<=tr[o].l&&tr[o].r<=r) { add(o, k); return; } pushdown(o); modify(lc, l, r, k), modify(rc, l, r, k); pushup(o); } ll query(int o, int l, int r) { if (tr[o].l>r||tr[o].r<l) return 0; if (l<=tr[o].l&&tr[o].r<=r) return tr[o].sum; pushdown(o); return query(lc, l, r)+query(rc, l, r); } #undef lc #undef rc } namespace LCT { struct Node { int val, cov; int fa, c[2]; } tr[MAXN]; #define lc tr[x].c[0] #define rc tr[x].c[1] #define par tr[x].fa inline bool isroot(int x) { return tr[par].c[0]!=x&&tr[par].c[1]!=x; } inline void cover(int x, int k) { tr[x].val=tr[x].cov=k; } inline void pushdown(int x) { if (tr[x].cov) { if (lc) cover(lc, tr[x].cov); if (rc) cover(rc, tr[x].cov); tr[x].cov=0; } } inline bool getlr(int x) { return tr[par].c[1]==x; } inline void rotate(int x) { int y=par, z=tr[y].fa; bool k=getlr(x); int w=tr[x].c[!k]; if (!isroot(y)) tr[z].c[getlr(y)]=x; par=z; tr[y].c[k]=w; if (w) tr[w].fa=y; tr[x].c[!k]=y; tr[y].fa=x; } void pushall(int x) { if (!isroot(x)) pushall(par); pushdown(x); } void splay(int x) { pushall(x); while (!isroot(x)) { if (!isroot(par)) rotate(getlr(x)^getlr(par)?x:par); rotate(x); } } void access(int x, int p) { int y=0; while (x) { splay(x); if (int k=tr[x].val) SGT::modify(1, k-SAM::st[x].len+1, k-SAM::st[par].len, -1); rc=y, y=x, x=par; } cover(y, p); SGT::modify(1, 1, p, 1); } void build() { for (int i=2; i<=SAM::m; i++) { tr[i].val=tr[i].cov=0; tr[i].c[0]=tr[i].c[1]=0; tr[i].fa=SAM::st[i].fail; } } #undef lc #undef rc #undef par } struct Query { int l, r, id; bool operator < (const Query& rhs) const { return r<rhs.r; } } a[MAXN]; ll ans[MAXN]; int main() { // freopen("P6292.in", "r", stdin); // freopen("P6292.out", "w", stdout); scanf("%s", s+1), n=strlen(s+1); SAM::build(); LCT::build(); scanf("%d", &q); for (int i=1; i<=q; i++) { scanf("%d%d", &a[i].l, &a[i].r); a[i].id=i; } sort(a+1, a+q+1); SGT::build(1, 1, n); for (int i=1, j=1; i<=q; i++) { while (j<=a[i].r) LCT::access(SAM::pos[j], j), j++; ans[a[i].id]=SGT::query(1, a[i].l, a[i].r); } for (int i=1; i<=q; i++) printf("%lld\n", ans[i]); return 0; } ```