8.25\(_{xzr、ch}\)
T1\(_{100pts}\)
我：打表发现 \(>100\) 的数很少，\(\le 100\) 的数很多，分阈值处理。
std：\(ans_i\) 单调且 \(ans_i\le \dfrac{n}{i}\)，按 \(i\) 根号分治。
T2\(_{100pts}\)
我：保证修改不联通，感觉很难卡，直接打暴力。
std：图始终为森林，\(u\) 与 \(v\) 有答案的情况只有三种（略），直接维护 \(fa\) 数组即可，那么修改合并两棵树就启发式合并一下。
T3\(_{0pts}\)
我：没看懂题。
std：由于我们考虑的是相对顺序，所以位置信息无关紧要。在相对关系上看，选择区间整体左移一位相当于把一个数插到左边任意数之间，反之亦然。
转化完题意后发现对于一个数的操作无法影响前面的数的相对顺序，那么我们维护前面的数成为上升序列的最小代价一定没问题
上升序列是一个二维偏序关系，\(i<j \& p_i<p_j\)，我们按编号从小到大考虑，那么我们拿到了一个 \(p_k\)，如果它比当前尾的 \(p_i\) 大，那么说明它可以不动或者右移（这里右移由于是任意位置，我们可以抽象地理解为直接移到了目的地，以后关于它的贡献我们基本不用算了，在脑子里模拟一下）我们只会不移动或者直接移动到需要的位置，所以按这个来 DP，巧妙
T4\(_{80pts}\)
我：乱搞——bfs 分层，然后把每层的 siz 记录下来，最后按 siz 排序，能取几个就是答案。
std：写了题解。
总结：
T1——观察答案值域与单调性，实在不行打表
T2——不要瞎分析复杂度，NOIP 绝对挂
T3——一定要读题，NOIP 你不写暴力那你包炸
T4——网络流大胆猜大胆写，没人卡的乱搞糊上去也可以的。
9.2\(_{ydy}\)
T1\(_{100pts}\)
我：考虑最大值的 \(l,r\)，在这里我没有想到直接处理临界 \(l,r\) 于是开始偏移：我想着按 k 来动态更新，然后想着是 k 加一次，所有存活的最大值区间的 l 左移一位，然后会杀一些区间，至此我心想势能分析←实际上是假的）开始用 set,vector 写，写完调不出来，用了 2h 了，然后从每个位置考虑，发现 \(i\) 在 \(a_i<a_{i+1}\) 时会被感染，这样直接存一下很好写了。代码跑得飞快甚至比大家都快，然后我突然发现我这个复杂度是假的，直接弄个单调递增的数据就 T 了。
std：找到每个位置作为最大值的 \(l,r\)，发现在 k 加 1 时贡献的点貌似加 1，他对 k 的贡献的点为 \([max(x-k+1,l),min(x,r-k+1)]\)，所以 \(ans_k+=min(k,x-l+1,r-x,r-l+1-k)\)，我们把 ans 函数画出来，发现这个点对它的贡献是 \(min(y=k,y=-k+r-l+1,y=min(x-l+1,r-x) )\)，前两个是一次函数，后两个是常函数所以并起来了，最后是一个腰的斜率为 1 的梯形 ← 等差数列维护问题：可以二次差分后单点改最后一起查。
T2\(_{60pts}\)
我：先画杨辉三角，发现了先取整个三角形再取零散的假结论，写完过不了大样例。假了后想到 bfs，求最大的数相加，但是中间有取模，于是写暴力 + long double，long double 居然 \(n\le 500\) 没炸精度。
std：典的 k 优解问题，难点在于如何比较 \(C_n^m\)，取 log 用 long double。实现也不一定 bfs（但是 bfs 更快），更简洁的是把 \(C_n^i\) 先都存下来，然后取它时把 \(C_{n-1}^i\) 加进来（因为 \(C_{n-1}^{i-1}\) 比 \(C_n^{i-1}\) 小，欲取前者时后者肯定已经取了，所以要用他的时候肯定在，当然你都放进来然后用 map 存个 vis 也是没问题的）log 乘转加，除转减
T3\(_{0pts}\)
我：不会写暴力
std：如何合法？我们只关心选的端点，所以别的用省略号即可，假如定了端点
那么合法应该类：\(l_1…r_1l_2…r_2l_3…r_3\)
不合法但有潜力的类：\(l_1…r_1l_2…r_2l_3…\)
dp 存这种状态很不错了，显然我们只关心 l 的种类数
\(f_{i,j,0/1}\)：i 处有 j 种 l 且状态为合法/不合法（上面俩
加省略号：\(f_{i,j,0}×(m-j)→f_{i+1,j,0}\)
加 r：\(f_{i,j,0}×j→f_{i+1,j,1}\)
加 l：\(f_{i,j,1}×(m-j)→f_{i+1,j+1,0}\)
加 r：\(f_{i,j,1}×j→f_{i+1,j,1}\)
T4\(_{0pts}\)
我：没看懂题
std：每个人具体的能力值没用，一个事件到达下一个难忘的事件是确定的，我们可以预处理出来。考虑转成图论，每个事件直接向下一个难忘事件连边，是一棵树，问题转化为：每个点减 k 后，求 x 和 y 的 LCA 到根路径任选数累加的最大和。现在想要大于 k 的数加起来，我们可以用主席树按 val 倒序插入值，树剖后在 k 根查询，这是我的理解。但是还有更好写的做法：实际上我们可以每个点维护到根路径的值域线段树，儿子继承父亲时可持久化。
总结：
T1——花了 2.5h （陷入前世恐惧），一定不要瞎分析复杂度，觉得差不多了再写，还有要想到找临界。
T2——打表打大点，别看出来个假结论。
T3——想出来第一步的转移问题可以有很多分。
T4——一定要读题啊！
9.6\(_{gzez十四}\)
T1\(_{20pts——2.5h}\)
我：一开始想到了拆位，然后思考这一位的 \(cnt_1\) 区间个数，然后弄了个神秘奇偶计数法，写完之后发现加法在里面没考虑进位，发现十分复杂，把自己深深地限制在了抽象奇偶计数法的思维里。于是开始调转思路，对的，我觉得可以从左到右枚举左端点然后数合法右端点的个数，然后感觉困难于是放弃了这个想法。但凡想到枚举右端点，求合法左端点，然后用上数据结构，从此 A 上 T1。于是我又盯上了 \(\sum a_i\le 10^6\) 的数据范围，并坚定地认为这是个特殊性质，然后又找上了根号分治，我经典不分析复杂度，然后写完跑得巨慢分析一下发现跟暴力没区别。
std：转前缀和，枚举右端点找合法左端点个数，考虑树状数组上插入 \(qz_i\) 信息，后面查询的时候考虑借位的情况，如果两数的这一位都是一样的，那么我们让低位数借位即可，否则不让借位，所以我们维护这一位 0、1 两个树状数组，在低位数位置 +1。
为什么我总是走些抽象道路啊？为什么我总是跟正解擦边而过啊？
T2\(_{24pts——1.5h}\)
我：发现限制很抽象，所以想着 CDQ 分治，花了下式子，然后扫描线，中间发现绝对值都是没用的，直接记录最大最小值即可，后来发现只能处理一个询问，再后来发现 \(L\) 不统一并且还要记录 \(\sum\) 答案，所以复杂度假了，只能做 \(q=1\) 的部分分，然后发现分治实际上是多余的，直接扫描线拿下部分分。
std：承接上面的扫描线，思考怎么处理多组询问，难点在于对右端点贡献区间的处理（考试时死于此地，第一次见把贡献区间放线段树上修改节点答案 and 线段树节点存答案的题），把贡献区间也放在线段树上，在线段树节点上记录答案，查询时直接查询。
T3\(_{13pts——10min}\)
我：最后半小时才开 T3、T4 题面，发现是根号重构板子题，但是就剩不到半小时，故打暴力。
std：每根号存一下修改和询问，然后把当前需要修改的边在之前最后一次出现的位置的值也存过来，无修改的按重量从大到小排序，询问从大到小排序，每次询问我们先把无修改的边添加，然后找到修改的边找到他离询问最近的一次修改进行修改。查询后退栈撤销。
T4\(_{0pts——20min}\)
我：好像很可做？但是没时间想了，直接码暴力。
std：转成 DP，先来两维——节点、时刻，然后发现只需要满足儿子比父亲的时刻小就可以，所以 DP 式子呼之欲出，发现 DP 式子很丑，所以把 DP 含义由“恰好 i 时刻”改为“前 i 时刻”，简化完式子发现后者是一个定值，所以最终是一个数组合并 + 区间取 max 的转移式子，第一个用线段树合并，由于 f 不降，所以区间取 max 只会找到一段区间，那么我们只需要维护 ma、mi 帮助找到那个区间就可以了。
小问题（线段树合并）：
- 线段树合并为了保证复杂度，pushdown 的时候如果是空节点不要下传。
- 由于区间取 max 时我们并未到叶子节点，所以我们在查询时，递归到最下面的节点即可，而修改时，我们要把当前节点分开，注意要先 down 后裂，不然你裂后再 down 会打乱你刚给你儿子的初始值。
总结：
T1——没有清晰的思维路线导致没有快速切掉。没有坚定自己冲的方向。没有把好性质牢牢把握。不分析复杂度就瞎写
T2——没有确定好思路就写，写到最后发现出锅浪费了很长时间。
T3、T4——沉迷前两题不读题导致的，每个人对每个题的难度是不一样的，所以最好不要死磕前两道题，不看后两道题，没人规定必须先打完 T2 再打 T3、T4。
9.11\(_{gzez十五}\)
T1\(_{15pts——3.5h}\)
我：一眼看出贪心删最大值的性质和一个数只有 log 个状态的性质，然后想二分最大值然后把序列整体往下压，想了下整体二分发现不行，然后考虑加一个数的影响，感受到当前变量会被下压，而前面的最小值会被回溯，感觉直接把所有数的所有状态存下来，然后每次加数模拟一个指针的移动就好了。然后我开始码，码了 3h，中途小根堆转 set 了一次，拿拍子拍了 2h 的错，最后我发现这个做法特别生草，我无法知道最小值相同的时候该选哪个移动指针，于是这题就废了。如果想到了接近正解的思路，想好了再码，如果实现很抽象，我们可以再仔细想想有没有更好的等价的实现方法。
std：处理好末态，考虑减一个数的影响，发现这一个数的操作次数会不断分给前面的最大值，用 set 维护。
T2\(_{0pts——0}\)
T3\(_{0pts——40min}\)
我：最近刚学过容斥组合数学，所以开场先想了 20min 这题，在 DAG 上 DP，状态应该要存两条链最后一个关键点，思考 \(f_{i,j}\) 表示第一条链走到 \(i\) 第二条链走到 \(j\) 的方案数。由于这个 DP 的含义本来就不好，所以死了 QAQ。
std：先按 \((x_i+y_i)\) 排序，由于 \(x_i\le x_j,y_i\le y_j\) 所以排序后只能前面转移后面，然后 \(f_{i,j}\) 表示前 \(i\) 个点都被经过了，然后第二条链末尾为 \(j(j\le i)\)，同时这个含义顺便钦定了第一条链的末尾为 \(i\)。这个含义舒服多了，显然是从 \(f_i → f_{i+1}\) 的转移形式。
但是你显然不能让 2 链低 1 链一等，正确的路径应该同时转移（额外条件我们用容斥解决，在此先考虑 DP），把含义变成：第一条链末尾为 \(i\)，第二条链末尾为 \(j\)，前 \(\max(i,j)\) 的点都被经过了。
那么转移的下一步一定是 \(\max(i,j)+1\) 这个点，这样 1 链 2 链就同等了！
那么先考虑无不能相交限制的，我们发现转移的时候我们不容易钦定在转移过程种两条链没有相交，那么我们直接钦定重合点个数二项式反演。
\(f(i)\)：钦定了 \(i\) 个点重合的方案数。
\(g(i)\)：恰好 \(i\) 个点重合的方案数。
\(ans=g(0)=\sum_i (-1)^i f(i)\)，发现 \(i\) 与 \(f(i)\) 的次幂一样，所以把 \(-1\) 下发给转移到重合点的时候，这样我们就不用考虑转移的时候链相交的问题了。
for(int i=1;i<=cnt;i++)for(int j=1;j<=cnt;j++)if(i>j)jia(f[i+1][j],f[i][j]*dis[i][i+1]),jia(f[i][i+1],f[i][j]*dis[j][i+1]),jian(f[i+1][i+1],f[i][j]*dis[i][i+1]%mo*dis[j][i+1]);else if(i<j)jia(f[i][j+1],f[i][j]*dis[j][j+1]),jia(f[j+1][j],f[i][j]*dis[i][j+1]),jian(f[j+1][j+1],f[i][j]*dis[i][j+1]%mo*dis[j][j+1]);elsejia(f[i+1][i],f[i][i]*dis[i][i+1]),jia(f[i][i+1],f[i][i]*dis[i][i+1]),jian(f[i+1][i+1],f[i][i]*dis[i][i+1]%mo*dis[i][i+1]);
\(f_{cnt,cnt}\) 即第一问答案。
第二问显然是 \((1,2)→(n-1,m),(2,1)→(n,m-1)\)，相交如何计算，我们可以画一下相交的情况，然后在第一次相交的时候交换链 1 和 2 的路径（感觉这个做法很像反射容斥），发现相交路径与 \((1,2)→(n,m-1),(2,1)→(n-1,m)\) 双射，总路径数 - 相交路径数，两者都可以用上面的 DP 求出来，只是终点不同。
题的题解
T4\(_{5pts——20min}\)
我：暴力
std：发现操作很抽象，考虑 \(/w\) 算法，把 64 个操作（包括询问）分一块，发现每个操作最多分裂出两个等价类——我们考虑最后询问都是一些块，这些块最多 \(2\sqrt n\) 个，我们只需要考虑懒标记和分裂的一些细节就好了。
再小处理一下每个块能贡献到的询问。我们倒着枚举值域计算答案，把当前答案可以贡献的询问找出来，我们可以维护当前答案在的块再或上其询问，一层一层找实际上就处理出这个数组来就好。
用 ull 会很快很好写。
9.16\(_{gzez十六}\)
T1\(_{0pts——2h}\)
我：构造？？最优解问题？开始猜想是诈骗，但是我太傻了，想了不去做，也不去看大样例，浪费了很长时间同时走向了远的道路。首先知道排序会去掉内部的逆序对数，手玩了一下样例，想要维护最长上升子序列，只要长度 \(\ge\) 就好了，因为最后可以微操，发现我从头开始一个一个加进子序列十分缓慢（遥远的一步：我没有想到实际上连续地无微操地加进去等价于直接进来排序，所以前面这个操作只会加 \(1\)）。后来我才看到大样例的 \(1\) 和 \(2\)，但后面越来越偏，如：试图维护所有上升块启发式合并——没有任何价值。
std：先判断答案为 1，可以树状数组先扫一遍。另一个，我们找到前缀最大的 \(\le (整体逆序对-k)\)，加个微操就行。
T2\(_{15pts——1h50min}\)
T3\(_{0pts——10min}\)
我：怎么感觉有点典？但是我觉得 bool DP 应该挺难，但是位居 T3 并且没时间了我应该也做不出来，暴力不好码呀？那我写个乱搞。
std：\(f_{i,j}\)：s 匹配到 i，t 匹配到 j 可达性。
\(f_{i,j}→f_{i+1,j+1},s_{i+1}=t_{j+1}\)
\(f_{i,j}→f_{i,j+2},t_{j+1}=t_{j+2}\)
T4\(_{11pts——30min}\)
总结：
T1——鉴定为写下思路不看，不及时捋思路，不坚定结论，瞎想且注意力不集中导致的。
9.17\(_{gzez十七}\)
T1\(_{20(36)pts——4.5h}\)
我：先看出一个数最多 log 次 % 和一个数有用序列为 log 大的下降子序列，然后猜答案值域是最多两段连续区间、等价类很少这两个性质，码了一下观察发现前者对后者错，但是这样就没啥用。又想转化成区间加操作简化问题，无果。又思考了一下离散化，感觉到等价类很少，但是说不上来具体是哪个等价类，错误地认为一个 \(a_i\) 只会拆一个区间，然后想了一个分裂等价类的 B 性质做法，写出来发现是 \(O(n^2)-O(1)\) 的。