P10149 [Ynoi1999] XM66F

这个。没写过。

P9991 [Ynoi Easy Round 2023] TEST_107

考虑这个等价于强制钦定一种数不选，所以答案就是一个位置 pp 的相等前驱 / 后继与它的距离的最大值（若不存在则为 l−1l - 1 或 r+1r + 1）。

分三种情况讨论即可做到单 log⁡\log。没写过。

P8512 [Ynoi Easy Round 2021] TEST_152

考虑直接颜色段均摊得出 O(n)O(n) 个修改操作，然后可以发现唯一的问题就是有时候前面减掉的贡献是不存在的。那么设这次修改操作是把第 yy 个区间覆盖到第 xx 个区间上，那么前面减掉的贡献存在当且仅当 l≤x,y≤rl \le x, y \le r。

二维偏序即可单 log⁡\log​。

P5524 [Ynoi2012] NOIP2015 充满了希望

和上一道题思路几乎一样，只不过变成了单点查询，连颜色段均摊都不用了。

P4692 [Ynoi2016] 谁的梦

火题。先拆贡献变成每个颜色分别统计，然后容斥变为某种颜色没出现过的方案数。这个东西乘法原理即可。单点修改相当于分裂一段或合并两段，直接 STL 维护即可做到单 log⁡\log。会涉及一些除零的构式细节。

P5527 [Ynoi2012] NOIP2016 人生巅峰

最开始想的是区间长度 >v> v 时一定有解，实际上可以通过鸽巢原理分析出 >13> 13 时就一定有解。这个东西是 log⁡v\log v 级别的。那么其它情况暴力跑背包即可。至于维护每个位置的实际值，可以通过 BIT 维护每个位置的次数，然后实际用到该位置的时候再将 BIT 对应位置改为 11。使用 bitset 优化，时间复杂度为 O(n+m(log⁡n+vlog⁡vω)log⁡v)O(n + m(\log n + \frac{v \log v}\omega)\log v)。

P6108 [Ynoi2009] rprsvq

简单分析得到我们只需要维护区间和与区间平方和，剩下的部分就只是求几个只与 r−l+1r - l + 1 相关的系数了。求系数要推一坨东西，再见。

P9989 [Ynoi Easy Round 2023] TEST_69

每个点的有用修改次数之和是 O(nlog⁡V)O(n \log V) 的。直接线段树维护区间 lcm⁡\operatorname{lcm} 来决定要不要向下递归。直接写应该是能过的。看了题解发现好像可以通过一些神秘方法做到单 log⁡\log。具体来说，pushup 的时候如果当前区间操作之前 lcm⁡>V\operatorname{lcm} > V 才暴力 pushup，否则直接将当前区间 lcm⁡\operatorname{lcm} 对 xx 取 gcd⁡\gcd（而不是左右儿子取 lcm⁡\operatorname{lcm}）。分析无非就是，前者最多会操作一次，后者辗转相除次数均摊单 log⁡\log，还是有点厉害的。

P9990 [Ynoi Easy Round 2023] TEST_90

考虑左端点从右往左扫，那么我们对于每种颜色只需要考虑它第一次出现的位置，然后该位置后面奇偶性都会改变。那么就相当于维护 0101 序列，支持区间异或，区间历史和。可以简单做到单 log⁡\log。

P9995 [Ynoi2000] rspcn

这啥啊没见过啊。参考了题解。

借助 ODT 的思想，把一段有序段放在一起维护，然后就只需要若干棵权值线段树了。然后对于一种颜色，我们钦定它在它出现的最早位置计算贡献，那么可以将每一段的贡献放到段内对应序列上的右端点上，而每段的贡献都可以在对应的权值线段树上维护出来。最后那段被砍了一部分的段可以手动进去查。是大常数单 log⁡\log。