★3.5位でもいい気がする。
https://yukicoder.me/problems/no/2020
問題
N個の文字列S[i]が与えられる。
以下のクエリに順次答えよ。
- 指定された文字列S[x]の末尾に1文字cを加える
- 文字列を1つS[y]が指定されるので、他の文字列との共通接頭辞の長さの総和を答える。
解法
まずクエリ完了後の文字列群に対しTrieを構築し、DFS順でインデックスを張ろう。
S[x]文字列の末尾に文字が追加される場合、S[y]の末尾に対応するTrie上のノードが、S[x]の追加した文字に対応するノードのSubTree内にあれば、解は1増加する。
そのため、BITを使って文字列追加毎に区間に1を加算していこう。
後者のクエリに対しては、BIT上でS[y]に対応するノードに対応する値を答えればよい。
int nex; int E[454545][26]; int N; string S[202020],T[202020]; int pos[202020]; int Q; int A[202020],B[202020]; char C[202020]; int id; int L[454545],R[454545]; void dfs(int cur,int pos,string& S) { if(pos==S.size()) return; int x=S[pos]-'a'; if(E[cur][x]==-1) { E[cur][x]=nex++; } dfs(E[cur][x],pos+1,S); } void dfs2(int cur) { L[cur]=id++; int i; FOR(i,26) if(E[cur][i]!=-1) dfs2(E[cur][i]); R[cur]=id++; } template<class V, int ME> class BIT { public: V bit[1<<ME]; V operator()(int e) {if(e<0) return 0;V s=0;e++;while(e) s+=bit[e-1],e-=e&-e; return s;} void add(int e,V v) { e++; while(e<=1<<ME) bit[e-1]+=v,e+=e&-e;} }; BIT<ll,20> bt; void solve() { int i,j,k,l,r,x,y; string s; cin>>N; FOR(i,N) { cin>>S[i]; T[i]=S[i]; } cin>>Q; FOR(i,Q) { cin>>A[i]>>B[i]; B[i]--; if(A[i]==1) { cin>>C[i]; T[B[i]]+=C[i]; } } MINUS(E); nex=1; FOR(i,N) dfs(0,0,T[i]); dfs2(0); FOR(i,N) { FORR(c,S[i]) { x=c-'a'; pos[i]=E[pos[i]][x]; bt.add(L[pos[i]],1); bt.add(R[pos[i]],-1); } } FOR(i,Q) { y=B[i]; if(A[i]==1) { x=C[i]-'a'; S[y]+=C[y]; pos[y]=E[pos[y]][x]; bt.add(L[pos[y]],1); bt.add(R[pos[y]],-1); } else { cout<<bt(L[pos[y]])<<endl; } } }
まとめ
Trieを思いつけばあとはもうすぐ。