BZOJ 3238: [Ahoi2013]差异 [后缀数组单调栈]

3238: [Ahoi2013]差异

Time Limit: 20 Sec Memory Limit: 512 MB
Submit: 2326 Solved: 1054
[Submit][Status][Discuss]

Description

Input

一行，一个字符串S

Output

一行，一个整数，表示所求值

Sample Input

cacao

Sample Output

HINT

2<=N<=500000,S由小写英文字母组成

集训的时候想出来了还讲了一下 bingo！

前面的式子随便找一下规律(想一下矩阵)，发现求和时一个数贡献(n-1)次.......

后面很显然就是求一个height[i]在多长的区间内是最小的，然后贡献上这一段答案左长度*右长度*height

求这个不是裸单调栈嘛

发现以前单调栈写的太..了，，，st[]保存的是元素编号，l[i]和r[i]是i往两段延伸的长度，发现很多人两遍，一遍就可以了

//
//  main.cpp
//  bzoj3238
//
//  Created by Candy on 2017/1/4.
//  Copyright © 2017年 Candy. All rights reserved.
//

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
const int N=5e5+5;
typedef long long ll;
int n;
char s[N];
int sa[N],rnk[N],t1[N],t2[N],height[N],c[N];
bool cmp(int *r,int a,int b,int j){
    return a+j<=n&&b+j<=n&&r[a]==r[b]&&r[a+j]==r[b+j];
}
void getSA(int m){
    int *r=t1,*k=t2;
    for(int i=1;i<=n;i++) c[r[i]=s[i]]++;
    for(int i=1;i<=m;i++) c[i]+=c[i-1];
    for(int i=n;i>=1;i--) sa[c[r[i]]--]=i;
    for(int j=1;j<=n;j<<=1){
        int p=0;
        for(int i=n-j+1;i<=n;i++) k[++p]=i;
        for(int i=1;i<=n;i++) if(sa[i]>j) k[++p]=sa[i]-j;
        
        for(int i=0;i<=m;i++) c[i]=0;
        for(int i=1;i<=n;i++) c[r[k[i]]]++;
        for(int i=1;i<=m;i++) c[i]+=c[i-1];
        for(int i=n;i>=1;i--) sa[c[r[k[i]]]--]=k[i];
        
        swap(r,k);p=0;r[sa[1]]=++p;
        for(int i=2;i<=n;i++) r[sa[i]]=cmp(k,sa[i],sa[i-1],j)?p:++p;
        if(p>=n) break;m=p;
    }
}
void getHeight(){
    for(int i=1;i<=n;i++) rnk[sa[i]]=i;
    int k=0;
    for(int i=1;i<=n;i++){
        if(k) k--;
        if(rnk[i]==1) continue;
        int j=sa[rnk[i]-1];
        while(i+k<=n&&j+k<=n&&s[i+k]==s[j+k]) k++;
        height[rnk[i]]=k;
    }
}

int st[N],l[N],r[N],top;
void solve(){ //for(int i=1;i<=n;i++) printf("hi %d %d %d
",sa[i],rnk[i],height[i]);
    ll ans=(ll)n*(n+1)*(n-1)/2;
    for(int i=1;i<=n;i++){
        int le=i;
        while(top&&height[st[top]]>=height[i]){
            le=l[st[top]];
            r[st[top]]=i-1;
            top--;
        }
        st[++top]=i;
        l[i]=le;
    }
    while(top) r[st[top--]]=n;
    for(int i=1;i<=n;i++) ans-=(ll)2*height[i]*(i-l[i]+1)*(r[i]-i+1);
    printf("%lld",ans);
}
int main(int argc, const char * argv[]) {
    scanf("%s",s+1);
    n=strlen(s+1);
    getSA(300);
    getHeight();
    solve();
    return 0;
}

BZOJ 3238: [Ahoi2013]差异 [后缀数组 单调栈]