题面

题目链接

大秦 为你打开 题目传送门

备用题面

有一个队列，现在对它进行n次操作，每次操作可以是下面三种中的一种：

“in x”：向队列中加入插入一个整数 $x(0 ≤x ≤10^9)$ 。

“out”：从队列中弹出一个数字。

“query”：从队列中查询中位数，例如队列中有 $m$ 个数字，则中位数是，升序排序后第 $floor(\cfrac m 2)+1$ 个数字。

初始队列为空。

思路

权值线段树模板题，直接在线段树上面跑二分，线段树的数值表示这段区间（指数字）数字的个数。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
#include<bits/stdc++.h>
using namespace std;

const int N = 100010;

class WgtSegTree {
    private: 
        struct Node {
            int L, R;
            int cnt;
            int num;
        }node[N << 2];
        int tot = 0;
    public: 
        void Build(int p, int L, int R) {
            node[p].L = L, node[p].R = R, node[p].cnt = 0;
            if(L == R) {
                node[p].num = ++tot;
                return ;
            }
            int mid = (L + R) >> 1;
            Build(p << 1, L, mid);
            Build(p << 1 | 1, mid + 1, R);
        }
        void Modify(int p, int x, int v) {
            if(node[p].L == node[p].R) {
                node[p].cnt += v;
                return ;
            }
            int mid = (node[p].L + node[p].R) >> 1;
            if(x <= mid) Modify(p << 1, x, v);
            else Modify(p << 1 | 1, x, v);
            node[p].cnt = node[p << 1].cnt + node[p << 1 | 1].cnt;
        }
        int Query(int p, int k) {
            if(node[p].L == node[p].R) {
                return node[p].num;
            }
            int mid = (node[p].L + node[p].R) >> 1;
            if(node[p << 1].cnt >= k) return Query(p << 1, k);
            else return Query(p << 1 | 1, k - node[p << 1].cnt);
        }
};

int n;
pair<string , int > a[N];

int b[N], tmp[N], len;
WgtSegTree tree;

void Input() {
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) {
        cin >> a[i].first;
        if(a[i].first == "in") {
            scanf("%d", &b[++len]);
            a[i].second = len;
            tmp[len] = b[len];
        }
    }
}

void Init() {
    sort(tmp + 1, tmp + len + 1);
    for(int i = 1; i <= n; i++) {
        if(a[i].first == "in") {
            a[i].second = lower_bound(tmp + 1, tmp + len + 1, b[a[i].second]) - tmp;
        }
    }
}

void Work() {
    Init();
    tree.Build(1, 1, len);
    queue<int >q;
    for(int i = 1; i <= n; i++) {
        if(a[i].first == "in") {
            tree.Modify(1, a[i].second, 1);
            q.push(a[i].second);
        }
        else if(a[i].first == "out") {
            tree.Modify(1, q.front(), -1);
            q.pop();
        }
        else {
            int k = tree.Query(1, (int)floor(q.size() / 2) + 1);
            printf("%d\n", tmp[k]);
        }
    }
}

int main() {
    Input();
    Work();
    return 0;
}