MyException - 我的异常网
当前位置:我的异常网» VSTS » [codevs 1343] 蝗虫(省队选拔赛湖南)

[codevs 1343] 蝗虫(省队选拔赛湖南)

www.myexceptions.net  网友分享于:2015-02-08  浏览:0次
[codevs 1343] 蚱蜢(省队选拔赛湖南)

http://codevs.cn/problem/1343/

题解:

本题splay基本操作:

1.如果是左跳,比如从 x 左跳到 y,就相当于查询 [ y, x ) 区间的最大值,那么就把 y-1 伸展到根,把 x 伸展到根的右节点,那么根的右节点的左节点对应的就是这段区间。

1.如果是右跳,比如从 x 右跳到 y,就相当于查询 ( x, y ] 区间的最大值,那么就把 x 伸展到根,把 y+1 伸展到根的右节点,那么根的右节点的左节点对应的就是这段区间。

3.这里 splay 是要将某个位置的节点伸展到给定位置,所以采用从顶向下查询第 rank 个的方式伸展,见代码。

4.remove操作:删除第 k 个,就把第 k-1 个伸展到根,把第 k+1 个伸展到根的右节点,删除它的左节点即可。别忘记 update 操作。

5.insert操作:如果要插到第 k 处,就把第 k-1 个节点旋转到根,把第 k 个节点旋转到根的右节点,那么插入到根的右节点的左节点就可以代替原来的第 k 个。好像没必要像我分两种情况。最后别忘 update,先子节点再根节点。

6.move操作:就是先 remove 再 insert。

7.宏定义:因为用到大量的根节点的左右节点的调用,而这里还不适合用引用,所以干脆定义了宏,简单清楚,编程效果好了很多。

8.边界防溢出:因为1、2中的将 y-1、y+1 伸展到根都是危险操作,因为 y 有可能等于 1 或 n,而 0 节点不能成为根节点,因为0节点默认为空;n+1 节点直接溢出,所以建立两个虚拟节点,一个为1,一个为 n+1,分别放在开头和末尾,对编程本身没影响,但不用担心溢出了,不过各个节点相应的位置就变了,读入位置 x 后 x++ 就行了。


代码:

总时间耗费: 6439ms 
总内存耗费: 3 kB

有些慢,但内存耗的很少。

#include<cstdio>
#include<algorithm>
using namespace std;

const int INF = 1e9 + 7;
const int maxn = 100000 + 10;

int root, ch[maxn][2], v[maxn], s[maxn], maxv[maxn];

void update(int o) {
	maxv[o] = max(v[o], maxv[ch[o][0]]);
	maxv[o] = max(maxv[o], maxv[ch[o][1]]);
	s[o] = s[ch[o][0]] + s[ch[o][1]] + 1;
}

int cmp(int o, int k) {
	int sum = s[ch[o][0]] + 1;
	if(sum == k) return -1;
	return k < sum ? 0 : 1;
}

void rotate(int& o, int d) {
	int k = ch[o][d^1]; ch[o][d^1] = ch[k][d]; ch[k][d] = o;
	update(o); update(k); o = k;
}

void splay(int& o, int k) {
	int d = cmp(o, k);
	if(d == -1) return;
	if(d == 1) k -= s[ch[o][0]] + 1;
	int p = ch[o][d];
	int d2 = cmp(p, k);
	int k2 = (d2 == 0) ? k : k - s[ch[p][0]] - 1;
	if(d2 != -1) {
		splay(ch[p][d2], k2);
		if(d2 == d) rotate(o, d^1); else rotate(ch[o][d], d);
	}
	rotate(o, d^1);
}

void build(int l, int r, int pa) {
	if(l > r) return;
	if(l == r) { 
		maxv[l] = v[l]; s[l] = 1; 
		if(l < pa) ch[pa][0] = l; else ch[pa][1] = l;
		return;
	} 
	int m = (l+r) >> 1; maxv[m] = v[m];
	build(l, m-1, m); build(m+1, r, m); update(m);
	if(m < pa) ch[pa][0] = m; else ch[pa][1] = m;
}

#define lc ch[root][0]
#define rc ch[root][1]

void move(int x, int y) {
	splay(root, x-1); splay(rc, x-s[lc]); //x+1 - (s[lc]+1)
	int o = ch[rc][0];
	ch[rc][0] = 0; //remove
	update(rc);
	if(x < y) {
		splay(root, y-1); 
		splay(rc, y-s[lc]-1); //y - (s[lc]+1)
		ch[rc][0] = o; update(rc); update(root); //notice
	} else {
		splay(root, y); 
		splay(lc, y-1); //
		ch[lc][1] = o; update(lc); update(root);
	}
}

int main() {
	int n, m; 
	scanf("%d%d", &n, &m); 
	for(int i = 2; i <= n+1; i++) scanf("%d", &v[i]); 
	build(1, n+2, 0); 
	root = (n+3) >> 1;
	
	for(int i = 1; i <= m; i++) {
		int x, k; 
		char cmd[1]; 
		scanf("%d%s%d", &x, &cmd, &k); 
		x++;
		switch(cmd[0]) {
			case 'L': {
				splay(root, x-k-1); 
				splay(rc, x-s[lc]-1); //x - (s[lc]+1)
				printf("%d\n", maxv[ch[rc][0]]); 
				move(x, x-k);
				break; 
			}
			case 'D': {
				splay(root, x); 
				splay(rc, x+k-s[lc]); //x+k+1 - (s[lc]+1)
				printf("%d\n", maxv[ch[rc][0]]); 
				move(x, x+k);
				break;
			}
		}
	}
	
	return 0; 
}


文章评论

一个程序员的时间管理
一个程序员的时间管理
程序员都该阅读的书
程序员都该阅读的书
如何区分一个程序员是“老手“还是“新手“?
如何区分一个程序员是“老手“还是“新手“?
我跳槽是因为他们的显示器更大
我跳槽是因为他们的显示器更大
那些争议最大的编程观点
那些争议最大的编程观点
10个调试和排错的小建议
10个调试和排错的小建议
那些性感的让人尖叫的程序员
那些性感的让人尖叫的程序员
60个开发者不容错过的免费资源库
60个开发者不容错过的免费资源库
什么才是优秀的用户界面设计
什么才是优秀的用户界面设计
程序员眼里IE浏览器是什么样的
程序员眼里IE浏览器是什么样的
2013年中国软件开发者薪资调查报告
2013年中国软件开发者薪资调查报告
程序员的鄙视链
程序员的鄙视链
聊聊HTTPS和SSL/TLS协议
聊聊HTTPS和SSL/TLS协议
我是如何打败拖延症的
我是如何打败拖延症的
亲爱的项目经理,我恨你
亲爱的项目经理,我恨你
初级 vs 高级开发者 哪个性价比更高?
初级 vs 高级开发者 哪个性价比更高?
要嫁就嫁程序猿—钱多话少死的早
要嫁就嫁程序猿—钱多话少死的早
2013年美国开发者薪资调查报告
2013年美国开发者薪资调查报告
为什么程序员都是夜猫子
为什么程序员都是夜猫子
代码女神横空出世
代码女神横空出世
编程语言是女人
编程语言是女人
写给自己也写给你 自己到底该何去何从
写给自己也写给你 自己到底该何去何从
总结2014中国互联网十大段子
总结2014中国互联网十大段子
每天工作4小时的程序员
每天工作4小时的程序员
我的丈夫是个程序员
我的丈夫是个程序员
中美印日四国程序员比较
中美印日四国程序员比较
10个帮程序员减压放松的网站
10个帮程序员减压放松的网站
做程序猿的老婆应该注意的一些事情
做程序猿的老婆应该注意的一些事情
不懂技术不要对懂技术的人说这很容易实现
不懂技术不要对懂技术的人说这很容易实现
5款最佳正则表达式编辑调试器
5款最佳正则表达式编辑调试器
旅行,写作,编程
旅行,写作,编程
老程序员的下场
老程序员的下场
为啥Android手机总会越用越慢?
为啥Android手机总会越用越慢?
程序员最害怕的5件事 你中招了吗?
程序员最害怕的5件事 你中招了吗?
程序员周末都喜欢做什么?
程序员周末都喜欢做什么?
Java 与 .NET 的平台发展之争
Java 与 .NET 的平台发展之争
程序员必看的十大电影
程序员必看的十大电影
Web开发者需具备的8个好习惯
Web开发者需具备的8个好习惯
Java程序员必看电影
Java程序员必看电影
看13位CEO、创始人和高管如何提高工作效率
看13位CEO、创始人和高管如何提高工作效率
当下全球最炙手可热的八位少年创业者
当下全球最炙手可热的八位少年创业者
团队中“技术大拿”并非越多越好
团队中“技术大拿”并非越多越好
“懒”出效率是程序员的美德
“懒”出效率是程序员的美德
Web开发人员为什么越来越懒了?
Web开发人员为什么越来越懒了?
程序员的一天:一寸光阴一寸金
程序员的一天:一寸光阴一寸金
程序员应该关注的一些事儿
程序员应该关注的一些事儿
程序员和编码员之间的区别
程序员和编码员之间的区别
科技史上最臭名昭著的13大罪犯
科技史上最臭名昭著的13大罪犯
老美怎么看待阿里赴美上市
老美怎么看待阿里赴美上市
软件开发程序错误异常ExceptionCopyright © 2009-2015 MyException 版权所有