Month: 2020年1月

2 篇文章

Luogu P3054 [USACO12OPEN]跑圈Running Laps 题解
题意 农夫约翰让他的$ n (1 \leq n \leq 100,000) $头牛在长度为$ c $的跑道上进行跑$ l $圈的比赛,所有牛从同一起点,以不同的速度开始跑。直到当跑得最快的那一头牛跑完$ l $圈时,所有牛才同时停下。 约翰发现在跑圈过程中发生了几次“超越事件”。其定义是:在比赛结束前某时刻,奶牛$ x $已经超越了奶牛$ y $整…
Splay平衡树 学习笔记
0 前言 突然想学$Link Cut Tree$了(当然不是因为我们班里有一个叫$LCT$的人 但是$LCT$有一个非常重要的前置知识,那就是$Splay$,于是就有了此篇文章。 1 Splay原理 BST 要想理解$splay$的原理,就得先理解$BST$。 二叉查找树(Binary Search Tree,简称BST)是一棵二叉树,它的左子节点…