不能打 NOI /fn/fn/fn。因为好久没打模拟赛做一下 UNR#10，主要可能是为复现 NOI 做准备。
Day1
vp 100+100+10=210。T3 倍增分块有点太精妙了。
-
【T2】感觉题目不错，就是有点难写。
首先先考虑判定。考虑固定出现次数 \(x\)，则发现第 \(i\) 段可行的结尾对于 \(x\) 始终是一段区间 \([l_i,r_i]\)，且 \(r_i\) 是尽量后选择 \(i\) 段的端点，而 \(l_i\) 是尽量前选择 \(i\) 段的端点，则 \(k\) 合法的条件 \(n \in [l_i,r_i]\)。考虑 \(x+1\) 时的 \([l_i',r_i']\)，根据定义不难发现始终有 \(r_i <l_i'\)，所以每个 \(k\) 对应的 \(x\) 是唯一的！所以可以对每个 \(x\) 单独处理，然后套路的拆开 \(l,r\) 将 \(\sum n \in [l_k,r_k]=\sum [l_k \le n]-[r_k <n]\)， 所以分别对 \(l,r\) 进行 dp：
- 对于 \(l\)，这部分比较容易。令 \(g_{i,j}\) 表示区间 \([i,j]\) 恰好出现 \(x\) 个数的方案书，则令 \(f_{u,i}\) 表示 \(l_u=i\) 进行转移即可；
- 对于 \(r\)，发现区间 \([i,j]\) 的转移与 \(a_{j+1}\) 有关，不难想到需要 \(a_{j+1}\) 的值，即令 \(g_{i,j,v}\) 表示 \([i,j]\) 出现 \(x\) 个数，且都不是 \(v\) 的方案数个数，同样令 \(f_{u,i,v}\) 表示 \(r_u=i\) 且 \(a_{i+1}=v\) 的方案数个数。因为求 \([i+1,j]\) 的方案时已确定 \(a_{i+1}\)，所以可能需要一点细节。
\(v\) 可能很大，但显然值域可压缩 \(O(n)\)。第二部分的复杂度看上去是 \(O(kn^4)\)，但事实上 \(x \le n/k\)，所以复杂度 \(O(n^4)\)。
-
【T3】感觉倍增分块很精妙！
考虑一组 \([l,r]\) 如何判定，发现一个巧妙的事实：对于 \(k \in [\frac{l+r}2,r-l+1]\)，判定 \(s_{l,l+k-1}<rev(s_{r-k+1,r})\) 均是可行的！于是联想到使用倍增分块。即取 \(k=2^p\) 然后将查询区间分为 $\log $ 组比大小，直接使用 \(sa\) 即可做到 \(O(n \log^2n+q\log^2n)\)！这里有一个小优化，就是事实上每个询问 \([l,r]\) 只有最后一个 \(k=2^p\) 会增加查询节点，所以本质上节点只有 \(O(n\log n+q)\) 于是复杂度优化到 \(O(n\log^2n+q\log n)\)。
然后可以有一些 16 叉树的常数优化，还有一个比较 sa 的做法，还没读懂。
trick：感觉比较 Ad-hoc，区分度也比较小。主要是对于 \(k\) 的观察感觉非常巧妙！！！
Day2
vp 100+100+20=220，感觉风格和 Day1 差不多，就是 T2 好写一点。
-
【T2】仙人掌的部分分给得不错 /qiang
看到求 \(T\) 的个数而不是 \((T,s)\) 的个数，于是思考合法 \(s\) 满足什么条件。发现如果用 \(T\) 刻画 \(s\) 非常复杂，于是先考虑仙人掌。
对于一个环 \(p_1,p_2,\cdots,p_k\)，假定断掉 \((p_1,p_2)\)，则发现 \(p_1\) 可以为 \(s\) 当且仅当 \(p_2\) 可以为 \(s\)，如此套环得到合法的 \(s\) 在圆方树上是一条链，于是点 - 边容斥 \(O(n^22^n)\)。发现这里的 "链" 是有种非树边的感觉。
于是直接考虑 \((T,s)\) 若 \(s=u\) 成立，则是不是 \(u\) 某条非树边的端点 \(v\) 也成立？事实上并非如此，因为可能会存在返租边 \((dep_a<dep_b)\) 经过 \(v\)，但发现将 \(v\) 调整为 \(b\)，不断经过这样的调整可能找到另外一个合法的根。比较显然，根据 \(v\) 向子树通过上述的寻找方法，可以找到所有合法点。比较显然，\(v\) 与 \(u\) 属于同一点双，于是合法点 \(s\) 在圆方树上构成联通块！
所以考虑点-边容斥，点好计算，令 \(f_{s,i}\) 表示 \(s\)，根为 \(i\) 的方案数个数。对于边，即理解为同点双的两个点 \((u,v)\)，刻画一下发现 \(u,v\) 可同时称为根的条件是，点双在 \(T\) 中是 \(u \to v\) 的链，这里直接链 dp 就 ok 了，复杂度 \(O(n^22^n)\)。 -
【T3】呜呜有没有 dalao 可以教教我 /kl
后记
不能打 NOI /fn/fn/fn，其实两天 T2 感觉和省选 D1T2 差不多风格，依旧懊悔为啥省选 Day1 不先看一眼 T2，非要只剩 1.25h 的时候再慌慌忙忙的看 T2 /ll/ll/ll（T3 部分分也没敲完）。
吓哭了，是 NOI 出简单了，还是 Oiers 都太强了。听说 NOI-Day1 好多 260+。。。