小翔
题单介绍
自己出的/抄的题。没有质量，没有难度。
[std](https://www.luogu.com.cn/blog/LeonintheLead/xiao-xiang-ti-ku)
1. [皮蛋](https://www.luogu.com.cn/problem/U196926)
显然皮蛋碰撞和对穿没有区别，所以 sort 一下然后循环一遍就完了。时间复杂度 $O(n\log n)$ 。
2. [毛笋](https://www.luogu.com.cn/problem/U196955)
语文题。读完题发现每个笋能不能吃到是确定的（曼哈顿距离）。跑个最长不下降子序列即可。时间复杂度 $O(n\log n)$ 。
3. [蒜头](https://www.luogu.com.cn/problem/U211078)
烂题。想法是区间 dp 。但现在看来应该出错了。
4. [藤瓜](https://www.luogu.com.cn/problem/U210102)
做洛谷某月赛把题看成了这个。。。很显然改变一个点的值会造成后面所有点答案的整体变化，而相对答案差值不会变化。所以就拿树状数组维护一下，每次查询即可。时间复杂度 $O(n\log n)$ 。
5. [蒜头2](https://www.luogu.com.cn/problem/U198916)
一直有的一个问题，学了 Polya 定理之后发现做法的，不过该做法可能比较拉。
考虑不旋转的情况。设 $g_{n,0}$ 表示染 $n$ 个，最后一个不染的方案数， $g_{n,1}$ 表示染 $n$ 个，最后一个染的方案数。那么有 $g_{n,0} = g_{n-1,1} + g_{n-1,0}$ ， $g_{n,1} = g_{n-1,0}$ 。那么 $g_{n,0} = g_{n-1,0} + g_{n-2,0}$ 。这显然是一个斐波那契数列的递推式。故答案是 $fib_{n+1}$ （设 $fib_0 = fib_1 = 1$ ）。斐波那契直接快速幂就好了。
我们令 $g(n) = fib_{n+1}$ 。设 $f(n)$ 表示以 $n$ 为循环节的答案。则最终答案为
$$\sum_{d\mid n} \frac{f(d)}{d}$$
然后我们还有
$$g(n) = \sum_{d\mid n} f(d)$$
莫反一下
$$f(n) = \sum_{d\mid n} g(d)\times \mu (\frac{n}{d})$$
然后就不会了捏，故直接用
$$ans = \sum_{d\mid n} \frac{\sum_{T\mid d} g(T)\times \mu (\frac{d}{T})}{d}$$
来算了。复杂度实测略小于 $O(n)$ ，不会证。
6. [扑克](https://www.luogu.com.cn/problem/U239483)
刚学会 Splay 区间翻转来出的。操作 2 是板板，操作 3 就是单点插入 + 删除，操作 4 可以维护。这题的最大价值（虽然也没什么价值）在于操作 1 。
我们直接插入 $y$ 次显然是不正确的。注意到插入的数相同，故我们记一下每个节点有几个就好了。要询问的时候要是用到改节点就把他原地分成两个。时间复杂度大概是 $O(m\log n)$ ，常数略大。
7. [阿克](https://www.luogu.com.cn/problem/U242817)
也是做题的时候看错题了出的。
最大值最小题，考虑二分。然后写一个充满细节的树形 dp 。
可以意会不可言传的啦。
8. [排队](https://www.luogu.com.cn/problem/U225360)
教 CTR 单调栈的时候想到的，发现 $O(n)$ 无法处理这个问题。可能是我太菜了捏。
$O(n\log n)$ 的做法很多。如果能排序的话，各种乱搞都可以。有个大佬告诉我还可以单调栈上跑二分。
9. [平衡树性能测试（随机数据）](https://www.luogu.com.cn/problem/U241769)
刚学平衡树，想测测各种平衡树（以及乱搞）的速度。
10. [平衡树测试（构造数据）](https://www.luogu.com.cn/problem/U242347)
为了卡掉 BST 而生。
11. [链表](https://www.luogu.com.cn/problem/U236407)
给 CTR 的练习题。然而他不做。
12. [线性筛](https://www.luogu.com.cn/problem/U231257)
随便搞了几个函数让 CTR 筛，但他不干。
13. [AK](https://www.luogu.com.cn/problem/U190185)
某年普及组题，硬塞了个线性逆元阶乘进去。
14. [运算](https://www.luogu.com.cn/problem/U74716)
sb题。坑人用的。