专栏首页wym【BZOJ 1503】郁闷的出纳员【权值线段树】

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

 维护全局信息,结点记录该值出现的次数。

 支持全局k最小值,可增加删除,查找前驱,后继。相对平衡树,代码简单,快。

当数据较大时,需要离散化。

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

输出+add - base就行,base 是防止负数出现

#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].num = 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 x){
	if(t[p].l==t[p].r){
		if(t[p].l==x){
			t[p].num++;//插入就是出现次数++,删除就是-- 
		}
		return ;
	}
	lazy(p);
	int mid = (t[p].l+t[p].r)>>1;
	if(x<=mid)insert(p*2,x);
	else insert(p*2+1,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;
	scanf("%d%d",&kk,&minn);
	build(1,0,400100);
	for(int i=0;i<kk;i++)
	{
		scanf("%s%d",s,&x);
		if(s[0] == 'I')
		{
			if(x < minn) continue;
			sum++;
			insert(1,x-add+base);//add为偏移量,不总体操作 加base防负数
		}
		else if(s[0] == 'A')	add += x;
		else if(s[0] == 'S')
		{
			add -= x;
			update(1,minn-add+base);
		}
		else{
			if(x > t[1].num) printf("-1\n");
			else printf("%d\n",ask(1,t[1].num-x+1)+add-base);
		}
	}
	printf("%d\n",sum-t[1].num);
	return 0;
}

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • hdu 5249 KPI 权值线段树裸题

    用户2965768
  • PTA 7-14 电话聊天狂人 二叉搜索树

    输入首先给出正整数N(≤10^​5​​),为通话记录条数。随后N行,每行给出一条通话记录。简单起见,这里只列出拨出方和接收方的11位数字构成的手机号码,其中以空...

    用户2965768
  • Java Set集合 HashSet

    HashSet存储对象,应重写hashCode()和equals()方法,以便更好控制集合中的这些元素

    用户2965768
  • 【LeetCode】面试题46. 把数字翻译成字符串

    给定一个数字,我们按照如下规则把它翻译为字符串:0 翻译成 “a” ,1 翻译成 “b”,……,11 翻译成 “l”,……,25 翻译成 “z”。一个数字可能有...

    韩旭051
  • 分治法

    版权声明:本文为博主原创文章,转载请注明博客地址: https://blog.csdn.ne...

    zy010101
  • 历届试题 幸运数

    1 3 5 7 9 …. 。这时,3为第2个幸运数,然后把所有能被3整除的序号位置的数删去。注意,是序号位置,不是那个数本身能否被3整除!! 删除的应该是5,1...

    AI那点小事
  • 185. [USACO Oct08] 挖水井

    185. [USACO Oct08] 挖水井 ★★   输入文件:water.in   输出文件:water.out 简单对比 时间限制:1 s   内存限制:...

    attack
  • 归并排序

    在课本上学到了归并排序,不过课本上写得有些模糊,所以查了一下,原本对某科已经失去了信心,不过发现某科C语言版的写得还挺好理解,于是就照着自己写了一个。代码可以自...

    用户1148523
  • 简单说说vue的父子组件,父子组件传值和vuex

    一、vue的父子组件之间是如何传值的? 首先呢,需要说说的是,vue既然有双向绑定,那为何会有父子组件之间的传值问题?这个问题也简单,vue的组件会供其他的vu...

    前端博客 : alili.tech
  • C语言之二级指针

    心跳包

扫码关注云+社区

领取腾讯云代金券