hdu 5249区间第k大（学习了下树状数组的搞法）

浏览数：28 / 时间：2015年06月08日

KPI

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 205 Accepted Submission(s): 70

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

Source

2015年百度之星程序设计大赛 - 初赛(1)

Recommend

hujie | We have carefully selected several similar problems for you: 5251 5250 5248 5247 5246

主席树随便搞搞就行。听别人说说树状数组也能搞，于是学习了下，果然神奇

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 1e4 + 10;
int c[maxn],tot;
void Modify(int x,int d)
{
	for(int i = x; i <= tot; i += i&-i) c[i] += d;
}
int findk(int k,int limt)
{
	int ans = 0,cnt = 0;
	for(int i = limt; i >= 0; i--) {
		ans += (1<<i);
		if(ans > tot || cnt + c[ans] >= k) ans -= (1<<i);
		else cnt += c[ans];
	}
	return ans + 1;
}
char Q[maxn];
int date[maxn],sorted[maxn];
int main(int argc, char const *argv[])
{
	int n;
	int cas = 1;
	while(scanf("%d",&n) == 1) {
		printf("Case #%d:\n",cas++);
		int cur = 1;
		for(int i = 1; i <= n; i++) {
			char cmd[10];
			scanf("%s",cmd);
			Q[i] = cmd[0];
			if(Q[i]=='i') {
				scanf("%d",date + cur);
				sorted[cur] = date[cur];
				++cur;
			}
		}
		tot = cur;
		memset(c,0,sizeof(c[0])*tot);
		sort(sorted+1,sorted+cur);
		int ql = 0,qr = 0;
		for(int i = 1; i <= n; i++) {
			if(Q[i]=='i') {
				++qr;
				int pos = lower_bound(sorted+1,sorted+cur,date[qr]) - sorted;
				Modify(pos,1);
			}else if(Q[i] == 'o') {
				++ql;
				int pos = lower_bound(sorted+1,sorted+cur,date[ql]) - sorted;
				Modify(pos,-1);
			}else {
				int k = (qr - ql + 2) >> 1;
				printf("%d\n",sorted[findk(k,18)]);
			}
		}
	}
	return 0;
}

郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。

hdu 5249区间第k大（学习了下树状数组的搞法）