题意
给定一个字符串S和一个权值函数a(i)，求对于0≤r<n，长度为r的相等子串对个数和相等子串对开头两位置权值乘积的最大值。
My Idea
首先看到标签知道是后缀数组，那么就先搞出height数组。
考虑一个naive的方法：从大到小枚举r，每次只考虑两位置最大为r匹配(而不考虑5匹配也能是3匹配的)。我们建一棵height的线段树。对于每一次，我们先找出height中的每一个height[p] = r的位置，然后向前后二分并用线段树判断，找到最大的使height[p]为最小值的区间，然后左右乘一乘就算出来了。
然而复杂度是O(nlg2n)的，300000的时候显然会超时(当然松爷肯定能卡过去)。
正解
居然是并查集……
最后一步变成边计算边合并，维护一个带权并查集就好了。神思路…… 如果用DA就是O(nlgn+nα(n))，如果用DC3就是O(nα(n))了(不过蒟蒻显然不会)..Code
#includeusing namespace std;const int maxn = 300005;struct S_A { int A[maxn], SA[maxn], C[maxn], rank[maxn], h[maxn], n; struct p { int x[2], id; p(){} p(int a, int b, int c):id(c) {x[0] = a, x[1] = b;} } RE[maxn], RT[maxn]; S_A():n(0){} void radix_sort() { for (int y = 1; y >= 0; y--) { memset(C, 0, sizeof C); register int i; for (i = 1; i <= n; i++) C[RE[i].x[y]]++; for (i = 1; i < maxn; i++) C[i] += C[i-1]; for (i = n; i >= 1; i--) RT[C[RE[i].x[y]]--] = RE[i]; for (i = 1; i <= n; i++) RE[i] = RT[i]; } for (int i = 1; i <= n; i++) { rank[RE[i].id] = rank[RE[i-1].id]; if (RE[i].x[1] != RE[i-1].x[1] || RE[i].x[0] != RE[i-1].x[0]) rank[RE[i].id]++; } } void build_sa() { for (int i = 1; i <= n; i++) RE[i] = p(A[i], 0, i); radix_sort(); for (int k = 1; k < n; k <<= 1) { for (int i = 1; i <= n; i++) RE[i] = p(rank[i], i+k<=n?rank[i+k]:0, i); radix_sort(); } for (int i = 1; i <= n; i++) SA[rank[i]] = i; } void build_height() { for (int ht = 0, i = 1; i <= n; i++) { if (rank[i] == 1) ht = 0; else { int k = SA[rank[i]-1]; if (--ht < 0) ht = 0; while (A[i+ht] == A[k+ht]) ht++; } h[rank[i]] = ht; } } void init(const char *str) { for (; *str != '\0'; ++str) A[++n] = *str-'a'+1; build_sa(); build_height(); }}SA;char str[maxn];long long a[maxn];long long ansx[maxn], ansy[maxn];struct p { int to, next;} edge[maxn];int head[maxn], top = 0;void push(int i, int j) { edge[++top].to = j; edge[top].next = head[i]; head[i] = top;}int fa[maxn];long long siz[maxn], mx[maxn], mn[maxn];long long cnt = 0, maxd = LONG_LONG_MIN;int findp(int i){ return fa[i]?fa[i]=findp(fa[i]):i; }void link(int i, int j) { //cout << i << " " << j << endl; if (!i || !j) return; int p = findp(i), q = findp(j); if (p != q) { maxd = max(maxd, max(mn[p]*mn[q], max(mx[p]*mx[q], max(mn[p]*mx[q], mx[p]*mn[q])))); cnt += siz[p]*siz[q]; fa[p] = q; siz[q] += siz[p]; mx[q] = max(mx[q], mx[p]); mn[q] = min(mn[q], mn[p]); }}int main() { int n; scanf("%d", &n); scanf("%s", str); for (int i = 1; i <= n; i++) scanf("%lld", &a[i]), siz[i] = 1, fa[i] = 0; SA.init(str); for (int i = 1; i <= n; i++) mn[i] = mx[i] = a[SA.SA[i]]; for (int i = 1; i <= n; i++) push(SA.h[i], i); for (int i = n-1; i >= 0; i--) { for (int j = head[i]; j; j = edge[j].next) { int to = edge[j].to, p = findp(to), q = findp(to-1); maxd = max(maxd, max(mn[p]*mn[q], max(mx[p]*mx[q], max(mn[p]*mx[q], mx[p]*mn[q])))); } for (int j = head[i]; j; j = edge[j].next) { int to = edge[j].to; link(to-1, to); } ansx[i] = cnt; ansy[i] = maxd; if (ansy[i] == LONG_LONG_MIN) ansy[i] = 0; } for (int i = 0; i < n; i++) printf("%lld %lld\n", ansx[i], ansy[i]); return 0;}