动态开点线段树写法

$O(\log^2n)$ 查询

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100000;
const int MAXAI = 1'000'000'000;
const int MAXTOT = 30 * MAXN;
int n, m;
int a[MAXN + 5];
// 动态开点线段树维护权值数组
int tot = 1;                            // 节点数量
int lson[MAXTOT + 5], rson[MAXTOT + 5]; // 左右子节点
int t[MAXTOT + 5];
void update(int now, int l, int r, int x, int y)
{
    if (l == r)
    {
        t[now] += y;
        return;
    }
    int mid = (l + r) / 2;
    if (x <= mid)
    {
        if (!lson[now])
            lson[now] = ++tot;
        update(lson[now], l, mid, x, y);
    }
    if (x > mid)
    {
        if (!rson[now])
            rson[now] = ++tot;
        update(rson[now], mid + 1, r, x, y);
    }
    t[now] = t[lson[now]] + t[rson[now]];
}
int query(int now, int l, int r, int x, int y)
{
    if (x <= l && r <= y)
        return t[now];
    int mid = (l + r) / 2;
    int res = 0;
    if (x <= mid && lson[now])
        res += query(lson[now], l, mid, x, y);
    if (y >= mid + 1 && rson[now])
        res += query(rson[now], mid + 1, r, x, y);
    return res;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    // 找中位数
    for (int i = 1; i <= n; i++)
    {
        update(1, 1, MAXAI, a[i], 1);
        if (i % 2 == 0)
            continue;
        int k = i / 2 + 1;
        // 找到排名为k的数是几
        int l = 1;
        int r = MAXAI;
        int ans = -1;
        while (l <= r)
        {
            int mid = (l + r) / 2;
            if (query(1, 1, MAXAI, 1, mid) >= k)
            {
                ans = mid;
                r = mid - 1;
            }
            else
                l = mid + 1;
        }
        cout << ans << "\n";
    }
    return 0;
}

$O(\log n)$ 查询

int dfs(int now, int l, int r, int k)
{
    if (l == r)
        return l;
    int mid = (l + r) / 2;
    if (t[lson[now]] >= k)
        return dfs(lson[now], l, mid, k);
    return dfs(rson[now], mid + 1, r, k - t[lson[now]]);
}
...

        int k = i / 2 + 1;
        // 找到排名为k的数是几
        cout << dfs(1, 0, MAXAI, k) << "\n";

中位数

对顶堆写法

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1000000;
int n;
int a[MAXN + 5];
// ql（大的优先） < qr（小的优先）
priority_queue<int> ql;
priority_queue<int> qr;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    if (n % 2 == 0)
        n--;
    ql.push(a[1]);
    cout << ql.top() << "\n";
    for (int i = 2; i <= n; i += 2)
    {
        // 放入a[i],a[i+1]
        if (a[i] <= ql.top())
            ql.push(a[i]);
        else
            qr.push(-a[i]);
        if (a[i + 1] <= ql.top())
            ql.push(a[i + 1]);
        else
            qr.push(-a[i + 1]);
        // 保证左边比右边多
        if (ql.size() < qr.size())
        {
            ql.push(-qr.top());
            qr.pop();
        }
        // 保证数量相差1
        while (ql.size() - qr.size() > 1)
        {
            qr.push(-ql.top());
            ql.pop();
        }
        cout << ql.top() << "\n";
    }
    return 0;
}

线段树写法

先离散化 a[]，然后用线段树维护每个数出现了几次，update(1,1,n,x,1) 来给 x 的出现次数加 1。然后在线段树上 dfs 找到第 $k$ 名是谁实现中位数。

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 500000;
int n, m;
int a[MAXN + 5];
int temp[MAXN + 5];
// 线段树：单点修改、区间查询（区间和）
int t[4 * MAXN + 5];

// 当前做到了树上的now号节点，当前节点对应的区间为 [l,r]
// 需要给第x个数加y
void update(int now, int l, int r, int x, int y)
{
    if (l == r)
    {
        t[now] += y;
        return;
    }
    int mid = (l + r) / 2;
    // 左子树 now*2,l,mid
    // 右子树 now*2+1,mid+1,r
    if (x <= mid)
        update(now * 2, l, mid, x, y);
    else
        update(now * 2 + 1, mid + 1, r, x, y);
    t[now] = t[now * 2] + t[now * 2 + 1];
}
int query(int now, int l, int r, int x, int y)
{
    //[l,r] 是 [x,y] 的子区间
    if (x <= l && r <= y)
        return t[now];
    int mid = (l + r) / 2;
    // 左子树 now*2,l,mid
    // 右子树 now*2+1,mid+1,r
    int res = 0;
    if (x <= mid)
        res += query(now * 2, l, mid, x, y);
    if (y > mid)
        res += query(now * 2 + 1, mid + 1, r, x, y);
    return res;
}
int dfs(int now, int l, int r, int k)
{
    if (l == r)
        return l;
    int mid = (l + r) / 2;
    if (t[now * 2] >= k)
        return dfs(now * 2, l, mid, k);
    else
        return dfs(now * 2 + 1, mid + 1, r, k - t[now * 2]);
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        temp[i] = a[i];
    }
    sort(temp + 1, temp + n + 1);
    for (int i = 1; i <= n; i++)
        a[i] = lower_bound(temp + 1, temp + n + 1, a[i]) - temp;
    // 找中位数
    update(1, 1, n, a[1], 1);
    int k = 1;
    cout << temp[a[1]] << '\n';
    if (n % 2 == 0)
        n--;
    for (int i = 2; i <= n; i += 2)
    {
        update(1, 1, n, a[i], 1);
        update(1, 1, n, a[i + 1], 1);
        k++;
        cout << temp[dfs(1, 1, n, k)] << "\n"; // 找到排名为k的数是几
    }
    return 0;
}

树状数组写法

下面给出的查第 $k$ 大数的写法是单次 $O(\log^2 n)$ 的，如果想要 $O(\log n)$ 实现，可以查看 http://wiki.33dai.cn/ds/fenwick/#tricks

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 500000;
int n, m;
int a[MAXN + 5];
int temp[MAXN + 5];
// 树状数组
int t[MAXN + 5];
int lowbit(int x)
{
    return x & (-x);
}
// 第x个数加k
void update(int x, int k)
{
    for (int i = x; i <= n; i += lowbit(i))
        t[i] += k;
}
// 返回前x个数的和
int query(int x)
{
    int res = 0;
    for (int i = x; i >= 1; i -= lowbit(i))
        res += t[i];
    return res;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        temp[i] = a[i];
    }
    sort(temp + 1, temp + n + 1);
    for (int i = 1; i <= n; i++)
        a[i] = lower_bound(temp + 1, temp + n + 1, a[i]) - temp;
    // 找中位数
    update(a[1], 1);
    int k = 1;
    cout << temp[a[1]] << '\n';
    if (n % 2 == 0)
        n--;
    for (int i = 2; i <= n; i += 2)
    {
        update(a[i], 1);
        update(a[i + 1], 1);
        k++;
        // 找到排名为k的数是几
        int l = 1;
        int r = n;
        int ans = -1;
        while (l <= r)
        {
            int mid = (l + r) / 2;
            if (query(mid) >= k)
            {
                ans = mid;
                r = mid - 1;
            }
            else
                l = mid + 1;
        }
        cout << temp[ans] << "\n";
    }
    return 0;
}