有人几何学的很差，考场上还非要写。
exchange-argument，已经是咱非常了解的题目啦啦啦。
套路题，二分然后最短路
对这种题还是比较熟悉了，不好处理的区间问题分类讨论变偏序，二维偏序解决区间交，贡献独立的情况，李超树搞定贡献分离的情况。
当然可以 CDQ 然后凸包上二分，但是我觉得我更擅长一般的数据结构。
我…. 不会解析几何。/ll /ll。
办法其实非常蠢，一条可行的最短路一定经过圆弧交点，且只会在这些交点拐弯。
所以求出所有交点，然后判断交点两两路径是否合法，连边跑最短路。
可行的交点其实不多，得判掉在圆内的点，然后剩下点的个数感觉上是 $O(n)$ 的，实际也是 $O(n)$ 的，证明我不会，等问数学竞赛的回来再补。
然后判合法本质上是判一条路径是否被覆盖，需要写线圆交，然后前面要写圆圆交，这玩意不是一次函数，会非常裂开，我写的很丑。
圆圆交直径相同，比较好办，用极坐标可以偷懒，线圆交相当折磨。
见 计算几何入门。
用向量写会相当舒适。
经典的 01 分数规划问题，二分小数，直接 DP ，然后记录转移状态，倒推分数得到答案。
注意这种答案可能为 0 的 01 分数规划一定要从 -1 开始二分答案，不然可能会取不到 0。
注意到其实它的分子分母都比较小，二分分数也是可行的一种方式 。
考场上的错误其实挺离谱的，就不细说了。
二分分数不用倒推，就很简单了。
套路题。
观察发现如果每张牌个数都大于等于 $2$，那么一定合法。否则一定会用一些顺子来凑，同一个位置最多被三个顺子用，所以如果一个位置超过 $5$ 个，可以视为 $5$ 个，状压 $DP$ 出合法的状态，对每种状态计算答案并求和。
拿到状态后计算答案就是个组合数。
题意超级钢琴。
真的是非常经典的题目了，可以说是开创了处理同一个问题 $1-k$ 优解的先河。
将解空间拆分成二维，枚举其中一维，考虑第二维的选择并计算答案，用 priority_queue 选择最优答案，选择答案后将当前的第一维按第二维剩下的情况拆分。
动态点分治也是一样的思路。
非常经典的题目，严格递增转不降是经典套路，最优解一定取到每个数值也是经典结论。
本题保证数据随机，应该是需要利用随机序列单调上升子序列长度为 $O(\sqrt n)$ 的性质，但实际上可以 $O(n^2)$ 轻松通过。
哦，应该是考虑补集转化，然后考虑哪些点固定，然后 $dp_i$ 表示第 $i$ 个点固定的最优代价，转移只能从能完成 LIS 转移的点转移过来，中间合法的条件是要么大于右边要么小于左边，根据经典结论一定可以调整成一段和左边相等，一段和右边相等，然后随机的情况下转移点个数 $O(1)$，长度 $O(\sqrt n)$，总复杂度 $O(n\log n+n\sqrt n)$。
假设有一种最优解包含了不是原有数的数。
考虑第一个不是原有数的数，如果它被调大了，那么把它调小成上一个原有数一定更优。
如果它被调小了，就把它调到第一个比调整后的数大的原有数的位置，如果因此导致后面若干个数小于它了，那么不难得知这些数现在都被夹在两个原有的数之间，而且都是从两个原有数区间的外面调整过来的。从左边第一个数开始，找和它相同的数，如果相同的数中，被调小的数较多，那么全部调到第一个和它不同的数，否则调回第一个原数，变成子问题。
最大值最小显然二分。
考虑一个划分合法的条件，发现只能在某些合法的位置断开，而且在这些位置是否断开不影响第一个条件的合法性。
所以考虑对这些位置动态规划，直接转移是 $O(n^2)$ 的，然后考虑维护所有可能的转移，发现如果拿个单调栈记录 $a$，那么转移的改变可以描述为 $O(n)$ 次区间加，线段树维护即可。
一个数组，考虑每个前缀的后缀最大值，可以被描述为 $O(n)$ 次区间加。
中规中矩的动态规划题。但我选择读错题。
求最长周长可以用一列一列考虑，处理出每个点向上延申的最上面的位置，用单调栈维护这个东西，然后可以做到 $O(点数)$ 处理。
又是逆向考虑的标准题目。
考虑最终答案的直径，对于直径这种东西，它的中点是非常特殊的，因为从中心到两边的距离是相同的。
这道题又要最小化直径生成树，也就是最小化中心到两边的距离，那从中心到某个点最小距离的最大值恰好就是直径的一般，所以对每个点跑一遍 BFS，求出 BFS 树的直径即可。
不难得到一个结论：最小直径生成树的直径中点（有可能在一条边上）是图的绝对中心，其中图的绝对中心可以存在于一条边上或某个点上，该中心到所有点的最短路的最大值最小。
算是套路的反向转对穿。
称将反向视为对穿后形成的局面为对照局面，那么对照局面的周期为 $2L$，故问题周期为 $2L$，转化为 $T\le 2L$。
考虑往回走比较恼火，转化为撞墙后继续走，然后有一个相同颜色的人在此时出发，即在最初在一个对应的位置准备出发，容易发现仍然没有两个点在同一位置。
扩大了 $n,m$ 的范围以及数轴的考察范围，但是不用考虑转向了，难度实际上降低了。
由于有颜色差别，所以可以分出两种思考方向。
两个 Heren 相遇后换衣服，从左往右依次考虑每个向左的 Heren，除了第一次之外，都是右边的 Heren 在相邻之间换衣服（向左的那个 Heren 和第 $i$ 个换衣服之后马上和第 $i+1$ 个换），相邻向左的 Heren 换衣服是可以快速计算区间答案的（或者说用扫描线后是均摊 $O(1)$ 的）。
考虑将对照局面的相遇和原局面的相遇，只需要求出相遇位置的排名，就可以对应回原局面的情况，注意从 $[0,L]$ 之外出发的点，是什么颜色其实并不重要，因为排名落在这些区间的相遇，一定在 $(0,L)$ 外面，注意是开区间，所以还需要妥善处理边界。
发现每一个向左的点的所有相遇事件，其位置的排名单调递增，对应的坐标也单调递增，回到原序列相邻元素是一个区间加。
思考这个方式的本质，和换衣服的思路没有太大差异。
敲下"相遇"的时候，差点又掉眼泪....
考场上想到了处理移动相交转图上问题搞，但是相交关系比较多，这个思路走不动。
首先得发现一件事，如果用一个方向的移动完全可以移动完，证明考虑找左端点最靠左然后最靠上的，所以左端点一定不会被遮挡，然后如果这条线段被另一些线段遮挡，那么找到遮挡它的线段中左端点最靠左然后最靠上的，依次找下去，左端点递增，所以一定会找到一个不被遮挡的线段，移除它就行。
考虑构造一种方案，不妨要求必须往上移动，对每个方向分别求最早的一次不合法，其它情况可以转坐标系。
考虑求出一个方向上，遮挡限制关系构成的图，首先它一定是个 DAG。我估计我是想不到的，但可能确实平面组合几何问题应该考虑扫描线，由于线段不交，所以扫描线与对应线段交点的相对位置永远不变，用 set 维护扫描线即可，加入时会多出 $O(1)$ 条边。这样构建出来的图是可以正确描述遮挡关系的，感性理解挺容易的，证明有点难写。
拓扑排序之后第二问做完了，第一问的话，如果出现了拓扑序较大的先被移动了，那么就是不合法的，但是需要注意拓扑序只是一个比较松的限制，还需要加上横坐标区间有交才是两条线段存在先后限制的充要条件，证明是显然的。
需要注意的是，这道题用了 set 去维护边，其中涉及到了浮点数的运算和比较，所以 erase 的时候需要考虑浮点误差。
模板函数用于将同一个函数对不同类型生效，一般来说，最好不要用 auto 来捕获，写模板函数才是正确的方式。
模板函数的声明和定义一般不能分开。
如果你想偷懒，就是调用的时候不想写 <T1,T2...>，那么你调用的时候必须能让编译器推断出每个模板类型参数是什么，而且同一种类型不能冲突。
这里需要注意字面量的类型问题。
注意，如果你使用了默认参数，那么调用的时候可能就无法让编译器推断出类型从而出现 CE。
1 | template<typename T1,typename T2> |
类型参数捕获比较阴间的例子，可以发现它会先捕获”简单”的，不太想深究这个：
1 | template<typename T1,typename T2> |
如果显示指定参数，那么会出现类型强制转换，和正常的函数调用完全相同。
例子就不举了，和正常函数没差别。
1 | const int* p = &a; //指向常量的指针 |
中规中矩的一道题，但是我的做法比较蠢。
考虑最终那些序列可以成为答案的方式没有问题，但是我考虑的条件是对于 $a_i$，大于等于它的数必须多余 $n-i+1$ 个。这样需要记录的东西是 $2$ 维的，然后转移还不是优雅的前缀和形式。实际上可以考虑 $b_i\ge a_i$ 这个条件，也就是多想一想的事，这样的转移可以写成优雅的前缀和。
像这种转化后考虑条件的题，一定要找一个简易的条件去做。
中规中矩的一道状压题。
我考虑直接爆搜联通块，但是这样的做法不是很优雅。转移时其实仅和当前选了哪些点有关，所以其实可以动态规划，做到 $3^n$，这种联通块相关的题，一定要考虑联通块之间有没有关系，能不能用动态规划搞定。
中规中矩的一道数据结构优化动态规划的题。
一种比较经典的动态规划优化方式是拿数据结构维护可能的转移，这题本身有着比较优美的性质，可以将对转移代价的贡献拆成两个区间加。
对于修改独立的情况，如果要快速求出答案需要预处理序列，不妨考虑二进制分组。
有意思的二分题。
最大值最小还是可以考虑二分的。
对于这种两者加起来不超过一个数的题，往往可以考虑每个数与 $\frac{s}{2}$ 的关系。
这种题，显然最终的答案序列是很多个不超过 $\frac{s}{2}$ 的，中间夹着不超过一个大于 $\frac{s}{2}$ 的，所以容易证明不超过 $\frac{s}{2}$ 的数是必选的，如果不选，一定可以调整过去。
然后二分之后需要 check 一下总个数。一个区间中存在合法的大于 $\frac{s}{2}$ 的数，当且仅当最小值合法。但是如果真的要检查区间最小值个数，那是非常困难的，因为我们需要先得知每个区间的位置，这个位置个数是 $O(n)$ 的。
所以不妨从合法的数本身的性质考虑，容易发现，合法的数，与它左右两边第一个小于它的数的和一定是小于 $s$ 的，如果出现相等那么为了避免重复需要设一个第二关键字。
这样就可以做到 $O(\log)$ check 了，对于两边的边界，可以特判掉。
我们发现需要 check 的东西形如 $[l,r]$ 中 $\le x$ 的数的个数，这是整体二分擅长处理的东西，所以考虑整体二分，二分的时候将原来的有序组有序的分裂下去，就变成了一维偏序，而且不需要排序（已经有序了）。求左右区间端点也可以类似的做。
对于边界，可以用 ST 表特判，时间复杂度 $O(n\log n)$。常数比较大。
整体二分的卡常是有一些技巧的，比如巧妙处理归并，归并的同时分裂数组，通过下标分裂而不是 vector 等。
还没写完，估计是个论文级别的大坑
NOI2021 中的《轻重边》，一种比较经典的解法是将操作视为点染色，然后处理相邻点颜色相同的数量得到答案。但还有一种真正的树链剖分做法，这种做法能够体现树链剖分的本质——将树划分成 $\log n$ 条链，依次处理它们。
这一类题本质上都是树上邻域修改问题，即给定一条链，修改这条链的邻域。
条件：操作存在结合律。
给定一个点，修改其树上邻域。
这个是比较好做的，分两种情况讨论，操作是否存在逆元（且逆元容易求解）。
将一个点的操作视为两个部分，自身+父亲，对一个点的邻域操作时，在自身上打一个标记，暴力修改自己父亲的值，如果操作存在交换律则没有问题，如果不存在，则需要先得到父亲的真实值，然后操作后再放一个父亲的父亲标记的逆元。
共需进行 $O(n)$ 次操作和求解逆元。
如果操作只有结合律，那么会比较麻烦，如果是邻域赋值这类和之前的值无关的操作，可以记录一下每个点操作时间戳，清空一下树上标记，还是有救的。
如果和之前的值有关，并且查询只在最后做，那么可以开线段树记录一下
没救了，暴力吧。
首先处理的操作必须具备结合律
首先处理在链上的情况是比较容易的，因为邻域只涉及额外 $O(1)$ 个点，我们需要将这个优势拿到树上去。
考虑每次处理的 $\log$ 条重链，对于每条重链，它只会在 $top_u$ 处对其它，或者受到其它重链的影响。不妨将对一个点的修改放到两个地方，它自己和它父亲
考完了一个月之后再来写总结也是没谁了。。。
简单题，随手构造出来就行。
可以加强，比如弄成质数个，或者干脆 $10^{18}$ 个。
然而有个结论，考虑往一个字符串后添加 $k$ 个 $0/1$，那么本质不同子序列个数一定可以写成 $k(x-b)+x$ 的形式，其中 $x$ 为该字符串的本质不同子序列个数，$b$ 为上一个 $0/1$ 前一个位置的答案。根据这个玩意来构造，不会太好做。
发现本质不同子序列个数随 $n$ 的增长近乎呈指数增长，猜想满足条件的不会太多，所以暴力处理即可。
实际上设 $DP$ 状态，$dp[i]$ 表示考虑到前 $i$ 个字符，本质不同子串个数，有转移 $dp[i]=2\times dp[i-1]-dp[lst[i]-1]$，$lst$ 表示 $i$ 处字符上一次出现的位置。
于是设 $dp[i][j][k]$ 为考虑前 $i$ 个字符，上一个 $0$ 处本质不同子序列数量 $j$，上一个 $1$ 处本质不同子序列数量为 $k$，枚举 $0,1$，直接转移。
我想的是折半之后爆搜，然后剪一下枝，比 $std$ 快 $5$ 倍。
确实也是折半，但是其实可以考虑偏序关系，两个 $(x,y,z)$ 三元组合并，不妨要求 $x_1+x_2\le y_1+y_2\le z_1+z_2$，然后值为 $z_1+z_2-(x_1+x_2)$，本质上是个二维偏序。
还可以剪个枝，强制要求 $x_1\le y_1\le z_1$。同样能对应上去。
实际上还可以发现强制要求 $z_2\le y_2\le x_2$ 也没有问题，证明比较繁琐，故省略。
很妙的一道题，我想的是，需要将相同城市联系起来，考虑它们在虚树上的关系，每个点需要和它倾向的所有点连边，然后实际上只会连 $O(n)$ 条边，连好之后 $tarjan$ 求下 $SCC$ 就行。
有一种非常神奇的做法，考虑点分治，暴力求分治中心的答案，然后考虑其它点，发现之后的所有点的答案都不会跨过分治中心，可以暴力计算。
怎么说，题不难，但是需要想一下。
考虑右端点进行贪心的思路挺妙的。
比较套路的题，先弄出一个 $t\times n^4$ 的凑合做，然后发现两维转移系数独立，转移答案为三角形和形式乘上两维系数，可以考虑固定第二维，单独计算第一维不同转移系数对应的式子，每一种系数的变化量为 $O(1)$，所以一次转移可以做到 $O(n)$。
神仙题，考场上猜到树一定有解，但是想的是通过背包来构造解，事实上，可以归纳的证明每棵子树带来的差异可以取 $[-sz_u,sz_u]$ 中的任意值，所以对于树暴力构造一条从根到某个点的路径，可以满足路径两边大小相等。
考虑图上的结果。
09 年的一篇集训队论文告诉我们对于图上的问题，往往可以考虑其生成树的解法，从而进行拓展，发现无向图的生成树没有横插边，所以直接选取生成树上的答案，由于没有返祖边，所以原来合法的同样合法。
也是比较套路的题。
很明显本质上是给你个一次函数做路径边权，然后 $k$ 的值为 $1$，所以计算出每个点每个 $k$ 的值即可。
我选择分层图跑 $dij$ 外加大力卡常，但这是一种非常 $SB$ 的行为，$dij$ 本质上还是保证了转移的无环性，但 $TM$ 这个转移本来就无环还跑你大爷的 $dij$，暴力 $dp$ 出来做凸包就行。
然后从 $n$ 的各个在凸包上的 $k$，倒推回去看那些点可能被用到，倒推可以写成记搜，这样只用存一遍边。
给一个 $n\times m$ 矩阵，元素为 $1-n\times m$ 的排列，问你所有子矩阵的 GCD 之和。
反正我想的是考虑一个右下角，移动左上角来统计答案，这样的话考虑到 gcd 的变化次数是$\log$ 的，说不定有救，但是需要完成区间取 GCD，这个不好做。
想一下，这个做法没有利用到每个数只出现一次的性质，通常这种只出现一次的性质往往和倍数这些相联系，不妨换个思路考虑，考虑 $i$ 的倍数的子矩阵的数量，然后发现容斥一下就可以得到答案。统计 $i$ 的倍数的子矩阵数量不难。
我想了一下，链是会做的，树链剖分，就是把树变成 $\log$ 个链来做。
然后其实每条重链按照链的方式来做，重链的交汇处需要特殊处理。
不妨把边下放到点，发现如果一个点的父亲的修改时间晚于该点的修改时间，那么这个点所代表的链就没用，所以对每个点维护两个东西，一个是该点的修改时间，另一个是该点代表的边是否被修改成重边。
查询的时候对链的交界处需要查修改时间判断是否有效。
其实有个更简易的方式，就是把修改看成染色，一条边有贡献当且仅当其两个端点颜色相同，这个很容易用树剖维护。
这两种方式其实体现出处理边的两种方式——下放到点考虑，考虑两个端点的状态。
需要灵活运用这两种方式解题。