题目大意：给定一个长度为$n$的字符串$s$，求有多少个无序字符串二元组$(x,y)$满足：$x,y$是$s$的字串，且$x$不是$y$的字串，$y$不是$x$的字串

题解：发现满足$x,y$是$s$字串的二元组很好求，于是转换为求有多少个无序二元组$(x,y)$满足$x$是$y$的字串或$y$是$x$的字串。

对$s$建后缀自动机，对于每一个一个本质不同的子串，计算它包含的本质不同的子串个数之和就是答案。一个子串可能出现多次，任意选取一次就可以计算答案。而对于自动机上的一个节点，它产生的贡献为$s_{min,r},s_{min+1,r},\dots,s_{max,r}$中的本质不同的字串。维护一个数组$p$，令$p_i$表示从$i$开始，到现在$r$的本质不同子串的个数（位置不同的相同子串只记录最后一次），可以对每一个本质不同的字串，在它最后一次出现的左端点$+1$。

每插入一个字符，就算一次新增的自动机节点的贡献，当$r$变大的时候，在$parent$树上从新增节点到根的最后出现位置都会更改。相当于把$parent$树上这一条链染色。

可以用$LCT$，使用$access$操作，每一条重链上的颜色都相等，改变颜色的时候就直接染色，然后改变$p$数组，因为$parent$树上左端点是连续的，所以原来的每条重链可以直接线段树修改。复杂度可以用$LCT$来证，是$O(n\log_2n)$的（可能假了）。

发现我们要求的是后缀和后的区间和，可以在线段树上区间加等差数列。发现$SAM$上节点可能分裂，这里查询答案的时候用原来的大小，查询这个节点原来的$[R-max+1,R-min+1]$。累加就是答案

卡点：写线段树的时候，放标记的时候修改当前节点权值错误，多乘了一个公差；因为调试的时候我枚举所有点放标记答案对了（我也不知道为什么）？？？？导致我后期调试方向出错，白班浪费了$3h+$，还是$little\_gift$一眼指出错误之处

C++ Code：

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <iostream>

const int maxn = 2e5 + 10;

int n, pos[maxn];

char s[maxn];

int nxt[maxn][26], fail[maxn], R[maxn], mnR[maxn];

int idx = 1, lst = 1;

namespace SgT {

	const int N = maxn << 2;

	long long V[N], tg[N], tg2[N];

	inline void addtg(int rt, int len, long long v) {

		V[rt] += v * len;

		tg[rt] += v;

	}

	inline void addtg2(int rt, int len, long long l, long long v) {

		V[rt] += l * len + (len * v) * (len + 1) / 2;

		tg[rt] += l;

		tg2[rt] += v;

	}

	inline void pushdown(int rt, int len) {

		const int L = rt << 1, R = rt << 1 | 1;

		if (tg[rt]) {

			addtg(L, len + 1 >> 1, tg[rt]);

			addtg(R, len >> 1, tg[rt]);

		}

		if (tg2[rt]) {

			addtg2(L, len + 1 >> 1, tg2[rt] * (len >> 1), tg2[rt]);

			addtg2(R, len >> 1, 0, tg2[rt]);

		}

		tg[rt] = tg2[rt] = 0;

	}

	inline void update(int rt) {

		V[rt] = V[rt << 1] + V[rt << 1 | 1];

	}

	void modify(int rt, int l, int r, int L, int R, long long v) {

		if (L <= l && R >= r) {

			addtg(rt, r - l + 1, v);

			return ;

		}

		pushdown(rt, r - l + 1);

		const int mid = l + r >> 1;

		if (L <= mid) modify(rt << 1, l, mid, L, R, v);

		if (R > mid) modify(rt << 1 | 1, mid + 1, r, L, R, v);

		update(rt);

	}

	void modify2(int rt, int l, int r, int L, int R, long long v) {

		if (L <= l && R >= r) {

			const int ll = R - r, len = r - l + 1;

			addtg2(rt, r - l + 1, ll * v, v); // ll + v, ll + 2v, ll + 3v ...

			return ;

		}

		pushdown(rt, r - l + 1);

		const int mid = l + r >> 1;

		if (L <= mid) modify2(rt << 1, l, mid, L, R, v);

		if (R > mid) modify2(rt << 1 | 1, mid + 1, r, L, R, v);

		update(rt);

	}

	void modify(int l, int r, int v) {

		const int len = r - l + 1;

		if (l > 1) modify(1, 1, n, 1, l - 1, len * v);

		if (l > 0 && r >= 1 && l <= r) modify2(1, 1, n, l, r, v);

	}

	long long query(int rt, int l, int r, int L, int R) {

		if (L <= l && R >= r) return V[rt];

		pushdown(rt, r - l + 1);

		const int mid = l + r >> 1;

		long long ans = 0;

		if (L <= mid) ans = query(rt << 1, l, mid, L, R);

		if (R > mid) ans += query(rt << 1 | 1, mid + 1, r, L, R);

		return ans;

	}

}

int fa[maxn], son[maxn][2], V[maxn];

#define lc(rt) son[rt][0]

#define rc(rt) son[rt][1]

inline int get(int rt, int tg = 1) { return son[fa[rt]][tg] == rt; }

inline bool isroot(int rt) { return !(get(rt, 0) || get(rt)); }

inline void pushdown(int rt) { V[lc(rt)] = V[rc(rt)] = V[rt]; }

inline void rotate(int x) {

	int y = fa[x], z = fa[y], b = get(x);

	if (!isroot(y)) son[z][get(y)] = x;

	fa[son[y][b] = son[x][!b]] = y, son[x][!b] = y;

	fa[y] = x, fa[x] = z;

}

inline void splay(int x) {

	static int S[maxn], top;

	S[top = 1] = x;

	for (int y = x; !isroot(y); S[++top] = y = fa[y]) ;

	for (; top; --top) pushdown(S[top]);

	for (; !isroot(x); rotate(x)) if (!isroot(fa[x]))

		get(x) ^ get(fa[x]) ? rotate(x) : rotate(fa[x]);

}

inline void cover(int x, int v) { V[x] = v; }

inline void access(int x, int v) {

	int t = 0;

	while (x) {

		splay(x), rc(x) = t;

		SgT::modify(V[x] - R[x] + 1, V[x] - R[fa[x]], -1);

		t = x, x = fa[x];

	}

	splay(1), cover(1, v);

	SgT::modify(1, v, 1);

}

long long num, ans;

int append(int ch, int id) {

	static int p, np, q, nq; p = lst, np = lst = ++idx, R[np] = R[p] + 1;

	for (; p && !nxt[p][ch]; p = fail[p]) nxt[p][ch] = np;

	if (!p) fail[np] = 1;

	else {

		q = nxt[p][ch];

		if (R[p] + 1 == R[q]) fail[np] = q;

		else {

			R[nq = ++idx] = R[p] + 1;

			memcpy(nxt[nq], nxt[q], 26 << 2);

			for (; nxt[p][ch] == q; p = fail[p]) nxt[p][ch] = nq;

			fail[nq] = fail[q], fail[q] = fail[np] = nq;

		}

	}

	num += R[np] - R[fail[np]];

	mnR[np] = R[fail[np]] + 1;

	return np;

}

int main() {

	std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0);

	std::cin >> s + 1; n = strlen(s + 1);

	for (int i = 1; i <= n; ++i)

		pos[i] = append(s[i] - 'a', i);

	for (int i = 1; i <= idx; ++i) fa[i] = fail[i];

	for (int i = 1; i <= n; ++i) {

		access(pos[i], i);

		ans += SgT::query(1, 1, n, i - R[pos[i]] + 1, i - mnR[pos[i]] + 1);

	}

	std::cout << (static_cast<unsigned long long> (num + 1) * num - 2 * ans) / 2 << '\n';

	return 0;

}

　　

最新文章

  1. Excel Sheet Column Title
  2. 轻型的ORM类Dapper
  3. 选择流程—— switch if else结构
  4. Ghost博客安装
  5. 实习日记：图像检索算法 LSH 的总结与分析(matlab)
  6. Swift使用FMDB操作SQLite
  7. 苹果应用商店DNS修改加快下载速度
  8. 送给和我一样曾经浮躁过的PHP程序猿
  9. [SAP ABAP开发技术总结]将文件存储到数据库表中，并可发送邮件
  10. 利用Jquery处理跨域请求
  11. Linux系统故障处理案例(一)
  12. 多线程+fork 引发的bug查找
  13. Html 定位position
  14. angular 4 实现的tab栏切换
  15. Docker下安装GitLab
  16. 最优装载—dp
  17. 将EditPad Lite 加入鼠标右键
  18. Mysql 一些基本的小东西
  19. Linux下初次使用github
  20. beta 答辩总结

热门文章

  1. Min25筛
  2. 微信小程序地图组件
  3. idea 导入 eclipse java ee 项目，并使用 tomcat 7 部署运行
  4. 检测算法简介及其原理——fast R-CNN，faster R-CNN，YOLO，SSD，YOLOv2，YOLOv3
  5. 简书 markdown 代码高亮标记
  6. [E2E_L7 51CTO]进一步解析OpenVINO提供的例子并且独立出来(win+vs)
  7. linux设置sudo不要密码
  8. （7）Flask微电影之会员中心页面搭建
  9. openresty开发系列38--通过Lua+Redis 实现动态封禁IP
  10. Hadoop，Spark,Flink 相关KB