利用了 KMP 性质和 SAM 这一“数据结构”的特点并进行了动态维护。 题目描述 对于一个字符串 $S$,我们定义 $fail[i]$,表示最大的 $x$ 使得 $S[1..x]=S[i-x+1..i]$,满足 $(x<i)$。 显然对于一个...
树链剖分
洛谷 P1505 旅游 题解 【树链剖分】【线段树】
是一个对边剖分的树剖题。 题目描述 Ray 乐忠于旅游,这次他来到了 T 城。T 城是一个水上城市,一共有\(N\)个景点,有些景点之间会用一座桥连接。为了方便游客到达每个景点但又为了节约...
洛谷 P2486 [SDOI2011]染色 题解【树链剖分】【线段树】
感觉树剖挺好用的 题目描述 给定一棵有n个节点的无根树和m个操作,操作有2类: 将节点a到节点b路径上所有点都染成颜色c; 询问节点a到节点b路径上的颜色段数量(连续相同颜色...
洛谷 P2542 [AHOI2005]航线规划 题解【树链剖分】【线段树】【tarjan】
一道特别特别特别考基本功的题。 题目描述 对Samuel星球的探险已经取得了非常巨大的成就,于是科学家们将目光投向了Samuel星球所在的星系——一个巨大的由千百万星球构成的Samuel星系。 星际空间站...
洛谷 P4092 [HEOI2016/TJOI2016]树 题解【树链剖分】/【并查集】/【模拟】
虽然这题可以用树剖或并查集来做,不过裸奔是最快的。。。 题目描述 在2016年,佳媛姐姐刚刚学习了树,非常开心。现在他想解决这样一个问题:给定一颗有根树(根为1),有以下两种操...
洛谷 P2146 [NOI2015]软件包管理器 题解【树链剖分】【线段树】
与其说是一道树剖题,不如说是学习了线段树的区间覆盖写法。 题目描述 Linux用户和OSX用户一定对软件包管理器不会陌生。通过软件包管理器,你可以通过一行命令安装某一个软件包,然...