【題解】CSES 1076. Sliding Median

作法一：兩個 multiset

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

這裏我踩到一個坑，就是 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];
    }
}