题意：3种操作分别为入队，出队，查询当前队列的中位数。操作数为1e5数量级。

思路：先考虑离线算法，可以离散+线段树，可以划分树，考虑在线算法，则有treap名次树，SBtree(size balanced tree)等等。

///这个模板有问题，别再用了。。。！！！！

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
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <queue>
using namespace std;
const int maxn = 1e5 + 7;
template<typename T> class SBTree {
public:
    SBTree() {
        root = nil = new Node();
        nil->ch[0] = nil->ch[1] = nil;
        nil->sz = 0;
        tot = top = 0;
    }
    ~SBTree() {}
 
    void clear() {
        root = nil; tot = top = 0;
    }
    int size() { return root->sz; }
    bool empty() { return root == nil; }
    void insert(const T &it) { insert(root, it); }
    void erase(const T &it) { erase(root, it); }
    bool find(const T &it) { return find(root, it); }
    const T &minItem() { return minMax(root, 0); }
    const T &maxItem() { return minMax(root, 1); }
    const T &select(int k) { return select(root, k); }
    int rank(const T &it) { return rank(root, it); }
 
private:
    const static int maxn = 1e4 + 7;
    struct Node {
        T key;
        int sz;
        Node *ch[2];
    } v[maxn], *stk[maxn], *root, *nil;
 
    int tot, top;
 
    void rotate(Node *&x, int d) {
        Node *y = x->ch[d ^ 1];
        x->ch[d ^ 1] = y->ch[d]; y->ch[d] = x;
        y->sz = x->sz; x->sz = x->ch[0]->sz + x->ch[1]->sz + 1;
        x = y;
    }
 
    void maintain(Node *&x, int d) {
        if (x == nil) return;
        if (x->ch[d]->sz < x->ch[d ^ 1]->ch[d ^ 1]->sz) rotate(x, d);
        else if (x->ch[d]->sz < x->ch[d ^ 1]->ch[d]->sz) {
            rotate(x->ch[d ^ 1], d ^ 1); rotate(x, d);
        } else {
            return;
        }
        maintain(x->ch[0], 1); maintain(x->ch[1], 0);
        maintain(x, 1); maintain(x, 0);
    }
 
    void insert(Node *&x, const T &it) {
        if (x == nil) {
            x = top ? stk[top--] : v + tot++;
            x->key = it; x->sz = 1;
            x->ch[0] = x->ch[1] = nil;
        } else {
            ++x->sz;
            insert(x->ch[x->key < it], it);
            maintain(x, it < x->key);
        }
    }
 
    void erase(Node *&x, const T &it) {
        Node *p;
        if (x == nil) return;
        --x->sz;
        if (it < x->key) erase(x->ch[0], it);
        else if (x->key < it) erase(x->ch[1], it);
        else {
            if (x->ch[1] == nil) {
                stk[++top] = x; x = x->ch[0];
            } else {
                for (p = x->ch[1]; p->ch[0] != nil; p = p->ch[0]);
                erase(x->ch[1], x->key = p->key);
            }
        }
    }
 
    bool find(const Node *x, const T &it) {
        if (x == nil || !(it < x->key || x->key < it)) return x != nil;
        return find(x->ch[x->key < it], it);
    }
 
    const T &minMax(const Node *x, int d) {
        return x->ch[d] == nil ? x->key : minMax(x->ch[d], d);
    }
 
    const T &select(const Node *x, int k) {
        if (x == nil || k == x->ch[0]->sz + 1) return x->key;
        return select(x->ch[x->ch[0]->sz + 1 < k], x->ch[0]->sz + 1 < k ? k - x->ch[0]->sz - 1 : k);
    }
 
    int rank(const Node *x, const T &it) {
        if (x == nil) return 1;
        if (it < x->key) return rank(x->ch[0], it);
        if (x->key < it) return rank(x->ch[1], it) + x->ch[0]->sz + 1;
        return x->ch[0]->sz + 1;
    }
};
SBTree<int> sbt;
int main() {
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
#endif // ONLINE_JUDGE
    int cas = 0, n;
    while (cin >> n) {
        printf("Case #%d:\n", ++ cas);
        sbt.clear();
        queue<int> Q;
        while (n --) {
            char s[10];
            scanf("%s", s);
            if (s[0] == 'i') {
                int x;
                scanf("%d", &x);
                sbt.insert(x);
                Q.push(x);
            }
            else if (s[0] == 'o') {
                int x = Q.front();
                Q.pop();
                sbt.erase(x);
            }
            else {
                int sz = Q.size();
                printf("%d\n", sbt.select(sz / 2 + 1));
            }
        }
    }
    return 0;
}

最新文章

  1. IOS开发基础知识--碎片19
  2. js抽奖跑马灯程序
  3. JavaEE EL的一些用法
  4. 文件的存储读写，XML文件的存储与读写
  5. c# 数据绑定之 DataFormatString 格式
  6. Spring MVC 之类型转换（五）
  7. Android Priority Job Queue (Job Manager)（一）
  8. Cocos2D-x培训课程
  9. devi into python 笔记（六）正则表达式 原始字符串
  10. 让乔布斯立足肩上的C语言之父
  11. GCD 倒计时
  12. 【Android LibGDX游戏引擎开发教程】第08期：中文字体的显示和绘制（下）
  13. shell执行php文件传递参数
  14. Python for循环之图像练习
  15. Mysql 分区（range，list，hash）转载
  16. Fata7y Ya Warda! SPOJ - DRUIDEOI 单调栈
  17. AppFog使用
  18. ubuntu禁止系统自动升级之界面操作
  19. [hadoop]mapreduce原理简述
  20. 040——VUE中组件之组件间的数据参props的使用实例操作

热门文章

  1. [YII2] 去除自带js，加载自己的JS，然后ajax（json）传值接值！
  2. golang依赖管理
  3. 移植seetafaceengine-master、opencv到ARM板
  4. beego rel/reverse
  5. python学习02python入门二
  6. Nginx四层代理
  7. 数据挖掘入门系列教程（十一）之keras入门使用以及构建DNN网络识别MNIST
  8. tx-Lcn 分布式事务
  9. Spring Boot中使用@JsonComponent
  10. Libra教程之:Libra协议的关键概念