前言:
期末考完了,我短暂地复活了。愉快地看了五个小时书,突然想起我马上要去将近一个暑假集训,又想起我这一年居然并没有在OI能力上获得什么长进,又想起我还有两天半考八级而我因为期末复习已经忘掉所有知识点,又想起还有四个月就要CSP-S了,又想起我暑假过完了就初三了。
我完蛋了。
———————————————————————————————————————————
倍增。
第一道倍增
打发暴力。
感觉打字变慢了qwq
不暴力了。直接正解。
观察到a[i]≤13a[i]\le13a[i]≤13。突然耳鸣。
直接开十三个长度约为2e42e42e4得倍增数组。
预处理一下出现次数即可。
惊恐 惊喜地发现不会打倍增。
所以做了一个倍增小分析。
唔。所以这道题本质上是一个RMQ(预处理部分)+LCA(查找部分)。