BZOJ3879 SvT（后缀树+虚树）

亦凉 2021-12-07 13:31 202阅读 0赞

对反串建SAM得到后缀树，两后缀的lcp就是其在后缀树上lca的len值，于是每次询问对后缀树建出虚树并统计答案即可。

#include<iostream> 
    #include<cstdio>
    #include<cmath>
    #include<cstdlib>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    #define ll long long
    #define N 1000010
    #define P 23333333333333333ll
    char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<'0'||c>'9')) c=getchar();return c;}
    int gcd(int n,int m){return m==0?n:gcd(m,n%m);}
    int read()
    {
    	int x=0,f=1;char c=getchar();
    	while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
    	while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
    	return x*f;
    }
    int n,m,t,a[N*3],son[N][26],fail[N],deep[N],len[N],id[N],p[N],dfn[N],cnt=1,last=1;
    struct data{int to,nxt;
    }edge[N];
    void addedge(int x,int y){t++;edge[t].to=y,edge[t].nxt=p[x],p[x]=t;}
    char s[N];
    void ins(int c)
    {
    	int x=++cnt,p=last;last=x;len[x]=len[p]+1;id[len[x]]=x;
    	while (!son[p][c]) son[p][c]=x,p=fail[p];
    	if (!p) fail[x]=1;
    	else
    	{
    		int q=son[p][c];
    		if (len[p]+1==len[q]) fail[x]=q;
    		else
    		{
    			int y=++cnt;
    			len[y]=len[p]+1;
    			memcpy(son[y],son[q],sizeof(son[q]));
    			fail[y]=fail[q],fail[q]=fail[x]=y;
    			while (son[p][c]==q) son[p][c]=y,p=fail[p];
    		}
    	}
    }
    namespace euler_tour
    {
        int id[N<<1],LG2[N<<1],f[N<<1][22],cnt;
        void dfs(int k)
        {
            dfn[k]=++cnt;id[cnt]=k;
            for (int i=p[k];i;i=edge[i].nxt)
            {
            	deep[edge[i].to]=deep[k]+1;
                dfs(edge[i].to);
                id[++cnt]=k;
            }
        }
        void build()
        {
            dfs(1);
            for (int i=1;i<=cnt;i++) f[i][0]=id[i];
            for (int j=1;j<=21;j++)
                for (int i=1;i<=cnt;i++)
                if (deep[f[i][j-1]]<deep[f[min(cnt,i+(1<<j-1))][j-1]]) f[i][j]=f[i][j-1];
                else f[i][j]=f[min(cnt,i+(1<<j-1))][j-1];
            for (int i=2;i<=cnt;i++)
            {
                LG2[i]=LG2[i-1];
                if ((2<<LG2[i])<=i) LG2[i]++;
            }
        }
        int lca(int x,int y)
        {
            if (!x||!y) return 0;
            x=dfn[x],y=dfn[y];
            if (x>y) swap(x,y);
            if (deep[f[x][LG2[y-x+1]]]<deep[f[y-(1<<LG2[y-x+1])+1][LG2[y-x+1]]]) return f[x][LG2[y-x+1]];
            else return f[y-(1<<LG2[y-x+1])+1][LG2[y-x+1]];
        }
    }
    using euler_tour::lca;
    namespace virtual_tree
    {
    	int p[N],size[N],stk[N],top,t;
    	bool flag[N];
    	ll ans;
    	struct data{int to,nxt;}edge[N];
    	void addedge(int x,int y){t++;edge[t].to=y,edge[t].nxt=p[x],p[x]=t;}
    	void newnode(int k,int x){if (!flag[k]) p[k]=0,flag[k]=1,size[k]=x;}
    	void build(int *a,int n)
    	{
    		stk[top=1]=1;newnode(1,0);t=0;
    		for (int i=1;i<=n;i++)
    		{
    			int l=lca(a[i],stk[top]);newnode(l,0);
    			while (top>1&&deep[stk[top-1]]>=deep[l]) addedge(stk[top-1],stk[top]),top--;
    			if (l!=stk[top]) addedge(l,stk[top]),stk[top]=l;
    			stk[++top]=a[i];newnode(a[i],1);
    		}
    		while (top) addedge(stk[top-1],stk[top]),top--;
    	}
    	void work(int k)
    	{
    		flag[k]=0;
    		for (int i=p[k];i;i=edge[i].nxt)
    		{
    			work(edge[i].to);
    			ans=(ans+1ll*size[k]*size[edge[i].to]*len[k])%P;
    			size[k]+=size[edge[i].to];
    		}
    	}
    	ll calc()
    	{
    		ans=0;
    		work(1);
    		return ans;
    	}
    }
    bool cmp(const int&x,const int&y)
    {
    	return dfn[x]<dfn[y];
    }
    int main()
    {
    #ifndef ONLINE_JUDGE
    	freopen("a.in","r",stdin);
    	freopen("a.out","w",stdout);
    	const char LL[]="%I64d\n";
    #else
    	const char LL[]="%lld\n";
    #endif
    	n=read(),m=read();
    	scanf("%s",s+1);
    	for (int i=1;i<=n;i++) ins(s[n-i+1]-'a');
    	for (int i=2;i<=cnt;i++) addedge(fail[i],i);
    	euler_tour::build();
    	while (m--)
    	{
    		t=read();for (int i=1;i<=t;i++) a[i]=id[n-read()+1];
    		sort(a+1,a+t+1,cmp);t=unique(a+1,a+t+1)-a-1;
    		virtual_tree::build(a,t);
    		printf(LL,virtual_tree::calc());
    	}
    	return 0;
    }

转载于:https://www.cnblogs.com/Gloid/p/10833132.html