- Kiến thức cần biết: Trie.
- Lời giải:
- Cây Trie cho truy vấn dạng 1 / 3:
-> Một node trên cây Trie sẽ bao gồm 2 giá trị: `cnt` = số lần node được đi qua trên đường đi một xâu hoàn chỉnh trên cây Trie, `child[x]` = chỉ số node của con nối với đỉnh qua cạnh có trọng số `x`.
-> Với truy vấn dạng 1, ta đơn giản là `add` một xâu đã đảo ngược vào cây Trie như một bài toán Trie cơ bản ( lưu ý cần tăng cnt lên 1 của mỗi đỉnh khi duyệt cây ).
-> Với truy vấn dạng 3, ta sẽ lấy xâu từ truy vấn trước rồi ( ta sẽ lưu xâu sau mỗi truy vấn ) duyệt cây Trie như phép `add`, chỉ khác là thay vì ta tăng `cnt` của mỗi đỉnh thì ta sẽ giảm `cnt` của mỗi đỉnh đi 1 khi duyệt cây.
- Cây Trie cho truy vấn dạng 2:
-> Để xử lí nhanh truy vấn dạng 2, ta sẽ có 1 `map<int,multiset<int>>` để lưu `mp[h]` là tập hợp số lần đi qua của một node trên cây Trie có độ cao `h`.
-> Việc lưu này tương đương với `mp[h]` là số lần xuất hiện của từng hậu tố độ dài `h`.
-> Với mỗi truy vấn dạng 1 / 3, mỗi khi ta duyệt đến một đỉnh, trước khi thay đổi giá trị của đỉnh đó, ta sẽ tiến hành xóa số lần xuất hiện của đỉnh đó tại tập hợp số lần xuất hiện của hậu tố có độ cao của nó.
-> Giả sử node đang xét có độ cao `h`, số lần xuất hiện là `cnt`, ta sẽ `erase` giá trị `cnt` ra khỏi tập `mp[h]`.
-> Sau khi ta xóa xong giá trị này, ta sẽ `insert` vào tập hợp `--cnt` hoặc `++cnt` ( tùy thuộc vào loại truy vấn ).
- Xử lí truy vấn dạng 2:
-> Với mỗi truy vấn `k` và `l`, ta chỉ cần kiểm tra xem `mp[l]` có giá trị lớn nhất trong tập hợp lớn hơn hoặc bằng `k` hay không, nếu có thì `YES`, nếu không thì `NO`.
- Code ví dụ:
```cpp
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define pb push_back
#define fi first
#define se second
const ll mod = 1e9+7, mxn = 1e5+7;
//node trong cây Trie
struct node
{
ll cnt, c[26];
node() {for (ll i = 0; i < 26; i++) {c[i] = 0;} cnt = 0;}
};
ll q;
vector<node> trie; //cây Trie
vector<string> qx; //mảng lưu lại xâu trong các truy vấn
map<ll,multiset<ll>> mp; //tập hợp số lần xuất hiện của node có độ cao h
void add(string& s) //truy vấn dạng 1
{
ll u = 0, h = 0; //u là đỉnh đang xét, h là độ cao của đỉnh đang xét
for (ll i = 0; i < s.size(); i++)
{
if (!trie[u].c[s[i]-'a']) {trie.pb(node()); trie[u].c[s[i]-'a'] = trie.size()-1;}
if (mp[h].size()) //nếu mp[h] tồn tại giá trị
{
multiset<ll>::iterator pointer = mp[h].lower_bound(trie[u].cnt); //pointer của giá trị >= cnt hiện tại
if (pointer != mp[h].end() && *pointer == trie[u].cnt) mp[h].erase(pointer); //nếu giá trị này == cnt thì xóa
}
trie[u].cnt++; mp[h].insert(trie[u].cnt); //tăng cnt lên 1 rồi add vào tập hợp độ cao h
h++; u = trie[u].c[s[i]-'a']; //tăng độ cao và chuyển node đang xét tới node con để tiếp tục xét
}
//xử lí cho node lá (tương tự bên trên)
if (mp[h].size())
{
multiset<ll>::iterator pointer = mp[h].lower_bound(trie[u].cnt);
if (pointer != mp[h].end() && *pointer == trie[u].cnt) mp[h].erase(pointer);
}
trie[u].cnt++; mp[h].insert(trie[u].cnt);
}
void rmv(string& s) //truy vấn dạng 3
{
//tương tự truy vấn dạng 1
ll u = 0, h = 0;
for (ll i = 0; i < s.size(); i++)
{
if (mp[h].size())
{
multiset<ll>::iterator pointer = mp[h].lower_bound(trie[u].cnt);
if (pointer != mp[h].end() && *pointer == trie[u].cnt) mp[h].erase(pointer);
}
trie[u].cnt--;
if (trie[u].cnt) mp[h].insert(trie[u].cnt); //do l >= 1 nên ta k cần lưu l = 0
h++; u = trie[u].c[s[i]-'a'];
}
if (mp[h].size())
{
multiset<ll>::iterator pointer = mp[h].lower_bound(trie[u].cnt);
if (pointer != mp[h].end() && *pointer == trie[u].cnt) mp[h].erase(pointer);
}
trie[u].cnt--;
if (trie[u].cnt) mp[h].insert(trie[u].cnt);
}
void query(ll& k, ll& l) //truy vấn dạng 2
{
if (mp[l].empty()) {cout << "NO" << '\n';} //nếu tập hợp trống
else if (*mp[l].rbegin() >= k) {cerr << *mp[l].rbegin(); cout << "YES" << '\n';} //nếu tập hợp có phần tử lớn nhất >= k
else {cerr << *mp[l].rbegin(); cout << "NO" << '\n';} //nếu tập hợp có phần tử lớn nhất < k
}
signed main()
{
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> q; trie.pb(node());
while (q--)
{
int type; cin >> type;
if (type == 1)
{
string s; cin >> s; reverse(s.begin(),s.end());
qx.pb(s); add(s); //lưu xâu trong các truy vấn lại
}
else if (type == 2)
{
ll k, l; cin >> k >> l;
query(k,l); qx.pb("0"); //lưu xâu trắng vì truy vấn dạng 3 xét trên truy vấn thứ i
}
else
{
ll x; cin >> x;
rmv(qx[x-1]); qx.pb("0"); //tương tự truy vấn 2
}
}
}
```
shiron104
Created at
21 likes