hdu1890 伸展树区间翻转复习

题意: 给你n个数,每次先输出第i大的数的位置(如果有多个,选下标小的那个),然后每次将第i个位置到第i大的数所在位置之间的数进行翻转。

思路:输入的数组可能有多个相同的值,我们可以进行两次排序把数组的值变为0---n-1(表示第几大)。

在建伸展树的时候我们可以顺便用pos[i]记录第i大的数的节点指针。

对于第i次操作,我们用flip记录翻转标记,每次先把第i大的节点pos[i]旋转到根,那么它的位置为i+左儿子的个数+1。然后左儿子打上翻转标记,最后删除根。

注意:下放懒惰标记时只要交换左右儿子的节点标号就可以了,也正因为这个原因,

下放函数的位置记得要放在没有引用任何左右儿子信息之前, 这跟区间其它操作最大的区别。

这次用指针写的,注意虚节点null 不能down, 因为null的左右儿子都为null 不能swap

#include #include #include using namespace std; struct node; node *null, *root; struct node { node *c[2], *fa; int sz, id; bool flip; bool d() { return fa->c[1] == this; } void fix(int d, node *x) { c[d] = x; x->fa = this; } void rot() { node *y = fa, *z = y->fa; int f = d(); z->fix(y->d(), this); y->fix(f, c[!f]); fix(!f, y); y->up(); } void splay(node *g) { while(fa != g) { node *y = fa, *z = y->fa; z->down(), y->down(),down(); if(z == g) rot(); else if(y->d() == d()) y->rot(), rot(); else rot(),rot(); } up(); if(g == null) root = this; } void up() { sz = c[0]->sz + c[1]->sz+1; } void down() { if(this==null) return; if(flip) { c[0]->flip ^= 1; c[1]->flip ^= 1; swap(c[0], c[1]); flip = 0; } } void out() {//debug printf("v%d ls%d rs%d lsz%d rsz%d fa%d\n", id, c[0]->id, c[1]->id, c[0]->sz, c[1]->sz, fa->id); } }; const int maxn = 100005; struct data { int val, id; bool operatorc[0] = x->c[1] = null, x->fa = fa; x->sz = 1, x->id = tot++, x->flip = 0; return x; } void build(node *&x, int l, int r, node *fa) { if( l > r ) return; int m = (l + r) >> 1; x = newNode(fa); pos[a[m].val] = x; build(x->c[0], l, m-1, x); build(x->c[1], m+1, r, x); x->up(); } void rto(int k, node *g) { node *x = root; while(true) { x->down(); int v = x->c[0]->sz+1; if(v == k) break; if(k > v) { k -= v; x = x->c[1]; }else x = x->c[0]; } x->splay(g); } void init(int n) { tot = 0; int i, j; for(i = 0; i sz = 0; root = null; build(root, 0, n-1, null); } void show(node *o) {//debug if(o==null) return; o->down(); o->out(); show(o->c[0]); show(o->c[1]); } void show() {//debug printf("root = %d\n", root->id); show(root); puts("~~~~~~"); } void work(int n) { int i; for(i = 0; i splay(null); printf("%d ", root->c[0]->sz+i+1); root->down(); root->c[0]->flip^=1; root->c[0]->down(); if(root->c[0]!=null) { rto(root->c[0]->sz, root); node *x = root; root = x->c[0]; root->fa = null; root->fix(1, x->c[1]); }else { root = root->c[1]; root->fa = null; } root->up(); } printf("%d\n", n); } }spt; int main() { int i, j, n; while(~scanf("%d", &n) && n) { spt.init(n); spt.work(n); } return 0; }

点击复制链接 与好友分享!回本站首页
您对本文章有什么意见或着疑问吗?请到论坛讨论您的关注和建议是我们前行的参考和动力
上一篇:Leetcode Symmetric Tree 递归和非递归解法
下一篇:POJ 3041 Asteroids 最小覆盖数
相关文章

POJ 3468 区间查询区间修改 伸展树

Codeforces 38G Queue 伸展树

POJ 1089 Intervals 区间覆盖+ 贪心

TYVJ P2065(区间嵌套与统计)

POJ 2355(区间最大值-zkw线段树优化D

POJ 3171(区间覆盖最小代价)

区间完全覆盖问题 &&区间均取最少2个

连号区间数

HDU3208(区间指数和)

区间dp-zoj3541-The Last Puzzle

图文推荐
hdu1890 伸展树区间翻转复习
ZOJ 3640 Help Me
hdu1890 伸展树区间翻转复习
CF 518C(Anya and
hdu1890 伸展树区间翻转复习
hdu 1016 Prime R
UVA - 11987 - A

分类:默认分类 时间:2012-01-07 人气:3
本文关键词:
分享到:

相关文章

Copyright (C) quwantang.com, All Rights Reserved.

趣玩堂 版权所有 京ICP备15002868号

processed in 0.037 (s). 10 q(s)