結果

問題 No.2020 Sum of Common Prefix Length
ユーザー SSRS
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#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;
}
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0