- **HINT 1:** Chú ý sau mỗi lần thực hiện hoạt động $1,$ set lúc trước bị thêm hoặc bớt $1$ phần tử. Hãy nghĩ xem khi đó trung vị set sẽ thay đổi như thế nào.<br>
#**HƯỚNG DẪN:**<br>
- Set được thiết kế con trỏ dựa theo con trỏ bidirectional iterator nên chỉ có thể $++;-$$-$ không linh hoạt như mảng, nên ta muốn từ $1$ set truy cập trung vị của nó sẽ mất $O(n).$<br>
- Do đó ta cần phải tìm nhanh trung vị set sau bằng việc biến đổi một ít trung vị của set trước khi cập nhật.<br>
- Để ý sau khi set thêm hoặc bớt phần tử, trung vị set (là $1$ phần tử khi set lẻ, lưu phần tử $\dfrac{n}{2}$ khi set chẵn) sẽ dịch sang trái, phải hoặc giữ nguyên.<br>
- Xét các trường hợp chẵn lẻ, với thêm, bớt của set ta có được công thức dịch chuyển của trung vị.<br>
**CHÚ Ý:** Khi xóa phần tử có thể xóa luôn vào iterator của trung vị set trước, khi đó iterator đang trỏ đến sẽ bị vô hiệu, nên hãy cập nhật trung vị trước khi xóa.
##**CODE MẪU:**
```cpp
#include<iostream>
#include<set>
#include<iomanip>
using namespace std;
set<int> st;
set<int>::iterator it,it1;
int n,x,i,d,m;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cin>>n;
while(n--)
{
cin>>i;
if(i==1)
{
cin>>x;
if(d==0) {st.insert(x),it=st.begin(),d++;continue;}
it1=st.find(x);
if(it1==st.end())
{
st.insert(x);
if(d%2==1&&x<*it) it--;
if(d%2==0&&x>*it) it++;
d++;
}
else
{
if(d%2&&(x>=*it)) it--;
if(d%2==0&&x<=*it) it++;
st.erase(it1);
d--;
}
}
else
{
//cout<<d<<"\n";
if(d%2==0)
{
m=*it+*next(it);
if(m%2) cout<<setprecision(1)<<fixed<<m/2.0<<"\n";
else cout<<m/2<<"\n";
}
else cout<<*it<<"\n";
}
}
}
```
*Có một cách khác là lưu cùng lúc $2$ set lưu phần tử trước trung vị và sau trung vị, khi đó chỉ cần cập nhật đầu set sau và cuối set đầu.
sharinganvanhoadong
Created at
0 likes