BZOJ3019 : [Balkan2012]handsome

首先預處理出$f[i][j][k]$表示長度為$i$的序列，第一個位置是$j$，最后一個位置是$k$時合法的方案數。

從后往前枚舉LCP以及那個位置應該改成什么。

用線段樹維護區間內最左最右的已經確定的位置，以及區間內的合法方案數。

合并的時候只需要將左右兒子的答案乘起來，然后再乘以左兒子最右到右兒子最左這一段區間的方案數即可。

時間復雜度$O(n\log n)$。

?

#include<cstdio>
const int N=400010,M=1050000,P=1000000007;
int n,m,i,j,k,x,a[N],g[3][3],f[N][3][3],pos[N],v[N],l[M],r[M],val[M],ans=1;char ch[9],s[N];
inline void read(int&a){char c;while(!(((c=getchar())>='0')&&(c<='9')));a=c-'0';while(((c=getchar())>='0')&&(c<='9'))(a*=10)+=c-'0';}
inline void up(int&x,int y){x+=y;if(x>=P)x-=P;}
void build(int x,int a,int b){l[x]=a,r[x]=b,val[x]=1;if(a==b){pos[a]=x;return;}int mid=(a+b)>>1;build(x<<1,a,mid),build(x<<1|1,mid+1,b);
}
inline bool change(int x,int p){if(~p){if(x>1&&~v[x-1])if(g[v[x-1]][p])return 0;if(x<n&&~v[x+1])if(g[p][v[x+1]])return 0;}v[x]=p,x=pos[x];if(p<0)l[x]=r[x]=0;for(x>>=1;x;x>>=1){l[x]=l[x<<1]?l[x<<1]:l[x<<1|1];r[x]=r[x<<1|1]?r[x<<1|1]:r[x<<1];val[x]=1LL*val[x<<1]*val[x<<1|1]%P;if(r[x<<1]&&l[x<<1|1])val[x]=1LL*val[x]*f[l[x<<1|1]-r[x<<1]+1][v[r[x<<1]]][v[l[x<<1|1]]]%P;}return 1;
}
inline int ask(){int ret=val[1],t,i;if(l[1]>1){for(t=i=0;i<3;i++)up(t,f[l[1]][i][v[l[1]]]);ret=1LL*ret*t%P;}if(r[1]<n){for(t=i=0;i<3;i++)up(t,f[n-r[1]+1][v[r[1]]][i]);ret=1LL*ret*t%P;}return ret;
}
int main(){read(n);for(i=1;i<=n;i++)read(a[i]);read(m);while(m--)scanf("%s",ch),g[ch[0]-'1'][ch[1]-'1']=1;scanf("%s",s+1);for(i=1;i<=n;i++)s[i]-='1',v[i]=s[i];for(i=0;i<3;i++)f[1][i][i]=1;for(i=1;i<n;i++)for(j=0;j<3;j++)for(k=0;k<3;k++)if(f[i][j][k])for(x=0;x<3;x++)if(!g[k][x])up(f[i+1][j][x],f[i][j][k]);build(1,1,n);for(i=n;i;change(a[i--],-1))for(j=0;j<s[a[i]];j++)if(change(a[i],j))up(ans,ask());return printf("%d",ans),0;
}