【BZOJ1503】【NOI2004】郁闷的出纳员_cz_xuyixuan的博客-程序员宅基地

技术标签: 【数据结构】线段树  【数据结构】平衡树  【类型】做题记录  【OJ】BZOJ  

【题目链接】

【思路要点】

  • 随便用个平衡树、线段树、块状链表、std::vector之类的数据结构维护一下就行了。
  • 时间复杂度\(O(NLogN)\)或\(O(N\sqrt{N})\)。

【代码】

#include<stdio.h>
#define MAXN	200000
struct data {
	int left, right, father, size, v, num; 
} tree[MAXN]; 
int n, m, l, tot, root, delta; 
void pushup(int x) {
	tree[x].size = tree[tree[x].left].size+tree[tree[x].right].size+1; 
}
void zig(int &x) {
	int y = tree[x].father; 
	int z = tree[y].father; 
	if (y == tree[z].left) tree[z].left = x; 
	else tree[z].right = x; 
	tree[x].father = z; 
	tree[y].left = tree[x].right; 
	tree[tree[x].right].father = y; 
	tree[x].right = y; 
	tree[y].father = x; 
	pushup(y); 
	pushup(x); 
	if (y == root) root = x; 	
}
void zag(int &x) {
	int y = tree[x].father; 
	int z = tree[y].father; 
	if (y == tree[z].left) tree[z].left = x; 
	else tree[z].right = x; 
	tree[x].father = z; 
	tree[y].right = tree[x].left; 
	tree[tree[x].left].father = y; 
	tree[x].left = y; 
	tree[y].father = x; 
	pushup(y); 
	pushup(x); 
	if (y == root) root = x; 	
}
void splay(int &x) {
	while (tree[x].father != 0) {
		if (tree[tree[x].father].left == x) zig(x); 
		else zag(x); 
	}
}
void insert(int k) {
	if (root == 0) {
		root = ++tot; 
		tree[tot].num = k; 
		tree[tot].size = 1; 
		return; 
	}
	int p = root, z; 
	while (p != 0) {
		z = p; 
		tree[p].size++; 
		if (k<tree[p].num) p = tree[p].left; 
		else p = tree[p].right; 
	}
	if (k<tree[z].num) tree[z].left = ++tot; 
	else tree[z].right = ++tot; 
	tree[tot].num = k; 
	tree[tot].size = 1; 
	tree[tot].father = z; 
	splay(tot); 
}
int dec(int &x, int f)
{
	if (x == 0) return 0; 
	int k; 
	if (tree[x].num+delta<m) {
		k = dec(tree[x].right, x)+tree[tree[x].left].size+1; 
		tree[tree[x].right].size = tree[x].size-k; 
		x = tree[x].right; 
		tree[x].father = f; 
	}
	else {
		k = dec(tree[x].left, x); 
		tree[x].size -= k; 
	}
	return k; 
}
int find(int &x, int k) {
	if (k <= tree[tree[x].right].size) return find(tree[x].right, k); 
	if (k == tree[tree[x].right].size+1) return tree[x].num; 
	return find(tree[x].left, k-tree[tree[x].right].size-1); 
}
int main() {
	scanf("%d%d", &n, &m); 
	int k; 
	char c[1]; 
	for (int i = 1; i <= n; i++) {
		scanf("%s%d", &c, &k); 
		if (c[0] == 'I' and k >= m) insert(k-delta); 
		if (c[0] == 'A') delta += k; 
		if (c[0] == 'S') {delta -= k; l += dec(root, 0); }; 
		if (c[0] == 'F') printf("%d\n", k <= tree[root].size?find(root, k)+delta:-1); 
	}
	printf("%d\n", l); 
	return 0; 
}

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/qq_39972971/article/details/79359860

智能推荐

文本溢出截断省略_马优晨的博客-程序员宅基地

(1)单行文本溢出省略&lt;style&gt; .demo { white-space: nowrap; overflow: hidden; text-overflow: ellipsis; }&lt;/style&gt;&lt;body&gt; &lt;div class="demo"&gt;这是一段很长的文本&lt;/...

Toast显示和关闭自个控制的方法_xiaopihaierletian的博客-程序员宅基地

Toast信息提示框之所以在显示一定时间后会自动关闭,是因为在系统中有一个Toast队列。系统会依次从队列中取(出队列)一个Toast,并显示 它。在显示一段时间后,再关闭,然后再显示下一个Toast信息提示框。直到Toast队列中所有Toast都显示完为止。那么有些时候需要这个 Toast信息提示框长时间显示,直到需要关闭它时通过代码来控制,而不是让系统自动来关闭Toast信息提示框。不过这

互联网大数据公司排名_互联网上最好的数据科学课程,按照您的评论排名_cumian9828的博客-程序员宅基地

互联网大数据公司排名by David Venturi 大卫·文图里(David Venturi) 互联网上最好的数据科学课程,按照您的评论排名 (The best Data Science courses on the internet, ranked by your reviews)A year and a half ago, I dropped out of one of the bes...

Android 如何监听自己是否被卸载及卸载后打开的浏览器进行反馈功能的实现 --- 仿360卫士_chenchaotom的博客-程序员宅基地

一个应用被用户卸载肯定是有理由的,而开发者却未必能得知这一重要的理由,毕竟用户很少会主动反馈建议,多半就是用得不爽就卸,如果能在被卸载后获取到用户的一些反馈,那对开发者进一步改进应用是非常有利的。目前据我所知,国内的Android应用中实现这一功能的只有360手机卫士、360平板卫士,那么如何实现这一功能的?  我们可以把实现卸载反馈的问题转化为监听自己是否被卸载,只有得知自己被卸载,才可

看源代码那些事_打杂人的博客-程序员宅基地

摘要:1.前言很多人问我如何看源代码?是不是我在看源代码这方面特别有天赋?其实不是的,我也只是个普通人,跟大伙没啥分别,只不过我没有别的特别爱好,一有空时,不是写自己的代码就是看别人的代码,我在看源代码时比较有耐心,纯粹就是兴趣驱动,或者说是一种好奇心。当然,我不会随随便便拿起一个开源项目就看,而是经过一定了解后才决定看它的源代码的,一旦决定要看了,我至少要把这个开源项目80%以上的代码看完,并不

随便推点

dircms宽字节注入漏洞_Yatere的博客-程序员宅基地

//------------------------------------Name: dircmsSite: www.dircms.netDesc: 宽字节带来的注入问题Author: tojen (tojen.me at gmail.com)Date: 2010/3/8//--------------------------------------描述:无意间黑盒发现dircms存在宽字节带来的注入问题,虽然流行过一段时间,貌似现在人们都不太关注这个问题。测试了下发现有俩个地方存在问题:1.http:/

android view 存值,使用ViewModel保存数据_weixin_39542093的博客-程序员宅基地

使用viewModel保存数据,使App被系统kill后,再次启动依然可以恢复被kill前的数据下面的model = ViewModelProviders.of(this,new SavedStateViewModelFactory(this)).get(MyViewModel.class);api过时了,没有此方法了,仅记录下实现保存数据的思路1.导入implementation 'androi...

Nginx超简单教程,小白都能看得懂_Java旅途的博客-程序员宅基地

一 Nginx简介1.1 什么是NginxNginx是一个高性能的http和反向代理服务器,其特点是占用内存小,并发能力强。Nginx专为性能优化而开发,性能是其最重要的考量,能经受高负载的考验,有报告表明能支持高达50000个并发连接数。1.2 反向代理正向代理:在浏览器中配置代理服务器,通过代理服务器进行互联网访问。反向代理:将请求发送到反向代理服务器,由反向代理服务器去选择目标服务器获取数据后,再返回给客户端,此时反向代理服务器和目标服务器对外就是一个服务器,暴漏的是代理服务器地址。1.3

表达式求值_ToLoveToFeel的博客-程序员宅基地

表达式求值1. 表达式求值原理原理代码模板AcWing 151. 表达式计算4C++#include &lt;iostream&gt;#include &lt;stack&gt;using namespace std;stack&lt;int&gt; nums; // 存储数字stack&lt;char&gt; ops; // 存储运算符和括号int qmi(int a, int b) { int res = 1; while (b)

python修改文件夹名称_python os.renames()对文件和文件夹重命名和os.rename()类似,但比它强大,可以修改上级目录名..._weixin_39892615的博客-程序员宅基地

对这个函数还有点纳闷,有时试了可以,以为好了,再次测试时又不行了,感觉陷入怪圈一直走不出来,先记录下,以后再尝试import osos.renames("D://test/xx/a.txt", "D://test/22/a.txt")'''我的目录结构--D盘----test文件夹------xx文件夹--------2文件夹--------a.txt文件运行过后把我的xx里面的a.txt删掉了,...

MMPose_Arrow的博客-程序员宅基地

MMPose1. 简介1.1 功能列表1. 简介MMPose代码MMPose文档1.1 功能列表

推荐文章

热门文章

相关标签