結果
問題 | No.2020 Sum of Common Prefix Length |
ユーザー | 👑 emthrm |
提出日時 | 2022-07-22 22:32:58 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 206 ms / 2,000 ms |
コード長 | 7,696 bytes |
コンパイル時間 | 2,503 ms |
コンパイル使用メモリ | 220,904 KB |
実行使用メモリ | 82,432 KB |
最終ジャッジ日時 | 2024-07-04 07:05:05 |
合計ジャッジ時間 | 7,830 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
5,248 KB |
testcase_01 | AC | 1 ms
5,376 KB |
testcase_02 | AC | 1 ms
5,376 KB |
testcase_03 | AC | 2 ms
5,376 KB |
testcase_04 | AC | 3 ms
5,376 KB |
testcase_05 | AC | 3 ms
5,376 KB |
testcase_06 | AC | 3 ms
5,376 KB |
testcase_07 | AC | 47 ms
5,376 KB |
testcase_08 | AC | 47 ms
5,504 KB |
testcase_09 | AC | 45 ms
5,376 KB |
testcase_10 | AC | 51 ms
5,376 KB |
testcase_11 | AC | 47 ms
5,376 KB |
testcase_12 | AC | 45 ms
5,504 KB |
testcase_13 | AC | 46 ms
5,376 KB |
testcase_14 | AC | 47 ms
5,504 KB |
testcase_15 | AC | 53 ms
11,392 KB |
testcase_16 | AC | 53 ms
11,264 KB |
testcase_17 | AC | 109 ms
35,712 KB |
testcase_18 | AC | 88 ms
25,472 KB |
testcase_19 | AC | 93 ms
27,520 KB |
testcase_20 | AC | 163 ms
76,096 KB |
testcase_21 | AC | 191 ms
66,944 KB |
testcase_22 | AC | 196 ms
66,816 KB |
testcase_23 | AC | 187 ms
65,792 KB |
testcase_24 | AC | 201 ms
73,856 KB |
testcase_25 | AC | 206 ms
73,216 KB |
testcase_26 | AC | 103 ms
50,616 KB |
testcase_27 | AC | 2 ms
5,376 KB |
testcase_28 | AC | 48 ms
7,552 KB |
testcase_29 | AC | 49 ms
7,680 KB |
testcase_30 | AC | 50 ms
7,424 KB |
testcase_31 | AC | 148 ms
74,624 KB |
testcase_32 | AC | 156 ms
82,432 KB |
testcase_33 | AC | 104 ms
49,920 KB |
testcase_34 | AC | 70 ms
22,272 KB |
testcase_35 | AC | 69 ms
22,272 KB |
testcase_36 | AC | 110 ms
48,512 KB |
testcase_37 | AC | 87 ms
32,768 KB |
ソースコード
#define _USE_MATH_DEFINES #include <bits/stdc++.h> using namespace std; #define FOR(i,m,n) for(int i=(m);i<(n);++i) #define REP(i,n) FOR(i,0,n) #define ALL(v) (v).begin(),(v).end() using ll = long long; constexpr int INF = 0x3f3f3f3f; constexpr long long LINF = 0x3f3f3f3f3f3f3f3fLL; constexpr double EPS = 1e-8; constexpr int MOD = 1000000007; // constexpr int MOD = 998244353; constexpr int DY4[]{1, 0, -1, 0}, DX4[]{0, -1, 0, 1}; constexpr int DY8[]{1, 1, 0, -1, -1, -1, 0, 1}; constexpr int DX8[]{0, -1, -1, -1, 0, 1, 1, 1}; template <typename T, typename U> inline bool chmax(T& a, U b) { return a < b ? (a = b, true) : false; } template <typename T, typename U> inline bool chmin(T& a, U b) { return a > b ? (a = b, true) : false; } struct IOSetup { IOSetup() { std::cin.tie(nullptr); std::ios_base::sync_with_stdio(false); std::cout << fixed << setprecision(20); } } iosetup; struct HeavyLightDecomposition { std::vector<int> parent, subtree, id, inv, head; explicit HeavyLightDecomposition(const std::vector<std::vector<int>>& graph, const int root = 0) : graph(graph) { const int n = graph.size(); parent.assign(n, -1); subtree.assign(n, 1); dfs1(root); id.resize(n); inv.resize(n); head.assign(n, root); int cur_id = 0; dfs2(root, &cur_id); } template <typename Fn> void update_v(int u, int v, const Fn f) const { while (true) { if (id[u] > id[v]) std::swap(u, v); f(std::max(id[head[v]], id[u]), id[v] + 1); if (head[u] == head[v]) break; v = parent[head[v]]; } } template <typename F, typename G, typename T> T query_v(int u, int v, const F f, const G g, const T id_t) const { T left = id_t, right = id_t; while (true) { if (id[u] > id[v]) { std::swap(u, v); std::swap(left, right); } left = g(left, f(std::max(id[head[v]], id[u]), id[v] + 1)); if (head[u] == head[v]) break; v = parent[head[v]]; } return g(left, right); } template <typename Fn> void update_subtree_v(const int ver, const Fn f) const { f(id[ver], id[ver] + subtree[ver]); } template <typename T, typename Fn> T query_subtree_v(const int ver, const Fn f) const { return f(id[ver], id[ver] + subtree[ver]); } template <typename Fn> void update_e(int u, int v, const Fn f) const { while (true) { if (id[u] > id[v]) std::swap(u, v); if (head[u] == head[v]) { f(id[u], id[v]); break; } else { f(id[head[v]] - 1, id[v]); v = parent[head[v]]; } } } template <typename F, typename G, typename T> T query_e(int u, int v, const F f, const G g, const T id_t) const { T left = id_t, right = id_t; while (true) { if (id[u] > id[v]) { std::swap(u, v); std::swap(left, right); } if (head[u] == head[v]) { left = g(left, f(id[u], id[v])); break; } else { left = g(left, f(id[head[v]] - 1, id[v])); v = parent[head[v]]; } } return g(left, right); } template <typename Fn> void update_subtree_e(const int ver, const Fn f) const { f(id[ver], id[ver] + subtree[ver] - 1); } template <typename T, typename Fn> T query_subtree_e(const int ver, const Fn f) const { return f(id[ver], id[ver] + subtree[ver] - 1); } int lowest_common_ancestor(int u, int v) const { while (true) { if (id[u] > id[v]) std::swap(u, v); if (head[u] == head[v]) break; v = parent[head[v]]; } return u; } private: std::vector<std::vector<int>> graph; void dfs1(const int ver) { for (int i = 0; i < graph[ver].size(); ++i) { if (graph[ver][i] != parent[ver]) { parent[graph[ver][i]] = ver; dfs1(graph[ver][i]); subtree[ver] += subtree[graph[ver][i]]; if (subtree[graph[ver][i]] > subtree[graph[ver].front()]) { std::swap(graph[ver][i], graph[ver].front()); } } } } void dfs2(const int ver, int* cur_id) { id[ver] = (*cur_id)++; inv[id[ver]] = ver; for (const int e : graph[ver]) { if (e != parent[ver]) { head[e] = (e == graph[ver].front() ? head[ver] : e); dfs2(e, cur_id); } } } }; template <typename Abelian> struct FenwickTree { explicit FenwickTree(const int n, const Abelian ID = 0) : n(n), ID(ID), data(n, ID) {} void add(int idx, const Abelian val) { for (; idx < n; idx |= idx + 1) { data[idx] += val; } } Abelian sum(int idx) const { Abelian res = ID; for (--idx; idx >= 0; idx = (idx & (idx + 1)) - 1) { res += data[idx]; } return res; } Abelian sum(const int left, const int right) const { return left < right ? sum(right) - sum(left) : ID; } Abelian operator[](const int idx) const { return sum(idx, idx + 1); } int lower_bound(Abelian val) const { if (val <= ID) return 0; int res = 0, exponent = 1; while (exponent <= n) exponent <<= 1; for (int mask = exponent >> 1; mask > 0; mask >>= 1) { const int idx = res + mask - 1; if (idx < n && data[idx] < val) { val -= data[idx]; res += mask; } } return res; } private: const int n; const Abelian ID; std::vector<Abelian> data; }; struct Xor128 { int rand() { unsigned int t = x ^ (x << 11); x = y; y = z; z = w; return w = (w ^ (w >> 19)) ^ (t ^ (t >> 8)); } int rand(const int ub) { const int res = rand() % ub; return res < 0 ? res + ub : res; } int rand(const int lb, const int ub) { return lb + rand(ub - lb); } long long randll() { return (static_cast<unsigned long long>(rand()) << 32) | rand(); } long long randll(const long long ub) { const long long res = randll() % ub; return res < 0 ? res + ub : res; } long long randll(const long long lb, const long long ub) { return lb + randll(ub - lb); } private: unsigned int x = 123456789, y = 362436069, z = 521288629; unsigned int w = std::time(nullptr); } xor128; int main() { constexpr int C = 26; int n; cin >> n; vector<string> s(n); REP(i, n) cin >> s[i]; int q; cin >> q; vector<int> x(q); vector<char> c(q, '$'); REP(i, q) { int type; cin >> type >> x[i]; --x[i]; if (type == 1) cin >> c[i]; } int num = 0; REP(i, n) num += s[i].length(); REP(i, q) num += c[i] != '$'; vector<array<int, C>> trie(1); fill(ALL(trie.front()), -1); trie.reserve(num + 1); auto add = [&](int index, char c) -> int { if (trie[index][c - 'a'] == -1) { trie[index][c - 'a'] = trie.size(); trie.emplace_back(); fill(ALL(trie.back()), -1); } return trie[index][c - 'a']; }; vector<int> pos(n, 0); REP(i, n) for (char c : s[i]) pos[i] = add(pos[i], c); REP(i, q) { if (c[i] != '$') pos[x[i]] = add(pos[x[i]], c[i]); } fill(ALL(pos), 0); const int m = trie.size(); vector<vector<int>> graph(m); REP(i, m) REP(c, C) { if (trie[i][c] != -1) graph[i].emplace_back(trie[i][c]); } HeavyLightDecomposition hld(graph, 0); FenwickTree<ll> weight(m); REP(i, n) for (char c : s[i]) { pos[i] = trie[pos[i]][c - 'a']; weight.add(hld.id[pos[i]], 1); } REP(i, q) { if (c[i] == '$') { cout << hld.query_v(0, pos[x[i]], [&weight](const int l, const int r) -> ll { return weight.sum(l, r); }, [](const ll a, const ll b) -> ll { return a + b; }, 0LL) << '\n'; } else { pos[x[i]] = trie[pos[x[i]]][c[i] - 'a']; weight.add(hld.id[pos[x[i]]], 1); } } return 0; }