省流：我是废物，别看了，退出去吧。
[ABC275Ex] Monster
我们发现如果要减一次，那么最好是点 \(i\) 左右两边能延伸到的最远处都减一下，反正多减不亏。
于是我们建立一棵以下标为顺序的笛卡尔树。
笛卡尔树是以权值建立的大根堆。
笛卡尔树的 \(O(n)\) 建立：
用一个栈维护笛卡尔树一直向右走的链。假如说我们要建立的是小根堆，那么显然的是这条链从栈底到栈顶一定是递增的。我们按顺序插入元素。对于每个元素，我们从栈顶向下弹出栈，如果当前位置大于自己，那么就弹出，否则就挂在个位置的右儿子上，把下面的挂在自己的左儿子上。这样能保证中序遍历和之前一样。
然后报一张 OI-wiki 的图。
代码：
for(int i=1;i<=n;i++) { int k=top; while(k&&B[st[k]]<B[i]) k--; if(k) rson[st[k]]=i; if(k!=top) lson[i]=st[k+1]; st[++k]=i; top=k; } int rt=st[1];
建立出笛卡尔树之后，不难发现，每次操作的顺序没有影响，所以我们令顺序为从底向上。
设 DP 方程为 \(f_{i,j}\) 表示以 \(i\) 为根的子树，最大剩余的值不超过 \(j\) 的方案数。
\(f_{i,j}=\min \limits_{k=\max\{j,A_i\}}^{\infty} f_{lson(p),k}+f_{rson(p),k}+(k-j)\times B_i\)
\(k\) 的含义就是包括 \(i\) 本身的子树下最大值，\(k\) 不能小于 \(j\)，因为减的次数为正，\(k\) 也不能小于 \(A_i\)，因为 \(A_i\) 此前一定没被减过。
这样是 \(O(n^2)\) 的。
然后考虑凸性优化。证明这个函数是下凸的，我不会。我是废物。
就考虑假设左右两边都是下凸的函数。这个方程就相当于把他们加一起。凸包的函数斜率单调递增，两个凸包对应相加的斜率还是单调递增，所以最后的函数是斜率单调递增的东西，也就是下凸包。
然后这个取 \(\min\) 的操作就是先相加，再从一个值之前，取后缀最小值，
就有两种情况。一种是下凸的顶点在 \(A_i\) 之前，另一种是下凸的顶点在 \(A_i\) 之后。再偷两张图。
可以观察到，就是找到绿色直线后面最低点，删掉左边的所有东西，加一条横向的直线。
我们用 __gnu_pbds::priority_queue 维护分段函数每次加上去的斜率。
然后找到最低点，也就是斜率开始大于零的位置。将那之前的都替换成 \(0\) 。然后在最后加上斜率为 \(B_i\) 的直线，代表式子里的第三项。
__gnu_pbds::priority_queue 的好处是可以直接合并，复杂度 \(O(\log n)\) 的。
[ABC274Ex] XOR Sum of Arrays
科技题，看一眼怎么用的就跑（（
前置知识：Nim积
我们考虑如果是两个串的合并是相加的关系，那么哈希值相加也是可以的。那么任意两段相加是好做的。那么如果改成异或，那么 Nim 积就是乘法，他们两个之间的运算法则和乘法和加法是一样的。所以我们用 Nim 积维护 hash 值，然后像普通哈希一样做就行。
[ABC273Ex] Inv(0,1)ving Insert(1,0)n
这就又涉及到妙妙 SB-Tree 了。
我们观察到它的构造方式和 SB-Tree 完全相同，所以不是最简分数的都不行。所以可以以非最简分数为界，划分成一段一段的，对每一段计算答案。
然后我们对一段内的所有分数排序。进行这样的拆贡献：考虑一个树上节点会对多少个区间产生影响（因为求的是步数所以不能计算恰好等于的那个点）。这样我们可以计算每个树上节点可以到达多少个分数，然后计算区间即可。计算区间数量就是插入分数，计算从他自己到最近的左边的分数的距离乘以它到相邻右边的距离。
然后考虑在这棵树上走，走到所有有需要的树节点上。但是每次走一步是有问题的，因为有可能往一个方向走，然后走了 \(1e9\) 步。所以可以先二分一个走的步数，先往这个方向跳这么多步，然后每次递归时保证至少减少一个分数。这样最多递归 \(O(n)\) 次。
在递归时二分往每个方向走的数分别是什么。然后在每个节点上维护一个 set ，里面装的是节点能到达的分数。启发式合并维护 set 对应出现的答案是什么。然后加起来所有节点的答案就行。
P9067 [Ynoi Easy Round 2022] 虚空处刑
首先考虑每条边只有链接，没有断开。所以我们如果能维护每条边的连结状态，那么复杂度就是均摊的 \(O(n)\)。
所以我们让所有联通块的信息集中在最高的节点上。
于是我们对每个节点维护一个 map<int,vector<int> > C[maxn]，\(C_{i,j}\) 表示节点 \(i\) 为代表的联通块下面连结的联通块中颜色为 \(j\) 的点，这个点一定是它所在的联通块的头。那么如果要修改一个联通块的颜色时，先把 \(C_{findx(x),y}\) 之间的边都连上，然后再扔掉里面的所有点。连的时候要启发式合并 \(C\)。然后就是考虑父亲的那条边，如果能连，那么就直接连上，否则，在 \(C_{fa,y}\) 中加入自己。这样父亲上会剩下自己的边无法被删掉，这种边只有 \(O(n)\) 条，不影响复杂度，用到的时候特判掉就行。
[AGC005D] ~K Perm Counting
我又学到一个新 trick
我们在遇到排列相关问题时可以看成在一个 \(n\times n\) 的棋盘上放 \(n\) 个中国象棋里的车（国际象棋我不会，别问我），使得他们互不攻击。
这就对应了两辆车不能在同一行或同一列，正好对应了排列的性质。
然后我们就可以标记出不能放车的位置，如图（还是偷的）
然后就是在上面放 \(n\) 辆车。
考虑容斥，考虑 \(f_i\) 表示钦定 \(i\) 个车在灰色格子上，剩下的随便放的方案数，这只需要求出在灰色格子上放 \(n\) 个车的方案数。剩下的乘个 \((n-i)!\) 就行。
然后考虑有哪些灰色格子之间不能同时选。
在同一条链上的不能同时选。所以我们把所有链首尾拼接，只有连接处可以同时选。
然后求个独立集就行。
最后容斥显著可以 NTT，前面求独立集可以矩乘优化。不过和我无关。
P5363 [SDOI2019]移动金币
我们把每个金币之间形成的空隙看成石子，每有一个金币向前移动 \(k\) 步，就相当于把 \(k\) 个棋子从一块挪到了另一块。
这是阶梯 Nim 游戏的模型。
阶梯 Nim 游戏：\(n\) 堆式子，每次可以从第 \(i\) 堆石子移若干个到第 \(i-1\) 堆，当有人不能做下去就输了（即所有石子都在第 \(0\) 堆）。
结论：所有奇数堆的石子的异或和为 \(0\) 时后手必胜，否则先手必胜
证明：考虑两人都只动奇数堆的，那么就是普通的 Nim 游戏。加入此时先手必胜，后手试图用偶数堆移到奇数堆来改变局面，先手就能再将这些石子移到下一个偶数堆来变回原来的状态。对于后手也一样。
然后就考虑做法。我们先求所有偶数（标号窜一位）位置异或和为 \(0\) 的方案数。这就是有 \(n-m\) 个石子，分给 \(m+1\) 个堆，可以为空，但是偶数堆所有的石子异或和为 \(0\)。
我们考虑拆位，对每一位 DP。先扔掉所有奇数堆的，算出总方案数之后插板法算一下就行。\(f_{i,j}\) 表示当前做到第 \(i\) 位，已经用掉 \(j\) 个石子的方案数。
做到第 \(i\) 位时，我们枚举有多少个偶数堆这一位填 \(1\)。
\(f_{i,j}=\sum\limits_{k|2} f_{i-1,j-k\times(1<<i)} \times \dbinom{\frac {m+1}{2}}{k}\)
最后插板法算一下答案就行。
CF1603F String Journey
我打开这道题是想做巨大字符串的，但是根号做法是真的好写。
我们最优情况下的答案长度一定是 \(1,2,3\dots ans\)
所以总长是 \(\frac {ans(ans+1)}{2}\)，所以答案不超过 \(\sqrt{2n}\)。
考虑枚举答案长度，如果有不行的就输出。
我们枚举哪个字符串是最开始的答案，在看 \([i,i+ans-1]\) 行不行的时候先把所有开头大于 \(i+ans-1\) 的长度为 \(ans-1\) 的串，并且可以作为答案的哈希值扔进桶里，如果 \([i,i+ans-2]\) 或 \([i+1,i+ans-1]\) 的哈希值也在桶里，就说明这个可以作为答案串里。
如果在某时一个位置都不能成为答案串了，那么就退出即可。
后记
没有人曾体会 没有人曾了解
没有人曾感受 我喜与悲
我被肆意踏践 丢弃全部尊严
人们路过 笑过 骂过 不留一声抱歉
我等着你污蔑 我看着你诬陷
我观赏这喜剧 是你导演
既分不清现实 也听不进奉劝
用一分偏执 换三分喜悦
和人类说话还是挺累人的说。
感觉在 whk 还好，和其他人说话什么话题都多少沾点。学 OI 就不一样了。和机房里的人也还好，感觉理解难度不是很大，说的东西也还能理解，也不太单一。
但是和机房之外的人就不一样了。尤其是在春测之后，所有碰见我跟我搭话的人都要问问我什么考试成绩还有省队之类的。但是具体问下去对方又有一些细节不懂，导致 ta 理解不上去。然后我每次都要从头解释省队晋级标准，考试时间，然后要是对方再好奇，还得解释女队和校线之类的。解释完很累。
但是碰见的同学老师还算不太多，毕竟我只需要在大部队不上课的时候去走廊就没什么事。最累的是回家，这也不能说什么，毕竟我在学校会获得大量关于考试之类的信息，我父母什么都不能获得。本来我回家也不愿意说话，但是还是要跟家人说这些，说完了也挺累的。但还是因为信息差，所以他们肯定继续追问，但是我这时候什么都不想说了，我在家总共也就一个小时能说话，这基本上就占满了。所以到睡觉的时候会有一种“虽然什么都没干，但是要累死了”的感觉。
以上只指和人类说话，和猫猫就不一样了。不管我在学 OI 还是 whk，只要和他说话，顺便摸摸他，他就会真挚地望着我，有时候还会回复一句喵喵。
综上所述，和人类说话是不快乐的，但是和猫猫说话是非常快乐的。所以我要去撸猫了，而且不会拍照片给人类看！！！