Ở truy vấn $1$, việc lưu mảng sau khi chèn $a$ phần tử $x$ trong khi $a$ có thể lên tới $10^9$ là không khả thi.
Thay vào đó, ta có thể lưu số lần xuất hiện giá trị sau mỗi truy vấn loại $1$ hoặc loại $2$.
Vì $x$ có thể lên tới $10^9$ nên ta sẽ lưu bằng $\color{red}{map}$ (Ở đây vì chỉ cần truy xuất nên mình dùng $\color{green}{unordered}$ _ $\color{green}{map}$).
Để thực hiện các truy vấn loại $3$, ta cần lưu các số lần xuất hiện, trong mỗi giá trị là mảng
chứa các giá trị có số lần xuất hiện đó. Sau đó, lấy số lần xuất hiện lớn nhất và giá trị lớn
nhất có số lần xuất hiện đó.
Ta có thể dùng một $\color{red}{map}$ với $value$ trong mỗi $key$ là một $\color{orange}{set}$ chứa các giá trị xuất hiện.
Khi đó kết quả truy vấn là phần tử cuối cùng của $set$ trong phần tử cuối cùng của $\color{red}{map}$.
Lưu ý là vì phải xếp tăng dần nên không được dùng $\color{green}{unordered}$ _ $\color{green}{map}$ hay $\color{blue}{unordered}$ _ $\color{blue}{set}$.
Độ phức tạp: $O(n.log(n))$, bao gồm q truy vấn là $O(n)$, các thao tác với $\color{red}{map}$, $\color{orange}{set}$ là $O(log(n))$, với $\color{green}{unordered}$ _ $\color{green}{map}$ là $O(1)$.
ℂ𝕠𝕕𝕖 tham khảo:
```
#include <iostream>
#include <vector>
#include <unordered_map>
#include <map>
#include <set>
int main(){
std::ios_base::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
int q, n, x; std::cin>>q;
long long y;
std::unordered_map<int, long long> f;
std::map<long long, std::set<int>> a;
while(q--){
std::cin>>n;
if (n == 1){
std::cin>>x>>y;
auto it = a[f[x]].find(x);
if (it != a[f[x]].end()) a[f[x]].erase(it);
//Khi thêm a phần tử x thì xóa giá trị đó khỏi số lần xuất hiện cũ.
if (a[f[x]].empty()) a.erase(f[x]);
//Nếu giá trị đó là giá trị duy nhất có số lần xuất hiện như vậy thì xóa số lần xuất hiện.
f[x] += y;
a[f[x]].insert(x);
//Thêm vào giá trị xuất hiện mới
}
else if (n == 2){
std::cin>>x>>y;
auto it = a[f[x]].find(x);
if (it != a[f[x]].end()) a[f[x]].erase(it);
//Tương tự, khi xóa a phần tử x thì xóa giá trị đó khỏi số lần xuất hiện cũ.
if (a[f[x]].empty()) a.erase(f[x]);
//Tương tự.
if (y >= f[x]) f[x] = 0;
else{
f[x] -= y;
a[f[x]].insert(x);
}
//Thêm vào giá trị xuất hiện mới
}
else std::cout<< *a.rbegin()->second.rbegin() <<'\n';
// Truy vấn 3: xuất kết quả lớn nhất
}
return 0;
}
```
~(Giải vì hùa theo)~
minhnhatha
Created at
3 likes