結果
問題 | No.2020 Sum of Common Prefix Length |
ユーザー |
![]() |
提出日時 | 2022-07-22 21:59:20 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 3,227 bytes |
コンパイル時間 | 2,235 ms |
コンパイル使用メモリ | 196,720 KB |
実行使用メモリ | 62,880 KB |
最終ジャッジ日時 | 2024-07-04 06:18:55 |
合計ジャッジ時間 | 18,031 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 1 WA * 3 RE * 34 |
ソースコード
#include <bits/stdc++.h>using namespace std;template <typename T>struct invertible_binary_indexed_tree{int N;vector<T> BIT;function<T(T, T)> f;function<T(T)> inv;T E;invertible_binary_indexed_tree(){}invertible_binary_indexed_tree(int N, function<T(T, T)> f, function<T(T)> inv, T E): N(N), BIT(N + 1, E), f(f), inv(inv), E(E){}void add(int i, T x){i++;while (i <= N){BIT[i] = f(BIT[i], x);i += i & -i;}}T sum(int i){T ans = E;while (i > 0){ans = f(ans, BIT[i]);i -= i & -i;}return ans;}T sum(int l, int r){return f(sum(r), inv(sum(l)));}};struct heavy_light_decomposition{vector<int> p, sz, in, next;invertible_binary_indexed_tree<int> BIT;void dfs1(vector<vector<int>> &c, int v){sz[v] = 1;for (int &w : c[v]){dfs1(c, w);sz[v] += sz[w];if (sz[w] > sz[c[v][0]]){swap(w, c[v][0]);}}}void dfs2(vector<vector<int>> &c, int &t, int v){in[v] = t;t++;for (int w : c[v]){if (w == c[v][0]){next[w] = next[v];} else {next[w] = w;}dfs2(c, t, w);}}heavy_light_decomposition(vector<int> &p, vector<vector<int>> &c, int r = 0): p(p){int N = p.size();sz = vector<int>(N);dfs1(c, r);in = vector<int>(N);next = vector<int>(N, r);int t = 0;dfs2(c, t, r);BIT = invertible_binary_indexed_tree<int>(N, plus<int>(), negate<int>(), 0);}void add(int p, int x){BIT.add(in[p], x);}int sum(int v){int ans = 0;while (next[v] != 0){ans += BIT.sum(in[next[v]], in[v] + 1);v = p[next[v]];}ans += BIT.sum(0, in[v] + 1);return ans;}};int main(){int N;cin >> N;vector<string> S(N);for (int i = 0; i < N; i++){cin >> S[i];}vector<int> L(N);for (int i = 0; i < N; i++){L[i] = S[i].size();}int Q;cin >> Q;vector<int> t(Q), x(Q);vector<char> c(Q);for (int i = 0; i < Q; i++){cin >> t[i];if (t[i] == 1){cin >> x[i] >> c[i];x[i]--;S[x[i]] += c[i];}if (t[i] == 2){cin >> x[i];x[i]--;}}int V = 1;vector<map<char, int>> trie(V);for (int i = 0; i < N; i++){int v = 0;int L2 = S[i].size();for (int j = 0; j < L2; j++){auto itr = trie[v].find(S[i][j]);int w;if (itr != trie[v].end()){w = (*itr).second;} else {w = V;trie[v][S[i][j]] = V;trie.push_back({});V++;}v = w;}}vector<int> pr(V, -1);vector<vector<int>> ch(V);for (int i = 0; i < V; i++){for (auto P : trie[i]){pr[P.second] = i;ch[i].push_back(P.second);}}heavy_light_decomposition HLD(pr, ch);vector<int> curr(N, 0);for (int i = 0; i < N; i++){for (int j = 0; j < L[i]; j++){curr[i] = trie[curr[i]][S[i][j]];HLD.add(curr[i], 1);}}for (int i = 0; i < Q; i++){if (t[i] == 1){curr[x[i]] = trie[curr[i]][L[x[i]]];L[x[i]]++;HLD.add(curr[x[i]], 1);}if (t[i] == 2){cout << HLD.sum(curr[x[i]]) << endl;}}}