BZOJ 3238 AHOI 2013 差異 後綴數組+單調棧
題目大意：
<喎?http://www.Bkjia.com/kf/ware/vc/" target="_blank" class="keylink">vcD4KPHA+y7zCt6O60ru/tLj31ta689e6xMe+zcrHuvPXusr91+nDu8XcwcuhozwvcD4KPHA+x/Oz9nNho6xoZWlnaHTWrrrzvs2/ydLUwtK448HLoaO21NPaaGVpZ2h0yv3X6dbQtcTSu7j2JiMyMDU0MDujrGhlaWdodFtpXcC0y7WjrNXiuPYmIzIwNTQwO8TcubvX986qbGNwJiMyMDU0MDu1xNf308PT8ta71NrX87HftdrSu7j2scjL+9ChtcTOu9bDtb3T0rHftdrSu7j2scjL+9ChtcTOu9bDoaPV4rj2tqvO97rcw/fP1L/J0tSxttT2Uk1RJiM0Mzu2/rfWL7WltffVu6GjPC9wPgo8cD7Wrrrzvs3Kx8r90afM4sHLPC9wPgo8cD6msmxlbltUaV0gJiM0MzsgbGVuW1RqXSA9IChsZW4gJiM0MzsgMSkgKiBsZW4gKiAobGVuIC0gMSmjrNauuvOwycv509DH87P2wLS1xKayMiAqIGxjcChUaSxUaim89bX0vs3Kx7TwsLihozwvcD4KPHA+vMe1w7TwsLi/qmxvbmcgbG9uZzwvcD4KPHA+PGJyPgo8L3A+CjxwPkNPREWjujxicj4KPGJyPgo8cHJlIGNsYXNzPQ=="brush:java;">#include
#include
#include
#include
#define MAX 500010
using namespace std;
#define min(a,b) ((a) < (b) ? (a):(b))
char s[MAX];
int len;
int val[MAX],sa[MAX];
int height[MAX],rank[MAX];
inline bool Same(int x,int y,int l)
{
return val[x] == val[y] &&
((x + l >= len && y + l >= len) || (x + l < len && y + l < len && val[x + l] == val[y + l]));
}
void GetSuffixArray()
{
static int _val[MAX],q[MAX],cnt[MAX],lim = 256;
for(int i = 0; i < len; ++i) ++cnt[val[i] = s[i]];
for(int i = 1; i < lim; ++i) cnt[i] += cnt[i - 1];
for(int i = len - 1; ~i; --i) sa[--cnt[val[i]]] = i;
for(int d = 1;; ++d) {
int top = 0,l = 1 << (d - 1);
for(int i = 0; i < len; ++i) if(sa[i] + l >= len) q[top++] = sa[i];
for(int i = 0; i < len; ++i) if(sa[i] >= l) q[top++] = sa[i] - l;
for(int i = 0; i < lim; ++i) cnt[i] = 0;
for(int i = 0; i < len; ++i) ++cnt[val[q[i]]];
for(int i = 1; i < lim; ++i) cnt[i] += cnt[i - 1];
for(int i = len - 1; ~i; --i) sa[--cnt[val[q[i]]]] = q[i];
lim = 0;
for(int i = 0,j; i < len; ++lim) {
for(j = i; j < len - 1 && Same(sa[j],sa[j + 1],l); ++j);
for(; i <= j; ++i) _val[sa[i]] = lim;
}
for(int i = 0; i < len; ++i) val[i] = _val[i];
if(lim == len) break;
}
return ;
}
void GetHeight()
{
for(int i = 0; i < len; ++i) rank[sa[i]] = i;
for(int i = 0,k = 0; i < len; ++i) {
if(!rank[i]) continue;
if(k) --k;
int j = sa[rank[i] - 1];
while(s[i + k] == s[j + k]) ++k;
height[rank[i]] = k;
}
}
int l[MAX],r[MAX];
int stack[MAX],top;
int main()
{
scanf("%s",s);
len = strlen(s);
GetSuffixArray();
GetHeight();
long long ans = (long long)(len + 1) * len * (len - 1) >> 1;
for(int i = 1; i < len; ++i) {
while(top && height[stack[top]] > height[i]) --top;
if(!top) l[i] = 0;
else l[i] = stack[top];
stack[++top] = i;
}
top = 0;
for(int i = len - 1; i; --i) {
while(top && height[stack[top]] >= height[i]) --top;
if(!top) r[i] = len;
else r[i] = stack[top];
stack[++top] = i;
}
for(int i = 1; i < len; ++i)
ans -= (long long)(i - l[i]) * (r[i] - i) * height[i] * 2;
printf("%lld\n",ans);
return 0;
}
