题目要求
后面要减去的部分是两两后缀的
,那么做了后缀数组之后就是
后面其实就是
里面所有区间的最小值加起来再乘
.
这样我们考虑一个值可以作为最小值能够拓展的最左端和最右端,就可以算出这个值对答案的贡献.这个就单调栈就行了.具体见代码.
…mdzz又双叒叕缀写错后缀(chuo)数组了.
CODE
#include
using namespace std;
typedef long long LL;
const int MAXN = 5e5+5;
char s[MAXN];
int n, x[MAXN], y[MAXN], c[MAXN], sa[MAXN], rk[MAXN], ht[MAXN];
inline void Get_Sa(int m) {
for(int i = 1; i = 1; --i) sa[c[x[i]]--] = i;
for(int k = 1; k k) y[++p] = sa[i]-k;
for(int i = 1; i = 1; --i) sa[c[x[y[i]]]--] = y[i];
swap(x, y);
x[sa[1]] = p = 1;
for(int i = 2; i 1) {
j = sa[rk[i]-1]; k = k ? k-1 : 0;
while(i+k ht[i]) R[st[top--]] = i;
L[i] = st[top]; st[++top] = i;
}
while(top) R[st[top--]] = n+1;
LL ans = 1ll * (n-1) * n * (n+1) / 2;
for(int i = 2; i 服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net
机房租用，北京机房租用，IDC机房托管， http://www.e1idc.net
