？
胡策 R14？T3
不用vscode写了。
旋转是线性变换。镜像也是线性变换。
那么对点可以直接维护矩阵乘积（没有修改的情况）。
如果是对变换矩阵的修改呢？发现可以看成对空间的变换，实际上我们在改变基。那么可以使用基变换。
（考场时候想的是转置，而实际上就是逆。）
一个线性变换 \(A\) ,一个对基的线性变换矩阵 \(E\)。
正常一个列向量 \(v\) 经过这个线性变换后得到 \(Av\)。
那么如果我们对基（线性空间）变换的话，那么我们可以先把 \(v\) 变换到原先空间上 \(E^{-1}v\)，然后线性变换 \(A\) 再变回 \(E\) 上。
\(Av\to EAE^{-1}v\)。
那么发现事实上我们可以直接拿线段树来维护这个东西，维护区间矩阵乘法，修改形如： \(A\to EAE^{-1}\)。
维护起来时还存在一个问题，对坐标系的变换显然可以直接矩阵乘法是正确的。但是一个“镜像修改”对“旋转”这个操作，会让它变成逆。
所以特殊处理就好。
R14 T2
是个基础题。
首先发现如果 \(a_i,a_{i+1}\) 颜色相同我们必不会用别的颜色覆盖他。（因为覆盖产生的正贡献只有 1，保持原样不劣）。
每个点和他的颜色上一次出现的位置构成一个区间，于是问题就是让我们选出尽量多的不交区间。
第一步，把包含关系去掉，现在,l,r分别单调。
第二步发现我们此时可以尽可能选靠前的了，那可以拿倍增直接维护，也可以直接分治。
R15 T1
斯坦纳树。（我甚至有点忘了斯坦纳树了。。）
大概是说选择 \(k\) 个边，边权 \(a_i\to b_i\) 后，最短路最大是多少。
最开始还以为是二分。
考虑最短路最后构成了一个树。，我们就是要对这颗 有向树 dp。
仿照着斯坦纳树的dp，\(dp_{u,k,s}\) 表示现在根是 \(u\),选了 \(k\) 条边，集合状态是 \(s\)。
依旧是我们有两种转移，一种是我们延申一条树边的转移，一种是我们合并的转移。
依旧是我们可以按照 \(s\) 从小到大转移，（自然有序）。然后我们总共会进行 \(2^nn\) 次合并。每次合并的是枚举超集，一个卷积，总计复杂度 \(3^nn^3\) 很是吓人（至少比我最开始想的是 \(3^nn^4\) 强。。。）。
接下来是延申树边的转移，可以dij，然后复杂度是 \(2^nnm\log m\) 的。
dij 没啥救（也能跑过去），合并转移可以考虑这个卷积形式过于特殊： \[ f_{i+j}=\min\{f_{i+j},\max(g_i,h_j)\} \] 发现事实上，做完前缀min后，我们可以直接two pointers 转移。这下复杂度是 \(3^nn^2\) 的了。
值得注意的是 dij前，转移后什么的dp可能不自然满足单调减，（不是很懂，好像挺有道理）所以需要做一次前缀min。
R13 T1
12-3 还没写，记一下做法，防止明天忘了。
首先背包出来每家店的生成函数。（注意卷形如 \(\frac{1}{1-x^c}\) 的容易做到 \(O(n)\)）。
接下来考虑我们可以 \(O(n)\) 的根据点值表示求出一项。（在单位根意义下范德蒙德矩阵逆容易计算。）
不存在单位根的话，随便找 \(n+1\) 个点值。接下来预处理: \[ [x^n]\sum_{i=1}y_i\prod_{j\not=i} \frac{x-x_j}{x_i-x_j} \] （这是一个矩阵）。\(\vec y \cdot M\)。
但是 \(n^2mq\) 太大了。主要原因 \(q\) 过大了。同时 \(nm\) 的长度过长，以及每次我们都需要枚举会额外产生 一个 \(n\)。
解决 \(nm\) 过长和多出来的 \(n\) 的方法是分块（）。
我们分 \(B\) 块，这样长度就是 \(mn/B\)，合并次数就是 \(n/B\)。
问题来到如何预处理。不应忘记的是我们维护点值是先截断，后扩长的点值。
我们需要预处理所有 \(F_{s,k}(x)\) 含义为 \(s\) 这个集合被强制 \(\ge k\)。这样的总数是 \(m\sum_{i=0}^{n}\binom{n}{i}/i\approx m\sum_{}\binom{n+1}{i}/(n+1)\approx m2^n/n\) 。
发现朴素转移很困难。这里有一个很巧妙的容斥，我们计算钦定 \(s\) 这个集合强制 \(\le k\)，记作 \(g_{s,k}(x)\) （这里是只把 \(\le k\) 的生成函数乘起来），然后很巧妙的使用高维前缀和得到 \(s\) 这个集合恰好 \(\le k\) 的方案数。
接下来再次进行子集和（？）得到 \(s\) 这个集合强制 \(\ge k\) 的方案数。
那么为什么要做这个容斥呢？这保证了我们对于 \(k\) 种限制进行多次合并的时候，合并长度不是 \(nm\) 而是 \(m\) 。这当然是保证复杂度至关重要的一步。
但同时这样做复杂度会有一个高维前缀和。
R13 T2
很有趣的一道题，同样的先写题解，防止自己忘了。
首先不难得到一下结论，如果要加速，我们一定会直接按最高加速度 \(a\) 加速。
为什么？考虑如下 v-t 图像。
如下调整不劣。
接下来的结论就更加厉害了。如果我们一定要减速，那么我们不管现在时间多么靠前，都不如提前减速。
为什么？考虑如下 s-t 图像。
我们可以在过程的开始减少一点速度，也就是红色那条线，他是不劣的。除非，除非原来这条线已经顶到限制。
而顶到限制不是 \(L\) 限制，而是 \(R\) 限制（观察图像，实际上我们是推迟到达的。）
然后考虑过程，过程自然被分成若干阶段，每个阶段都是恰好到达 \(R\) 然后更改速度。