【luogu P6629】字符串（Runs）（树状数组）

字符串

题目链接：luogu P6629

题目大意

给你一个字符串，然后多次询问每次问你一个子串，问你这个串有多少个本质不同的平方子串。

思路

md 到底是什么阴间东西。

本原平方串

其实这个东西就是本原平方串。
首先一些简单的性质：$a$ 是 $b$ 前缀，$a$ 有 $p$ 的循环节，$b$ 有 $q$ 的，$p|q$，$q<|a|$，那 $b$ 也有 $p$ 的循环节。

然后如果 $s$ 是 $t$ 的前缀（都非空），而且 $2|s|>t$，那 $|t|-|s|$ 是 $s$ 的周期。
这个画个图不难理解，就是看多出来那一部分。

然后证一些东西：

1. 如果 $u,v,w$ 非空且 $uu$ 是 $vv$ 前缀，$vv$ 是 $ww$ 前缀，$uu$ 是本原平方串，那 $|u|+|v|<|w|$

首先如果 $|w|⩾2|v|$ 显然成立，所以只看 $|w|<2|v|$
然后可以得到 $|w|-|v|$ 是 $v$ 周期。
然后设 $|u|+|v|>|w|$（反证），即 $|w|-|v|<|u|$，所以 $|w|-|v|$ 也是 $u$ 周期。
然后分类 $2|u|⩽|v|$，那 $uu$ 是 $v$ 前缀，就有 $|w|-|v|$ 也是 $uu$ 周期。
但是 $|w|-|v|<|u|$，就更小了，所以不行。
如果 $2|u|>|v|$，我们就有 $|v|-|u|$ 是 $u$ 的周期。

然后你看看：$v$ 周期有 $|w|-|v|,|u|$（$|u|$ 这个你画个图看看就会发现了）
然后再把 $w$ 表示成 $v{s}_1$，$u=s_1{s}_2$，$v=u{s}_3$，$w=s_1{s}_2{s}_3{s}_1$
然后你把 $uu,vv,ww$ 列出来，会发现 $|s_2|$ 是 $s_2{s}_3$ 周期，然后还会有周期 $|v|-|u|=|s_3|$。
（别问，问就是看不懂照抄）

然后你 $\mathrm{WPL}$ 一下，就会 $s_2{s}_3$ 周期有 $\gcd (s_2,s_3)$。
然后你用最上面的性质也会有这也是 $u$ 的前缀。
然后 $u$ 又有周期 $|w|-|r|=|s_1|$，然后又 $\mathrm{WPL}$ 就有周期 $\gcd (s_1,s_2,s_3)$
那这个肯定是小于一半的，所以就矛盾了。

（别骂了看不懂硬胡的）

---

然后根据上面的性质有一些结论：

1. 一个串的本原平方串的个数不超过 $O(|s|\log |s|)$

考虑开头位置，如果有两个 $uu,vv$，下一个至少为上一个长度的两倍（好像说最垃是斐波那契，不知道为啥），然后是 $\log$ 级别的。

2. 一个串的本质不同的本原平方串个数是 $O(n)$ 的

考虑开头位置，如果有三个 $uu,vv,ww$，就会有 $|w|⩾|u|+|v|⩾2|u|$，所以 $uu$ 在 $w$ 开头就出现，肯定是在别的地方之前出现过，所以每个位置开头至多两个不同的。

---

然后我们不难看出，一个本原平方串一定是属于一个 $\mathrm{run}$ 的一部分，就本原平方串一定是 $\mathrm{run}$，然后还可以扩展。

那我们找本原平方串就可以从这里下手：
我们枚举 $\mathrm{run}$ 找对于的本原平方串，那 $\mathrm{run}r=(l,r,p)$ 中 $[l,r]$ 里面任意一个长度为 $2p$ 的子串都是本原平方串，然后找的复杂度是 $\sum _{r=(l,r,p)\in \mathrm{Runs}(\mathrm{s})}(r-l+1-2p+1)$，然后得到是 $O(n\log n)$ 级别。

找本质不同的

好的真正阴间的部分来了。
（毕竟前面可以记结论）
（好吧是我菜）

我们考虑把一个本原平方串按左右坐标放在二维平面上，那每次询问就是二维数点。
那考虑到问题为什么难求，因为可能有重复的，考虑容斥掉（其实也没有什么好容斥的，就是你构造一种方法使得减剩一个）
那就是你考虑到相同的有两种可能：同一个 $\mathrm{run}$ 里面的，不同的 $\mathrm{run}$ 之间的。

先看同一个 $\mathrm{run}$ 里面的，那发现一定是形成一个斜率 $45°$ 的线。
那就考虑从第二个点开始在它 $y$ 轴的位置上一个点 $x$ 轴的位置放一个 $-1$，那这样如果碰到了第二个必然也会碰到这个消去的。
然后你发现这个消去的也是斜线。

然后考虑不同的 $\mathrm{run}$ 之间的，就直接看哪个斜线是不是同一个（可以用 $\mathrm{map}$ 判），然后如果是就前面的最后一个跟后面的第一个之间像前面的方法一样放点，这个直接单独放即可。
然后至于斜线怎么二维偏序数点就拆成两个射线，然后神笔维护一下即可。
（至于维护可以看代码/fad）

代码

#include<map>
#include<cstdio>
#include<vector>
#include<algorithm>
#define ll long long

using namespace std;

const int N = 2e5 + 1000;
int n, q, ans[N], ly[N], sta[N], m, fn;
char s[N];
struct node {
    
	int l, r, id;
}qs[N];
struct RUNS {
    
	int l, r, p;
}runs[N];

struct HASH {
    
	const int di1 = 13331, di2 = 131;
	const int mo1 = 1e9 + 7, mo2 = 1e9 + 9;
	
	ll mi1[N], hash1[N], mi2[N], hash2[N];
	
	void start() {
    
		mi1[0] = mi2[0] = 1;
		for (int i = 1; i <= n; i++) {
    
			mi1[i] = mi1[i - 1] * di1 % mo1; mi2[i] = mi2[i - 1] * di2 % mo2;
			hash1[i] = (hash1[i - 1] * di1 + s[i] - 'a' + 1) % mo1;
			hash2[i] = (hash2[i - 1] * di2 + s[i] - 'a' + 1) % mo2;
		}
	}
	
	pair <int, int> get(int l, int r) {
    
		return make_pair((hash1[r] - hash1[l - 1] * mi1[r - l + 1] % mo1 + mo1) % mo1, (hash2[r] - hash2[l - 1] * mi2[r - l + 1] % mo2 + mo2) % mo2);
	}
}H;
map <pair <int, int>, int> mp;

int getl(int x, int y) {
    
	int l = 1, r = min(x, y), re = 0;
	while (l <= r) {
    
		int mid = (l + r) >> 1;
		if (H.get(x - mid + 1, x) == H.get(y - mid + 1, y)) re = mid, l = mid + 1;
			else r = mid - 1;
	}
	return re;
}

int getr(int x, int y) {
    
	int l = 1, r = min(n - x + 1, n - y + 1), re = 0;
	while (l <= r) {
    
		int mid = (l + r) >> 1;
		if (H.get(x, x + mid - 1) == H.get(y, y + mid - 1)) re = mid, l = mid + 1;
			else r = mid - 1;
	}
	return re;
}

bool cmpS(int x, int y) {
    
	int pl = getr(x, y);
	return s[x + pl] < s[y + pl];
}

void Lyndon(bool op) {
    
	ly[n] = n;
	sta[0] = 0; sta[++sta[0]] = n + 1; sta[++sta[0]] = n;
	for (int i = n - 1; i >= 1; i--) {
    
		while (sta[0] > 1 && cmpS(i, sta[sta[0]]) == op) sta[0]--;
		sta[++sta[0]] = i;
		ly[i] = sta[sta[0] - 1] - 1;
	}
}

void slove(int x, int y) {
    
	int l = getl(x, y), r = getr(x, y);
	if (l + r >= y - x + 1) runs[++m] = (RUNS){
    x - l + 1, y + r - 1, y - x};
}

bool cmp_run(RUNS x, RUNS y) {
    
	if (x.l != y.l) return x.l < y.l;
	if (x.r != y.r) return x.r < y.r;
	return x.p < y.p;
}

void get_runs() {
    
	for (int op = 0; op <= 1; op++) {
    
		Lyndon(op);
		for (int i = 1; i < n; i++) {
    
			slove(i, ly[i] + 1);
		}
	}
	sort(runs + 1, runs + m + 1, cmp_run);
}

void Init() {
    
	H.start();
	get_runs();
	int tmp = m; m = 0;
	for (int i = 1; i <= tmp; i++)
		if (runs[i].l != runs[i - 1].l || runs[i].r != runs[i - 1].r) {
    
			runs[++m] = runs[i];
		}
}

bool cmp_qr(node x, node y) {
    
	return x.r < y.r;
}

struct SZSZ {
    
	ll f[N], sum;
	
	void add(int x, int y) {
    
		sum += y;
		for (; x <= n + n; x += x & (-x)) f[x] += y;
	}
	
	ll ask(int x) {
    
		ll re = 0;
		for (; x; x -= x & (-x)) re += f[x];
		return re;
	}
}T;

vector <pair<int, int> > ed[N];
vector <RUNS> run[N];

void slove() {
    
	sort(qs + 1, qs + q + 1, cmp_qr);
	for (int x = 1; x <= m; x++) {
    
		run[runs[x].r].push_back(runs[x]);
		int l = runs[x].l, r = runs[x].r, p = runs[x].p;
		for (int i = l + 2 * p - 1; i <= r; i++)
			ed[i].push_back(make_pair(l, 2 * p));
	}
	int now = 1;
	for (int i = 1; i <= n; i++) {
    
		for (int j = 0; j < ed[i].size(); j++) {
     int l = ed[i][j].first, p = ed[i][j].second;
			int pl = i - ((i - l + 1) / p * p) + 1;
			pair <int, int> now = H.get(pl, i);
			if (mp[now]) {
    
				T.add(mp[now], -1);
				mp[now] = 0;
			}
		}
		while (now <= q && qs[now].r <= i) {
    
			ans[qs[now].id] = T.sum - T.ask(qs[now].l - 1);
			for (int j = 0; j < ed[i].size(); j++) {
    
				int l = max(qs[now].l, ed[i][j].first);
				int t = (qs[now].r - l + 1) / ed[i][j].second;
				int ql = qs[now].r - ed[i][j].second / 2 + 1;
				if (t) {
    
					int lef = max(ql, t * ed[i][j].second + l - 1);
					ans[qs[now].id] += (qs[now].r - lef + 1) * t;
					if (lef > ql) ans[qs[now].id] += (lef - ql) * (t - 1);
				}
			}
			now++;
		}
		for (int j = 0; j < run[i].size(); j++) {
     RUNS p = run[i][j];
			for (int r = p.r - p.p + 1; r <= p.r; r++)
				for (int l = r - 2 * p.p + 1; l >= p.l; l -= 2 * p.p) {
    
					pair <int, int> now = H.get(l, r);
					mp[now] = l; T.add(l, 1);
				}
		}
	}
}

int main() {
    
	scanf("%d %d", &n, &q);
	scanf("%s", s + 1);
	for (int i = 1; i <= q; i++) {
    
		scanf("%d %d", &qs[i].l, &qs[i].r); qs[i].id = i;
	}
	
	Init();
	slove();
	
	for (int i = 1; i <= q; i++) printf("%d\n", ans[i]);
	
	return 0;
}