lct – Tgotp-Blog

4817: [Sdoi2017]树点涂色

c++代码如下:

 

2002: [Hnoi2010]Bounce 弹飞绵羊

难点大概在建图上。

对于一个点x,把其连在他能跳的点下,也就是说,这是个有根树。

那么我们之前的destroy必须修改一下,

对于删除(x,y),因为y一定是由x得到,那么就有,deep[x]>deep[y]

那么将y splay到根,删除其右子树。

对于查询答案[......]

Read more

2049: [Sdoi2008]Cave 洞穴勘测

好blog推荐http://blog.csdn.net/tgop_knight/article/details/44539555

 

关于lct:

我的理解是:就是树链剖分写成了splay版本,另外将轻重链的划分由重儿子改成了偏爱儿子,即最后一次操作时所到的点

然后[......]

Read more