专栏首页wymhdu 5249 KPI 权值线段树裸题

hdu 5249 KPI 权值线段树裸题

#include <bits/stdc++.h>
using namespace std;
const int base = 200020;
const int maxn = 400020;
struct	T {
	int l,r,num,lazy;
} t[maxn*4]; // t[p] 表示值遇 l 到 r,num是该数出现次数
char s[10];
int minn,add;
void build(int p,int l,int r) {
	t[p].l = l;
	t[p].r = r;
	t[p].num = 0;
	t[p].lazy = 0;
	if(t[p].l==t[p].r) return ;
	int mid = (l+r)>>1;
	build(p*2,l,mid);
	build(p*2+1,mid+1,r);
}
void lazy(int p) {
	if(t[p].lazy==0)return ;
	else {
		t[p].lazy = 0; 
		t[p*2].lazy = 1;
		t[p*2].num = 0;
		t[p*2+1].lazy = 1;
		t[p*2+1].num = 0;
	}
}
void insert(int p,int v,int x) {
	if(t[p].l==t[p].r) {
		if(t[p].l==x) {
			t[p].num+=v;//插入就是出现次数++,删除就是--
		}
		return ;
	}
	lazy(p);
	int mid = (t[p].l+t[p].r)>>1;
	if(x<=mid)insert(p*2,v,x);
	else insert(p*2+1,v,x);
	t[p].num = t[p*2].num + t[p*2+1].num;
}

void update(int p,int x) { //工资低于x离开
	if(t[p].r<x) {
		t[p].num = 0;
		t[p].lazy = 1;
		return ;
	}
	if(t[p].l==t[p].r) {
		if(t[p].r<x)t[p].num = 0;
		return ;
	}
	lazy(p);
	int mid = (t[p].l+t[p].r)>>1;
	if(x<=mid) {
		update(p*2,x);
	} else {
		update(p*2,x);
		update(p*2+1,x);
	}
	t[p].num = t[p*2].num + t[p*2+1].num;
}
int ask(int p,int k) { //查询全局第 k 小,第 n - k + 1 大
//查询n - k + 1小则为查询第k大
	if(t[p].l==t[p].r)return t[p].l;
	lazy(p);
	if(k<=t[2*p].num)ask(p*2,k);
	else ask(p*2+1,k-t[p*2].num);
}
int main() {
	int kk,x,sum = 0;
	int cnt = 1;
	while(scanf("%d",&kk)>0) {
		queue<int> q;	while(!q.empty())q.pop();
		build(1,0,400100);
		printf("Case #%d:\n",cnt);cnt++;
		
		for(int i=0; i<kk; i++) {
			scanf("%s",s);
			if(s[0]=='i'){
				scanf("%d",&x);
				insert(1,1,x);
				q.push(x);
			}else if(s[0]=='o'){
				if(q.empty())continue;
				int x = q.front(); q.pop();
				insert(1,-1,x);
			}else {
				printf("%d\n",ask(1,t[1].num/2+1));
			} 
		}
	}


	return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 【BZOJ 1503】郁闷的出纳员【权值线段树】

    本题维护一个偏移量,当 A 操作时,不全都加工资 add+=x, S 操作 add-=x 。插入时x - add即可,这样仍然是全局偏移量。

    用户2965768
  • P1198 [JSOI2008]最大数 线段树入门

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 ...

    用户2965768
  • 南京网络预选赛 The Preliminary Contest for ICPC Asia Nanjing 2019 F 主席树 或 滑动窗口

    查询区间 [ id-k,id+k] 小于 val 的个数 num , 再在该区间查询第 num 大的数。

    用户2965768
  • hust Dating With Girls

    http://acm.sdibt.edu.cn:8080/judge/contest/view.action?cid=573#problem/B 题意:求最大权...

    用户1624346
  • Unique Paths

    问题:从起点到终点总共有多少条路径 分析:f[x,y]=f[x+1,y]+f[x,y+1],用记忆化搜索就可以解决了 class Solution { publ...

    用户1624346
  • 1021 个位数统计 (15 分)

    给定一个 k 位整数 N=dk−110k−1+⋯+d1101+d0 (0≤di≤9, i=0,⋯,k−1, dk−1>0),请编写程序统计每种不同的个位数字出现...

    可爱见见
  • 算24

    解题思路: n个数算24,必有两个数要先算。这两个数算的结果,和剩余n-2个数,就构成了n-1个数求24的问题。枚举先算的两个数,以及这两个数的运算方式。n...

    AI那点小事
  • HDU 5806

    思路:尺取法!!如果已经统计过的数中有k个数是不小于m的,那么后面再加上任意数,这个区间都符合要求。想通了这一点,这道题便好做了。 一发AC

    用户7727433
  • 【LeetCode第 162 场周赛】回顾

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY 版权协议,转载请附上原文出处链接和本声明。 ...

    韩旭051
  • BZOJ4636: 蒟蒻的数列(动态开节点线段树)

    attack

扫码关注云+社区

领取腾讯云代金券