結果
問題 | No.2020 Sum of Common Prefix Length |
ユーザー | 沙耶花 |
提出日時 | 2022-07-22 22:23:17 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 361 ms / 2,000 ms |
コード長 | 3,344 bytes |
コンパイル時間 | 6,523 ms |
コンパイル使用メモリ | 281,016 KB |
実行使用メモリ | 53,092 KB |
最終ジャッジ日時 | 2024-07-04 06:55:46 |
合計ジャッジ時間 | 16,282 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 38 |
ソースコード
#include <stdio.h> #include <atcoder/all> #include <bits/stdc++.h> using namespace std; using namespace atcoder; using mint = modint998244353; #define rep(i,n) for (int i = 0; i < (n); ++i) #define Inf 1000000000 struct HLD{ vector<int> sz,parent,depth,root,pos; vector<int> arr; HLD(vector<vector<int>> &E){ sz.resize(E.size(),1); parent.resize(E.size(),0); depth.resize(E.size(),0); root.resize(E.size(),0); pos.resize(E.size(),0); dfs(0,-1,E); dfs2(0,-1,E,0); } void dfs(int now,int p,vector<vector<int>> &E){ parent[now] = p; if(p==-1){ depth[now] = 0; } else{ depth[now] = depth[p]+1; } for(int i=0;i<E[now].size();i++){ int to = E[now][i]; if(to==p)continue; dfs(to,now,E); sz[now] += sz[to]; } } void dfs2(int now,int p,vector<vector<int>> &E,int r){ pos[now] = arr.size(); arr.push_back(now); root[now] = r; int maxi = 0; int ind = -1; for(int i=0;i<E[now].size();i++){ int to = E[now][i]; if(to==p)continue; if(maxi<sz[to]){ maxi = sz[to]; ind = to; } } if(ind==-1)return; dfs2(ind,now,E,r); for(int i=0;i<E[now].size();i++){ int to = E[now][i]; if(to==p||to==ind)continue; dfs2(to,now,E,to); } } vector<pair<int,int>> query(int u,int v){ vector<pair<int,int>> ret; int t = 0; while(root[u]!=root[v]){ if(depth[root[u]] <= depth[root[v]]){ ret.insert(ret.begin()+t,{pos[root[v]], pos[v]}); v = parent[root[v]]; } else{ ret.insert(ret.begin()+t,{pos[u],pos[root[u]]}); u = parent[root[u]]; t++; } } ret.insert(ret.begin()+t,{pos[u],pos[v]}); return ret; } int lca(int u,int v){ for(;;v=parent[root[v]]){ if(pos[u]>pos[v])swap(u,v); if(root[u]==root[v])return u; } } int get_distance(int u,int v){ return depth[u] + depth[v] - 2 * depth[lca(u,v)]; } }; void dfs(int cur,vector<vector<int>> &E,vector<char> &cs,string &S,vector<int> &t,int cp){ if(S.size()==cp)return; int ii = -1; rep(i,E[cur].size()){ int to = E[cur][i]; if(cs[to]==S[cp]){ ii = to; break; } } if(ii==-1){ ii = E.size(); E.push_back(vector<int>()); E[cur].push_back(ii); cs.push_back(S[cp]); } t.push_back(ii); dfs(ii,E,cs,S,t,cp+1); } void dfs(int cur,int p,vector<vector<int>> &E){ rep(i,E[cur].size()){ int to = E[cur][i]; dfs(to,cur,E); } if(p!=-1)E[cur].push_back(p); } int main(){ int N; cin>>N; vector<string> S(N); rep(i,N){ cin>>S[i]; } vector<string> T = S; int Q; cin>>Q; vector<int> t(Q),x(Q); vector<char> c(Q); rep(i,Q){ cin>>t[i]>>x[i]; x[i]--; if(t[i]==1){ cin>>c[i]; T[x[i]] += c[i]; } } vector<vector<int>> E(1); vector<char> cs(1,'-'); vector<vector<int>> ind(N); rep(i,N){ vector<int> tt; dfs(0,E,cs,T[i],tt,0); ind[i] = tt; } dfs(0,-1,E); HLD H(E); fenwick_tree<long long> F(E.size()+5); //cout<<E.size()<<endl; rep(i,N){ rep(j,S[i].size()){ F.add(H.pos[ind[i][j]],1); } } rep(i,Q){ if(t[i]==1){ F.add(H.pos[ind[x[i]][S[x[i]].size()]],1); S[x[i]] += c[i]; } else{ int v = ind[x[i]][S[x[i]].size()-1]; int u = 0; auto ret = H.query(u,v); long long ans = 0; rep(j,ret.size()){ int l = ret[j].first,r = ret[j].second; if(l>r)swap(l,r); ans += F.sum(l,r+1); } cout<<ans<<endl; } } return 0; }