「ROI 2016 Day2」二指禅

考虑对于每个点，有前缀和后缀两种转移

对于两种转移分别建立$\text{trie}$树，并且维护最小权值，对于$dp_i$，可以匹配一段后缀从$j<i$得到

也可以匹配一段前缀更新$j>i$，分别$O(n)$枚举在两棵树上匹配即可完成转移

暴力转移复杂度为$O(n^2)$

考虑优化转移效率，以$dp_i$匹配某一段前缀向$dp_j(j>i)$转移为例

Part1 考虑求出最大的$j$

这个问题实际上就是求出每一个后缀的最大前缀匹配，也就是一个$\text{exkmp}$问题

而且这题是一个多模板串版本，并不能用$\text{exkmp}$解决

Solution 1

是把所有前缀hash值取出来，放到$\text{hash_table}$里，然后二分长度+$\text{hash_table}$查询，复杂度为$O(\log L)$

Solution 2

树剖+hash

对于$\text{trie}$树树剖并且预处理hash值，重链上二分hash匹配，轻儿子暴力走，复杂度为$O(\log ^2L)$

如果使用全局平衡二叉树，可以做到单次查询复杂度为$O(\log L)$，常数应该远小于$\text{hash_table}$

Part2 在$j_{max}$基础上转移

考虑先求出最大的$j$之后，得到其对应的$\text{trie}$树节点$u$，在的祖先$u$中，每一种不同的权值更新一次

显然每一个祖先长度不同，因此最多只有$O(\sqrt L)$中不同的权值

因此可以for过去更新每一种权值，每次更新是一段区间，可以用树状数组维护

但是实际上极限情况下段极短，可以暴力枚举区间，所以并不是真的$O(\sqrt L\log L)$

比较容易说明复杂度的优化方法是：

采用分块$O(1)$更新，$O(\sqrt L)$查询

这样可以做到稳定$O(\sqrt L)$完成转移

因此预处理复杂度为$O(m\log L-m\log ^2L)$，转移复杂度为$O(m\sqrt L-m\sqrt L\log L)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,a,b) for(int i=a,i##end=b;i<=i##end;++i)
#define drep(i,a,b) for(int i=a,i##end=b;i>=i##end;--i)
template <class T> inline void cmin(T &a,T b){ ((a>b)&&(a=b)); }

const int N=3e5+10,INF=1e9+10,D=6;

int n,m;
char T[N];
int Pow1[N],Pow2[N];
int S[N];
const ll K1=19260817,P1=114514;
const ll K2=1e9+13,P2=1919810;

struct Solver{
    int S[N];
    int trie[N][2],s[N],cnt,H1[N],H2[N];
    int fa[N],top[N],sz[N],h1[N],h2[N],son[N],lst[N],bot[N],L[N],id[N],dfn,dep[N];
    // lst[i] 记录祖先中第一个s[f]!=s[i]的节点
    void dfs(int u){
        sz[u]=1;
        if(s[u]==s[fa[u]]) lst[u]=lst[fa[u]];
        else lst[u]=fa[u];
        rep(i,0,1) {
            int v=trie[u][i];
            if(!v) continue;
            fa[v]=u,dep[v]=dep[u]+1;
            h1[v]=(h1[u]*K1+i+1)%P1;
            h2[v]=(h2[u]*K2+i+1)%P2;
            dfs(v);
            sz[u]+=sz[v];
            if(son[u]==0 || sz[v]>sz[son[u]]) son[u]=v;
        }
    }
    void dfs(int u,int t){
        id[L[u]=++dfn]=u;
        bot[top[u]=t]=u; if(son[u]) dfs(son[u],t);
        for(int v:trie[u]) if(v&&v!=son[u]) dfs(v,v);
    }
    void Ins(char *T,int l,int w){
        int now=0;
        rep(i,1,l) {
            int c=T[i]-'0';
            if(!trie[now][c]) s[trie[now][c]=++cnt]=2e9;
            cmin(s[now=trie[now][c]],w);
        }
    }
    void Init(){
        rep(i,1,n) {
            H1[i]=(H1[i-1]*K1+S[i]+1)%P1;
            H2[i]=(H2[i-1]*K2+S[i]+1)%P2;
        }
        dfs(0),dfs(0,0);
    }
    int Que(int i) {
        // 求i 的最长匹配位置
        int u=0;
        while(i<=n) {
            if(!trie[u][S[i]]) break;
            if(trie[u][S[i]]!=son[u]){ u=trie[u][S[i++]]; continue; }
            int l=1,r=min(n-i+1,dep[bot[top[u]]]-dep[u]),res=1;
            while(l<=r){
                int mid=(l+r)>>1;
                if( (H1[i+mid-1]-1ll*H1[i-1]*Pow1[mid]%P1+P1)%P1 ==  (h1[id[L[u]+mid]]-1ll*h1[u]*Pow1[mid]%P1+P1)%P1 &&
                        (H2[i+mid-1]-1ll*H2[i-1]*Pow2[mid]%P2+P2)%P2 == (h2[id[L[u]+mid]]-1ll*h2[u]*Pow2[mid]%P2+P2)%P2)
                    l=mid+1,res=mid;
                else r=mid-1;
            }
            i+=res,u=id[L[u]+res];
        }
        return u;
    }
} X,Y;

struct BIT{
    ll s[N];
    void Init(){
        memset(s,127,sizeof s);
    }
    void Add(int p,ll x){
        while(p) cmin(s[p],x),p-=p&-p;
    }
    ll Que(int p){
        ll res=1e18;
        while(p<=n) cmin(res,s[p]),p+=p&-p;
        return res;
    }
} TX,TY;
ll dp[N];

int main(){
    rep(i,Pow1[0]=Pow2[0]=1,N-1) {
        Pow1[i]=Pow1[i-1]*K1%P1;
        Pow2[i]=Pow2[i-1]*K2%P2;
    }
    scanf("%d%d%*d",&n,&m);
    rep(i,1,n) scanf("%1d",S+i),X.S[i]=Y.S[n-i+1]=S[i];
    rep(t,1,m) {
        int w,l; scanf("%d%s",&w,T+1),l=strlen(T+1);
        X.Ins(T,l,w),reverse(T+1,T+l+1),Y.Ins(T,l,w);
    }
    X.Init(),Y.Init();

    rep(i,1,n) dp[i]=1e18;
    TX.Init(),TY.Init();
    TY.Add(1,0);
    rep(i,0,n) {
        // 暴力维护转移
        if(i) {
            cmin(dp[i],TX.Que(i));
            int u=Y.Que(n-i+1);
            while(u) {
                int l=Y.dep[Y.lst[u]]+1,r=Y.dep[u];
                if(r-l+1<=D) rep(j,l,r) cmin(dp[i],dp[i-j]+Y.s[u]);
                else cmin(dp[i],TY.Que(i-r+1)+Y.s[u]);
                u=Y.lst[u];
            }
        }
        TY.Add(i+1,dp[i]);
        if(i==n||dp[i]==1e18) continue;
        int u=X.Que(i+1);
        while(u) {
            int l=X.dep[X.lst[u]]+1,r=X.dep[u];
            if(r-l+1<=D) rep(j,l,r) cmin(dp[i+j],dp[i]+X.s[u]);
            else TX.Add(i+r,dp[i]+X.s[u]);
            u=X.lst[u];
        }
    }
    printf("%lld\n",dp[n]<1e18?dp[n]:-1);
}