弹飞绵羊LCT.doc
《弹飞绵羊LCT.doc》由会员分享,可在线阅读,更多相关《弹飞绵羊LCT.doc(3页珍藏版)》请在三一文库上搜索。
1、弹飞绵羊LCT题意:一共n个位置,每个位置一个属性ki,表示在i位置会被瞬间转移到i+ki(然后又依次转移)。问从一个点开始多少次会出界。并且支持修改ki。题解:把i向i+ki连边,若i+ki出界就向外面的总根连边。询问就是求深度。把一个节点splay到根之后(前提是根是原树最开始的根),左边一定是比它浅的(且一定是它到原树根的一条链(因为access操作),所以左儿子的size就是它的深度(根的深度为0)。居然以前要写一天的LCT半个小时就写好了,要不是BZOJ的编译器栈空间不够就1A了/*Problem: 2002User: Lazer2001Language: C+Result: Acc
2、eptedTIme:1988 msMemory:22324 kb*/# include bits/stdc+.hinline int read ( ) register int x, c ;while ( isspace ( c = getchar ( ) ) ) ;for ( x = -48 + c ; isdigit ( c = getchar ( ) ) ; ( x *= 10 ) += c - 48 ) ;return x ;template class T inline T min ( const T a, const T b ) return a b ? a : b ; templ
3、ate class T inline void swap ( T a, T b ) T c ( a ) ; a = b, b = c ; # define N 200010class LinkCutTree private :struct node int siz ;bool rev_flag ;node *ch 2, *fa ;inline void update ( ) siz = ch 0 - siz + ch 1 - siz + 1 ; pool N 1, *root N, *null ;int n ;inline void push_down ( node* p ) if ( p -
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 绵羊 LCT
链接地址:https://www.31doc.com/p-3436205.html