[LOJ6198] 谢特

之乎者助得甚？

给定字符串\(s\)和序列\(w\)，试求
\[ \max_{1\le i<j\le n} lcp(i,j)+(w_i\veebar w_j) \]
似乎这样的东西都能很好的用SA(height)+启发式合并来完成？

可以联系这题思考。

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10;

int n,w[N],sa[N],ht[N],rc[N];
char s[N];

void buildSa() {
    static int c[N];
    int i,p,k,m=128,*x=ht,*y=rc;
    for(i=0; i<=m; ++i) c[i]=0;
    for(i=1; i<=n; ++i) c[x[i]=s[i]]++;
    for(i=1; i<=m; ++i) c[i]+=c[i-1];
    for(i=n; i>=1; --i) sa[c[x[i]]--]=i;
    for(k=1; k<n; k<<=1) {
        for(i=n-k+1,p=0; i<=n; ++i) y[++p]=i;
        for(i=1; i<=n; ++i) if(sa[i]>k) y[++p]=sa[i]-k;
        for(i=1; i<=m; ++i) c[i]=0;
        for(i=1; i<=n; ++i) c[x[y[i]]]++;
        for(i=1; i<=m; ++i) c[i]+=c[i-1];
        for(i=n; i>=1; --i) sa[c[x[y[i]]]--]=y[i];
        swap(x,y), x[sa[1]]=p=1;
        for(i=2; i<=n; ++i) x[sa[i]]=
            y[sa[i]]==y[sa[i-1]]&&y[sa[i]+k]==y[sa[i-1]+k]?p:++p;
        if((m=p)>=n) break;
    }
    for(i=1; i<=n; ++i) rc[sa[i]]=i;
    for(i=1,k=0; i<=n; ++i) {
        p=sa[rc[i]-1]; if(k) k--; 
        while(s[p+k]==s[i+k]) k++;
        ht[rc[i]]=k;
    }
}

int tot,top,stk[N*18];
int ll[N],rr[N],bl[N],siz[N],ch[N*18][2];
pair<int,int> h[N];

int newNode() {
    return top?stk[top--]:++tot;
}
void fuckNode(int x) {
    stk[++top]=x; 
    ch[x][0]=ch[x][1]=0;
}
void insert(int x,int w) {
    for(int i=16; ~i; --i) {
        if(!ch[x][(w>>i)&1]) ch[x][(w>>i)&1]=newNode();
        x=ch[x][(w>>i)&1];
    }
}
int ans,tmp;
void query(int x,int y,int d,int now) {
    if(d<0) {
        tmp=max(tmp,now);
        return;
    }
    for(int k=0; k<2; ++k) if(ch[x][k]) {
        if(ch[y][k^1]) query(ch[x][k],ch[y][k^1],d-1,now|(1<<d));
        else query(ch[x][k],ch[y][k],d-1,now);
    }
}
void merge(int x,int y,int d) {
    if(d<0) return;
    for(int k=0; k<2; ++k) if(ch[x][k]) {
        if(!ch[y][k]) ch[y][k]=newNode();
        merge(ch[x][k],ch[y][k],d-1);
        fuckNode(ch[x][k]);
    }
}

int main() {
//  freopen("C:/Users/HSY/Downloads/2.in","r",stdin);
    
    scanf("%d%s",&n,s+1);
    for(int i=1; i<=n; ++i) 
        scanf("%d",w+i),newNode();
    buildSa();
    for(int i=2; i<=n; ++i) h[i-1]=make_pair(-ht[i],i);
    for(int i=1; i<=n; ++i) {
        ll[i]=rr[i]=bl[i]=i; siz[i]=1;
        insert(i,w[sa[i]]);
    }
    sort(h+1,h+n);
    for(int i=1; i<n; ++i) {
        int len=-h[i].first;
        int x=bl[h[i].second];
        int y=bl[h[i].second-1];
        if(siz[x]>siz[y]) swap(x,y);
        tmp=0; 
        query(x,y,16,0);
        ans=max(ans,tmp+len);
        for(int j=ll[x]; j<=rr[x]; ++j) bl[j]=y;
        ll[y]=min(ll[x],ll[y]);
        rr[y]=max(rr[x],rr[y]);
        siz[y]+=siz[x];
        merge(x,y,16);
    }
    printf("%d\n",ans);
    return 0;
}

原文链接:https://www.cnblogs.com/nosta/p/11182222.html
如有疑问请与原作者联系

标签：

版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点，本站所提供的摄影照片，插画，设计作品，如需使用，请与原作者联系，版权归原作者所有