自动搬运

查看原文

来自洛谷，原作者为

	Nemlit 自能生羽翼，何必仰云梯。

搬运于2025-08-24 21:34:49，当前版本为作者最后更新于2019-08-28 12:41:56，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

原题意：有多少个串的$lcp(i, j) >= r$(其中r为1~n中每一个数)

我们先不管第二问，只看第一问

第一次转化

首先不难发现一个非常好的性质：对于一个r相似的两杯酒，他们肯定也是r-1相似，r-2相似……

于是，我们考录倒序枚举，於是问题转化成了：有多少个串的$lcp(i, j) == r$(其中r为1~n中每一个数)

第二次转化

看到lcp，我们不难想到后缀数组，$lcp(i, j) == r$ 又等价于$min(he[i + 1], he[i + 2], ……, he[j])$

于是我们把问题重新考虑，就转化成了：求出he数组，然后问有多少个数对，满足$i - j$的he的最小值恰好等于r

第三次转化

我们把he数组降序排一遍序，然后按照顺序插入

然后我们可以把问题理解成：对于每次插入，我可以连接连续两堆数，然后这两堆数中每一个数值都比r大，所以我们可以把第一堆数的个数和第二堆数的个数相乘，得到的就是这两堆数对答案的贡献

举个例子：

假设我现在的数列长这样（还未被插入的数（即比r小的数）为*）：$5\ 4\ *\ 4\ 5\ 6\ 7\ *\ *\ 4\ *\ 8$

然后我现在要在第三个位置插入一个3

不难发现，一共有$(2 + 1) * (4 + 1) - 1 = 14$种方案（+1是因为3本身也可以算进来， -1是因为$[3, 3]$不能算）

所以这个合并的过程类似于并查集，我们只需要维护一个size就可以求出第一问了

对于第二问，我们只需要维护一个最小值和最大值即可（维护最小值是因为有复数）

代码如下

#include<bits/stdc++.h>
using namespace std;
#define il inline
#define re register
#define debug printf("Now is Line : %d\n",__LINE__)
#define file(a) freopen(#a".in","r",stdin);freopen(#a".out","w",stdout)
#define int long long
#define inf 1234567890000000000
il int read() {
    re int x = 0, f = 1; re char c = getchar();
    while(c < '0' || c > '9') { if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - 48, c = getchar();
    return x * f;
}
#define rep(i, s, t) for(re int i = s; i <= t; ++ i)
#define drep(i, s, t) for(re int i = t; i >= s; -- i)
#define _ 300005
int n, m, sa[_], rk[_], tp[_], a[_], he[_], val[_], ans1[_], ans2[_], now, num, b[_];
char c[_];
vector<int> q[_];
struct set {int size, mi, ma, fa;}e[_];
il void Qsort() {
	rep(i, 1, m) a[i] = 0;
	rep(i, 1, n) ++ a[rk[i]];
	rep(i, 1, m) a[i] += a[i - 1];
	drep(i, 1, n) sa[a[rk[tp[i]]] --] = tp[i];
}
il void get_sort() {
	for(re int w = 1, p = 0; p < n && w <= n; m = p, p = 0, w <<= 1) {
		rep(i, n - w + 1, n) tp[++ p] = i;
		rep(i, 1, n) if(sa[i] > w) tp[++ p] = sa[i] - w;
		Qsort(), swap(tp, rk), rk[sa[1]] = p = 1;
		rep(i, 2, n) rk[sa[i]] = (tp[sa[i]] == tp[sa[i - 1]] && tp[sa[i] + w] == tp[sa[i - 1] + w]) ? p : ++ p;
	}
}
il void get_height() {
	int j = 0;
	rep(i, 1, n) {
		if(rk[i] == 1) continue;
		if(j) -- j;
		while(c[i + j] == c[sa[rk[i] - 1] + j]) ++ j;
		he[rk[i]] = j;
	}
}
il int find(int x) {
	while(x != e[x].fa) x = e[x].fa = e[e[x].fa].fa;
	return x;
}
il void merge(int a, int b) {
	int x = find(a), y = find(b);
	now += e[x].size * e[y].size, num = max(num, max(e[x].ma * e[y].ma, e[x].mi * e[y].mi));
	e[y].fa = x, e[x].size += e[y].size, e[x].ma = max(e[x].ma, e[y].ma), e[x].mi = min(e[x].mi, e[y].mi);
}
signed main() {
	n = read(), scanf("%s", c + 1), m = 26, num = -inf;
	rep(i, 1, n) b[i] = read(), rk[i] = c[i] - 'a' + 1, tp[i] = i;
	Qsort(), get_sort(), get_height();
	rep(i, 1, n) e[i].fa = i, e[i].size = 1, e[i].ma = e[i].mi = b[sa[i]], q[he[i]].push_back(i);
	drep(i, 0, n - 1) {
		int pax = q[i].size();
		rep(j, 0, pax - 1) merge(q[i][j], q[i][j] - 1);
		if(now) ans1[i] = now, ans2[i] = num;
	}
	rep(i, 0, n - 1) printf("%lld %lld\n", ans1[i], ans2[i]);
	return 0;
}