生活随笔
收集整理的这篇文章主要介绍了
HDU-5249 KPI(STL or 权值线段树)
小编觉得挺不错的,现在分享给大家,帮大家做个参考.
题目链接
Problem Description
你工作以后, KPI 就是你的全部了. 我开发了一个服务，取得了很大的知名度。数十亿的请求被推到一个大管道后同时服务从管头拉取请求。让我们来定义每个请求都有一个重要值。我的KPI是由当前管道内请求的重要值的中间值来计算。现在给你服务记录，有时我想知道当前管道内请求的重要值得中间值。
Input
有大约100组数据。
每组数据第一行有一个n(1≤n≤10000)，代表服务记录数。
接下来有n行，每一行有3种形式
“in x”: 代表重要值为x(0≤x≤109)的请求被推进管道。
“out”: 代表服务拉取了管道头部的请求。
"query: 代表我想知道当前管道内请求重要值的中间值. 那就是说，如果当前管道内有m条请求, 我想知道，升序排序后第floor(m/2)+1th 条请求的重要值.
为了让题目简单，所有的x都不同，并且如果管道内没有值，就不会有"out"和"query"操作。
Output
对于每组数据，先输出一行
Case #i:
然后每一次"query"，输出当前管道内重要值的中间值。
Sample Input
6
in 874
query
out
in 24622
in 12194
query
Sample Output
Case #1:
874
24622
思路
- 权值线段树：更普通的线段树差不多将元素存在对应区间的位置上，例如5就存在父节点（l == r == 5）的节点上，这样就能查找区间第K大的元素。
- 用两个set(内部递增排序)模拟，添加和删除操作之后都要保持左set的长度(m/2+1)，这样方便询问的时候直接给出答案，而且不容易乱
#include <bits/stdc++.h>
#define LL long long
#define P pair<int, int>
#define lowbit(x) (x & -x)
#define mem(a, b) memset(a, b, sizeof(a))
#define rep(i, a, n) for (int i = a; i <= n; ++i)
#define maxn 10006
#define mid ((l + r) >> 1)
#define lc rt<<1
#define rc rt<<1|1
using namespace std
;map
<int, int> m1
;
map
<int, int> m2
;
int seg
[maxn
<< 2];
int a
[maxn
];void pushup
(int rt
) {seg
[rt
] = seg
[lc
] + seg
[rc
];
}void insert
(int rt
, int l
, int r
, int x
, int op
) {if (l
== r
) {seg
[rt
] += op
;return;}if (mid
>= x
) insert(lc
, l
, mid
, x
, op
);else insert(rc
, mid
+1, r
, x
, op
);pushup(rt
);
}int query(int rt
, int l
, int r
, int k
) {if (l
== r
) return l
;if (seg
[lc
] >= k
) return query(lc
, l
, mid
, k
);else return query(rc
, mid
+1, r
, k
- seg
[lc
]);
}
int main() {
#ifndef ONLINE_JUDGE
#endifint n
, d
, Case
= 1;char s
[10];while (scanf("%d", &n
) != EOF) {printf("Case #%d:\n", Case
++);mem(seg
, 0);priority_queue
<int> que
;queue
<int> que2
;m1
.clear();m2
.clear();for (int i
= 0; i
< n
; ++i
) {scanf("%s", s
);switch (s
[0]) {case 'i':scanf("%d", &a
[i
]);que
.push(a
[i
]);break;case 'o':a
[i
] = -1;break;case 'q':a
[i
] = -2; break;}}int pos
= que
.size();while (!que
.empty()) {m1
[que
.top()] = pos
;m2
[pos
] = que
.top();que
.pop();pos
--;}for (int i
= 0; i
< n
; ++i
) {if (a
[i
] >= 0) {insert(1, 1, n
, m1
[a
[i
]], 1);que2
.push(a
[i
]);}else if (a
[i
] == -1) {insert(1, 1, n
, m1
[que2
.front()], -1);que2
.pop();}else {pos
= query(1, 1, n
, que2
.size()/2 + 1);printf("%d\n", m2
[pos
]);}}}return 0;
}
#include <bits/stdc++.h>
#define LL long long
#define P pair<int, int>
#define lowbit(x) (x & -x)
#define mem(a, b) memset(a, b, sizeof(a))
#define rep(i, a, n) for (int i = a; i < n; ++i)
#define maxn 100005
using namespace std
;set
<int> st1
, st2
;
queue
<int> que
; int main() {
#ifndef ONLINE_JUDGE
#endifchar s
[10];int n
, d
, m
, Case
= 0;while (scanf("%d", &n
) != EOF) {printf("Case #%d:\n", ++Case
);while (!que
.empty()) que
.pop();st1
.clear();st2
.clear(); m
= 0;for (int i
= 0; i
< n
; ++i
) {scanf("%s", s
);if (s
[0] == 'i') {scanf("%d", &d
);if (st1
.empty() || *st1
.rbegin() > d
) st1
.insert(d
);else st2
.insert(d
);que
.push(d
);m
++;}else if (s
[0] == 'q') {printf("%d\n", *st1
.rbegin());}else {int tmp
= que
.front();que
.pop();if (st1
.find(tmp
) != st1
.end()) st1
.erase(tmp
);else st2
.erase(tmp
);m
--;}while (m
> 0 && st1
.size() > m
/2 + 1) {d
= *st1
.rbegin();st2
.insert(d
);st1
.erase(d
);}while (m
> 0 && st1
.size() < m
/2 + 1) {d
= *st2
.begin();st1
.insert(d
);st2
.erase(d
);}}}return 0;
}
总结
以上是生活随笔为你收集整理的HDU-5249 KPI(STL or 权值线段树)的全部内容，希望文章能够帮你解决所遇到的问题。
如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。
