zcmimi's blog
查看原题

点击跳转

可以考虑把字符串倒序

这样添加一个字母相当于增加了一个后缀,相对原来更好处理

可以发现在插入新的字符串时,height改变的只有height[pre],height[p],height[nxt]

通过平衡树动态维护这三个位置就可以了

#include<bits/stdc++.h>
#define gc getchar()
#define fur(i,x,y) for(int i=x;i<=y;++i)
void cmax(int &x,int y){if(x<y)x=y;}
int rd(){int x=0;char c;bool f=0;for(c=gc;c<'0'||'9'<c;c=gc)f^=c=='-';for(x=c-48,c=gc;'0'<=c&&c<='9';x=x*10+c-48,c=gc);return f?-x:x;}
const int N=100011;
using std::set;
int n,m,s[N],sa[N],rnk[N],tax[N],tp[N],height[N],f[20][N];
void qsort(){
    fur(i,0,m)tax[i]=0;
    fur(i,1,n)++tax[rnk[i]];
    fur(i,1,m)tax[i]+=tax[i-1];
    for(int i=n;i;--i)sa[tax[rnk[tp[i]]]--]=tp[i];
}
void suffix(){
    m=100000;
    fur(i,1,n)tp[i]=i,rnk[i]=s[i];
    qsort();
    for(int w=1,p=0;p<n;m=p,w<<=1){
        p=0;
        fur(i,1,w)tp[++p]=n-w+i;
        fur(i,1,n)if(sa[i]>w)tp[++p]=sa[i]-w;
        qsort();
        std::swap(tp,rnk);
        rnk[sa[1]]=p=1;
        fur(i,2,n)rnk[sa[i]]=p+=tp[sa[i]]^tp[sa[i-1]]||tp[sa[i]+w]^tp[sa[i-1]+w];
    }
}
void gh(){
    for(int i=1,k=0;i<=n;++i){
        if(k)--k;
        int j=sa[rnk[i]-1];
        while(s[i+k]==s[j+k]&&i+k<=n&&j+k<=n)++k;
        height[rnk[i]]=k;
    }
}
int min(int x,int y){return x<y?x:y;}
void st(){
    fur(i,1,n)f[0][i]=height[i];
    fur(k,1,20)
        fur(i,1,n-(1<<k)+1)
            f[k][i]=min(f[k-1][i],f[k-1][i+(1<<k-1)]);
}
int ask(int l,int r){
    if(l==r)return -1u>>1;
    ++l;
    int k=log2(r-l+1);
    return min(f[k][l],f[k][r-(1<<k)+1]);
}
struct qwq{int v,p;bool operator<(qwq t){return v<t.v;}}b[N];
set<int>T;
int main(){
    n=rd();
    fur(i,1,n)b[i]={rd(),i};
    std::sort(b+1,b+n+1);
    int p=0;long long ans=0;
    fur(i,1,n)s[n-b[i].p+1]=p+=b[i].v!=b[i-1].v;
    suffix(),gh(),st();
    for(int i=n;i;--i){
        T.insert(rnk[i]);
        set<int>::iterator it=T.find(rnk[i]);
        int k=0;
        if(it!=T.begin()){
            p=*(--it);
            k=ask(p,rnk[i]);
            ++it;
        }
        ++it;
        if(it!=T.end()){
            p=*it;
            cmax(k,ask(rnk[i],p));
        }
        ans+=n-i+1-k;
        printf("%lld\n",ans);
    }
}
LG 4070 [SDOI2016]生成魔咒
comment评论
Search
search