cogs2223. [SDOI2016 Round1] 生成魔咒（后缀数组 hash 二分 set

题意：对一个空串每次在后面加一个字符，问每加完一次得到的字符串有几个不同的子串。

思路：每个子串都是某个后缀的前缀，对于每个后缀求出他能贡献出之前没有出现过的前缀的个数，答案累加就行。

要求每个后缀的贡献，就是这个后缀的长度减去此前的后缀与该后缀的LCP的最大值，这个最大值是height[i]。

至于怎么找出先前的能与该后缀生成最大LCP的后缀，可以用set维护，将cmp函数自定义成按字典序从小到大，

那么目标后缀就是当前后缀的前趋或后继，求两次LCP并更新答案即可。字符串hash用来比较，二分答案找LCP的值，

另外s.insert(i).first能返回把元素i插入到s中的地址（迭代器）。

#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ULL;
const int maxn=200000;
const ULL BASE=1e9+7;
int N,now;
ULL a[maxn],base[maxn],has[maxn],ANS;

inline ULL get_hash(ULL from,ULL len){
    return has[from]-has[from+len]*base[len];
}
inline int find(int l,int r,int f1,int f2){
    if(l+1>=r) {
        if(get_hash(f1,r)==get_hash(f2,r)) return r;
        else return l;
    }
    int mid = (l+r)>>1;
    if(get_hash(f1,mid)==get_hash(f2,mid)) 
        return find(mid,r,f1,f2);
    else return find(l,mid-1,f1,f2);
}

struct cmp{
    bool operator()(const int &aa,const int &bb){
        int len = find(0,1e5,aa,bb);
        return a[aa+len]<a[bb+len];
    }
};
set<int,cmp> S;
set<int,cmp>::iterator tmp1,tmp2;
int main(){
    freopen("menci_incantation.in","r",stdin);
    freopen("menci_incantation.out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>N;
    base[0] = 1;
    for(int i=1;i<=N;i++) base[i] = base[i-1]*BASE;
    for(int i=N;i>=1;i--){
        cin>>a[i];
        now = 0;
        has[i] = has[i+1]*BASE+a[i];
        tmp1 = S.insert(i).first;
        tmp2 = tmp1;
        if(tmp1!=S.begin()){
            tmp1--;
            now = find(0,1e5,i,*tmp1);
        }
        if(++tmp2!=S.end()){
            now = max(now,find(0,1e5,i,*tmp2));
        }
        ANS += (ULL)N-i+1-now;
        cout<<ANS<<endl;
    }
    return 0;
}