【題解】CSES 1076. Sliding Median
===

###### tags: `競程` `題解` `資料結構`

參考資料：
- [ref1](https://www.luogu.com.cn/blog/Chanis/gnu-pbds)
- [ref2](https://usaco.guide/problems/cses-1076-sliding-median/solution)

---

## 作法一：兩個 multiset
以兩個動態排序的資料結構 $L$ $R$，分別維護前半小、後半大的，查詢時輸出中間切開的地方就行。
仔細地說，有奇數個元素時，中位數是 $\lceil \frac n 2 \rceil$，偶數個時，中位數是 $\frac n 2$。
使 $L$ 在 $n$ 為奇數時，比 $R$ 多一個，查詢時輸出 $L$ 的最後一個元素。

:::danger
這裏我踩到一個坑，就是 S.erase(x) 會把所有 x 刪除掉。
若只要刪除一個 x，使用 erase(S.lower_bound(x))
:::

int n, k, a[N];

multiset<int> L, R;

void era (int x)
{
    if (L.find(x) != L.end())
        L.erase(L.lower_bound(x));
    else
        R.erase(R.lower_bound(x));
}
void ins (int x)
{
    if (L.empty() || x<=*last(L))
        L.insert(x);
    else
        R.insert(x);
}
void bal ()
{
    while (R.size()>L.size())
    {
        L.insert(*R.begin());
        R.erase(R.begin());
    }
    while (L.size()-1>R.size())
    {
        R.insert(*last(L));
        L.erase(last(L));
    }
}

signed main()
{
    cin >> n >> k;
    rep(i,1,n) cin >> a[i];
    rep(i,1,n)
    {
        ins(a[i]);
        if (i>k) era(a[i-k]);
        bal();
        if (i>=k) cout << *last(L) << "\n "[i+1<=n];
    }
}

## 作法二：在值域線段樹上二分搜

- 找到最小的 $x$ 使 $cnt[1]+ \dots +cnt[x] \le \lceil \frac n 2 \rceil$

以 $cnt[x]$ 代表目前 $x$ 出現幾次。
當 $n$ 為奇數，取 $n/2+1$。當 $n$ 為偶數，取第 $n/2$ 個，因此找到第一個包含 $\lceil \frac n 2 \rceil$ 的 $cnt[1]+ \dots + cnt[x]$

- 在線段樹上二分搜：$query(u,k)$ 所代表區間 $[l,r]$ 中，最左的 $i$ 使得前綴至少為 $k$

if (sum[l[u]] >= k)
    return query(l[u],k)
else
    return query(r[u],k-sum[l[u]])

- 離散化

因為值域達 $10^9$，並且只關心數字間大小關係，所以離散化。

int n, k, a[N];

int v[N], m;
void lisan()
{
    rep(i,1,n) v[i] = a[i];
    sort(v+1,v+1+n);
    m = unique(v+1,v+1+n)-v-1;
    rep(i,1,n) a[i] = lower_bound(v+1,v+1+m,a[i])-v;
}

struct Seg
{
    int tr[N<<2];
    void modify (int p, int x, int u=1, int l=1, int r=m)
    {
        if (l==p && p==r)
        {
            tr[u] += x;
            return;
        }
        int mid = (l+r)/2;
        if (p<=mid) modify(p,x,u*2,l,mid);
        else modify(p,x,u*2+1,mid+1,r);
        tr[u] = tr[u*2] + tr[u*2+1];
    }
    int query (int x, int u=1, int l=1, int r=m)
    {
        if (l == r)
            return l;
        int mid = (l+r)/2;
        if (tr[u*2] >= x) return query(x,u*2,l,mid);
        else return query(x-tr[u*2],u*2+1,mid+1,r);
    }
} seg;

signed main()
{
    cin >> n >> k;
    rep(i,1,n) cin >> a[i];
    lisan();
    rep(i,1,n)
    {
        seg.modify(a[i],1);
        if (i > k)
            seg.modify(a[i-k],-1);
        if (i>=k)
            cout << v[seg.query((k-1)/2+1)] << "\n "[i+1<=n];
    }
}

## 作法三：支援 find_by_order 的資料結構

可以自己刻一顆 treap，或是使用 pbds。

食用 pbds 前：

#include <ext/extc++.h>
using namespace __gnu_pbds;

然後快樂的 AC 他：

typedef tree<
    pii,
    null_type,
    less<pii>,
    rb_tree_tag,
    tree_order_statistics_node_update
> trii;

int a[N], n, k;
trii tr;

signed main()
{
    cin >> n >> k;
    rep(i,1,n) cin >> a[i];
    rep(i,1,n)
    {
        tr.insert({a[i],i});
        if (i > k)
            tr.erase(tr.lower_bound({a[i-k],0}));
        if (i>=k)
            cout << tr.find_by_order((k-1)/2)->ff << "\n "[i+1<=n];
    }
}