題目鏈接：點擊查看

題目大意：給出 n 個模式串，每個模式串初始時的權(quán)值為 0，然后有 m 次操作：

1 i x：將第 i 個模式串的權(quán)值修改為 x

2 s：給出一個字符串 s，詢問字符串 s 作為主串時，所有可以與其匹配的模式串中，權(quán)值的最大值

題目分析：記錄一下第一次單切 div2 的 G 題吧，不知道是 cf 題目質(zhì)量變撈了還是我變強了，比賽結(jié)束前 20 分鐘看到 G 出的比 F 還多，反正在掛機也是無聊，就開了 G 題，發(fā)現(xiàn)就是 AC 自動機的裸題，寫了一發(fā)暴跳 fail 的代碼，交上去果不其然 T 掉了，后來想到了正解，但是只剩下了十分鐘。。賽后結(jié)束了一小時的時候 A 掉的

我的思路非常簡單，主要是數(shù)據(jù)結(jié)構(gòu)的嵌套比較復(fù)雜，代碼實現(xiàn)的復(fù)雜度有點高，看到前排大佬有更簡單的做法，但我沒有 get 到，是我菜了

首先肯定是將 n 個模式串扔進 AC 自動機里建 fail 樹，對于每個主串單獨進行匹配，當(dāng)枚舉到了第 i 個位置的時候，假設(shè)在樹上匹配到了節(jié)點 pos，顯然從根節(jié)點到 pos 節(jié)點的這條樹鏈都是可以在主串中匹配到的（都是前綴的后綴），每次都維護一下根節(jié)點到 pos 節(jié)點這條樹鏈上的最大值即可

再考慮更新，對于每個模式串而言，在字典樹上都有著唯一對應(yīng)的一個節(jié)點，我們只需要將這個節(jié)點對應(yīng)到線段樹上的那個位置更新一下即可

上述的兩個操作分別對應(yīng)著區(qū)間查詢最大值和單點修改，這個是線段樹的基本操作，基于是在樹鏈上操作，所以在 fail 樹上再進行一次樹鏈剖分就可以了

最后考慮一下，給出的字符串會有重復(fù)，也就是說在字典樹上的一個節(jié)點可能對應(yīng)著多個字符串，因為每次詢問只需要回答最大值，所以對于一個節(jié)點而言，只有最大值才具有貢獻，所以對于字典樹上的每個節(jié)點，我都用一個 mutilset 來維護每個節(jié)點的最大值，用于操作 1 的更新

時間復(fù)雜度為 O( nlog^2n )?

UPDATE：

補個題都能被hack。。

去看了一眼 hack 數(shù)據(jù)，發(fā)現(xiàn)是 multiset 使用錯誤，具體參考：

https://www.cnblogs.com/lakeone/p/5600494.html

簡單來說，如果設(shè)置 multiset<int>st：

st.erase(x)：將集合中所有的 x 都刪除

st.erase(st.find(x))：刪掉集合中的一個 x

UPDATE2：

補 F 題的時候翻到了一篇 G 的題解，證明了暴跳 fail 樹是可行的，甚至比樹剖還要優(yōu)秀（體現(xiàn)在代碼復(fù)雜度以及時間復(fù)雜度上），因為長度不同的串至多有 sqrt( n ) 個，所以如果跳過所有值為 -1 的節(jié)點，均攤時間復(fù)雜度是 O( n * sqrt( n ) )

代碼：
樹鏈剖分：

//#pragma GCC optimize(2) //#pragma GCC optimize("Ofast","inline","-ffast-math") //#pragma GCC target("avx,sse2,sse3,sse4,mmx") #include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> #include<cassert> #include<bitset> using namespace std;typedef long long LL;typedef unsigned long long ull;const int inf=0x3f3f3f3f;const int N=3e5+100;char s[N];int fail[N],trie[N][26],a[N],cnt=0;multiset<int>mmax[N];int rk[N];void insert_word(int id) {int len=strlen(s);int pos=0;for(int i=0;i<len;i++){int to=s[i]-'a';if(!trie[pos][to])trie[pos][to]=++cnt;pos=trie[pos][to];}mmax[pos].insert(0);rk[id]=pos; }void getfail() {queue<int>q;for(int i=0;i<26;i++){if(trie[0][i]){fail[trie[0][i]]=0;q.push(trie[0][i]);}}while(!q.empty()){int cur=q.front();q.pop();for(int i=0;i<26;i++){if(trie[cur][i]){fail[trie[cur][i]]=trie[fail[cur]][i];q.push(trie[cur][i]);}elsetrie[cur][i]=trie[fail[cur]][i];}} }vector<int>node[N];int son[N],fa[N],num[N];void dfs1(int u,int f) {son[u]=0;fa[u]=f;num[u]=1;for(auto v:node[u]){if(v==f)continue;dfs1(v,u);num[u]+=num[v];if(!son[u]||num[son[u]]<num[v])son[u]=v;} }int top[N],id[N],idd[N],tot;//id[節(jié)點]=編號 idd[編號]=節(jié)點void dfs2(int u,int root) {top[u]=root;id[u]=++tot;idd[tot]=u;if(son[u])dfs2(son[u],root);for(int i=0;i<node[u].size();i++){int v=node[u][i];if(v==fa[u]||v==son[u])continue;dfs2(v,v);} }struct Node {int l,r,mmax; }tree[N<<2];void pushup(int k) {tree[k].mmax=max(tree[k<<1].mmax,tree[k<<1|1].mmax); }void build(int k,int l,int r) {tree[k].l=l;tree[k].r=r;if(l==r){tree[k].mmax=*mmax[idd[l]].rbegin();return;}int mid=l+r>>1;build(k<<1,l,mid);build(k<<1|1,mid+1,r);pushup(k); }void update(int k,int pos,int val) {if(tree[k].l==tree[k].r){tree[k].mmax=val;return;}int mid=tree[k].l+tree[k].r>>1;if(mid>=pos)update(k<<1,pos,val);elseupdate(k<<1|1,pos,val);pushup(k); }int query(int k,int l,int r) {if(tree[k].r<l||tree[k].l>r)return -inf;if(tree[k].l>=l&&tree[k].r<=r)return tree[k].mmax;return max(query(k<<1,l,r),query(k<<1|1,l,r)); }void update(int x) {update(1,id[x],*mmax[x].rbegin()); }int query(int x) {int ans=-inf;while(top[x]!=0){ans=max(ans,query(1,id[top[x]],id[x]));x=fa[top[x]];}ans=max(ans,query(1,id[0],id[x]));return ans; }int search_word() {int ans=-inf;int pos=0;for(int i=0;s[i];i++){int to=s[i]-'a';pos=trie[pos][to];ans=max(ans,query(pos));}return ans; }int main() { #ifndef ONLINE_JUDGE // freopen("data.in.txt","r",stdin); // freopen("data.out.txt","w",stdout); #endif // ios::sync_with_stdio(false);int n,m;scanf("%d%d",&n,&m);for(int i=1;i<=n;i++){scanf("%s",s);insert_word(i);}getfail();mmax[0].insert(-1);for(int i=1;i<=cnt;i++)//建立fail樹{node[fail[i]].push_back(i);mmax[i].insert(-1);}dfs1(0,-1);dfs2(0,0);build(1,1,tot);while(m--){int op;scanf("%d",&op);if(op==1){int pos,val;scanf("%d%d",&pos,&val);mmax[rk[pos]].erase(mmax[rk[pos]].find(a[pos]));a[pos]=val;mmax[rk[pos]].insert(a[pos]);update(rk[pos]);}else{scanf("%s",s);printf("%d\n",search_word());}}return 0; }

暴跳fail：

//#pragma GCC optimize(2) //#pragma GCC optimize("Ofast","inline","-ffast-math") //#pragma GCC target("avx,sse2,sse3,sse4,mmx") #include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> #include<cassert> #include<bitset> using namespace std;typedef long long LL;typedef unsigned long long ull;const int inf=0x3f3f3f3f;const int N=3e5+100;char s[N];int fail[N],trie[N][26],a[N],top[N],cnt=0;multiset<int>mmax[N];int rk[N];void insert_word(int id) {int len=strlen(s);int pos=0;for(int i=0;i<len;i++){int to=s[i]-'a';if(!trie[pos][to])trie[pos][to]=++cnt;pos=trie[pos][to];}mmax[pos].insert(0);rk[id]=pos; }void getfail() {queue<int>q;for(int i=0;i<26;i++){if(trie[0][i]){fail[trie[0][i]]=0;q.push(trie[0][i]);}}while(!q.empty()){int cur=q.front();q.pop();if(*mmax[fail[cur]].rbegin()>=0)top[cur]=fail[cur];elsetop[cur]=top[fail[cur]];for(int i=0;i<26;i++){if(trie[cur][i]){fail[trie[cur][i]]=trie[fail[cur]][i];q.push(trie[cur][i]);}elsetrie[cur][i]=trie[fail[cur]][i];}} }int search_word() {int ans=-1;int pos=0;for(int i=0;s[i];i++){int to=s[i]-'a';pos=trie[pos][to];for(int j=pos;j;j=top[j])ans=max(ans,*mmax[j].rbegin());}return ans; }int main() { #ifndef ONLINE_JUDGE // freopen("data.in.txt","r",stdin); // freopen("data.out.txt","w",stdout); #endif // ios::sync_with_stdio(false);int n,m;scanf("%d%d",&n,&m);for(int i=1;i<=n;i++){scanf("%s",s);insert_word(i);}for(int i=0;i<=cnt;i++)mmax[i].insert(-1);getfail();while(m--){int op;scanf("%d",&op);if(op==1){int pos,val;scanf("%d%d",&pos,&val);mmax[rk[pos]].erase(mmax[rk[pos]].find(a[pos]));a[pos]=val;mmax[rk[pos]].insert(a[pos]);}else{scanf("%s",s);printf("%d\n",search_word());}}return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的CodeForces - 1437G Death DBMS(AC自动机fail树上树链剖分建线段树/暴跳fail)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。