- 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, χld[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<∫,μ<iset<∫〉 để 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ẽ ∈sert 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#∈clude<bitsstdc++.h>usingnamespacestd;typedeflonglong∫ll;#def∈epbpushback#def∈efifirst#def∈esesecondconstllmod