ResurrectionTX

题解

比赛(7) 笔记(6)

/ 注册

全部文章 / 题解（共2篇）

Codeforces 235C 【Cyclical Quest】

Description 传送门 Solution 考虑循环同构的性质，每次相当于从最前面删去一个字符，从最后面加上一个字符。在\(SAM\)里对应着往上跳\(fa\)或不跳和走对应的字符串转移边。考虑对于长度为\(l\)的串，最多删\(l\)次，最多加\(l\)次，所以直接在\(SAM...

SAM 字符串 Codeforces

2020-06-12

0 530

Luogu P5212 【SubString】

Description 传送门 Solution 动态加入字符就用\(SAM\)，发现答案就是一个点的子树的\(siz\)之和，所以需要动态维护子树和，上\(LCT\)。 \(lCT\)上每个节点，\(siz\)表示\(Splay\)上大小，\(lsiz\)表示虚子树大小，修改\(Upd...

Link-Cut-Tree 字符串 SAM Luogu

2020-06-16

0 381