chx卷完期末考之后感觉码力下降的厉害，所以就来复健一下
2025.1.24 - Codeforces Round 994 (Div. 2)
没什么难的题目，但是 B 题按错一个字符耽误了将近半个小时 对于 F 题，不难分析出条件为 $a_i< 2^k$ 且 $mex=2^k$ 所以考虑枚举这样的 $k$ ，对于大于 $2^k$ 的就断开，然后每个段维护一个权值线段树状物，在线段树里维护 mex 即可 然后发现 $x>0$ ，所以如果把操作倒过来，就是相当于段之间合并，所以写一个线段树合并即可，时间复杂度是 $\mathcal O(n\log^2n)$ 但是不开 longlong 调了一整天
2025.1.25 - Educational Codeforces Round 173 (Rated for Div. 2)
前五个题目都还好，但是 D 脑塞了，并且 E 特别狗屎，就纯大模拟 对于 F 题，有一个 CDQ分治 的做法 就是考虑对于每个询问在询问覆盖的最上分治点来处理它 然后由于 nim 问题和区间异或是相关的，而合并两段的异或和的信息是容易的，所以可以 CDQ分治 就是朴素的 dp 即可，时间复杂度是 $\mathcal O(nV\log n+qV)$ 对于 D 题，没想到是纯暴力，一直在想是不是有什么构造来实现 实际上，对于 D 题，不难构造出答案的下界：让大的那个数是区间内最大的质数即可 然后其实质数的间隔是很短的，这意味着答案的下界和 $r-l+1$ 的差别是不大的，直接暴力就行了
2025.1.26 - Good Bye 2024: 2025 is NEAR
前面四个题目还是十分容易的，然后 E 是一个巨型换根 dp 对于 F 题，我觉得十分有趣 首先有朴素的 dp：
$$dp[i][j] 表示第 i 行的 -1 填的是 j 的前 i 行的最优贡献是多少$$然后不难推导出转移方程：
$$dp[i][j]=\max_k\{dp[i-1][k]+A+B\cdot [j==k]+c_{i,k}\cdot L+c_{i-1,j}\cdot M\}$$总结一下就是相当于要求这么几个操作： 全体加上某个数，全体和某个数取最大值，给某个值增加一个数，求所有数的最大值 听说可以线段树，我不会 实际上可以考虑维护一个 set，记录哪些数是被取最大值了的，因为一旦某个数被取最大值了，一般条件下就永远都会被取最大值 对于那些没被取最大值的数，不难发现他们一定是从某个时刻起一直被“给全体加上某个值那个操作”来操作 所以考虑维护全体总共加了多少值 tot，然后对于每个没被取最大值的数，记录一下它是什么时候被单独更新的，它单独更新的时刻为 $t$ 那么它的值就是 $x+tot_{now}-tot_t$ 然后用一个 set 来维护 $x-tot_t$ 即可，时间复杂度是均摊的，为 $\mathcal O(nm\log nm)$
2025.1.27 - Codeforces Round 996 (Div. 2)
nnd，模拟大赛是把，无马也！ 前四个题依然容易，但是 D 我没有找到一个比较简单的写法 对于 D 题，每个怪只有两个关键时间点： 一开始向右走了多久，然后向左走了多久接上目标，然后又向右走多久送出目标 从小到大维护这个东西就行了 对于 E 题，我认为是十分妙的 首先固定一个清空的顺序，然后可以弄出策略，然后不难发现只需要最小化
$$\max_{i<n}\{\sum_{j\le i}a_j-\sum_{j<i}b_j\}$$即可，然后考虑调整法，看看交换相邻两个元素会产生什么影响，得到最优的序列应该满足：
$$\min(a_i,b_j)\le \min(a_j,b_i):i+1=j$$然后你不难发现实际上这种东西是有传递性的，所以可以直接排序 然后拍完序后依次是 $a_i<b_i$ ，$a_i=b_i$ ，$a_i>b_i$ 的情形，具体的在这三段内 第一段是按照 $a$ 从小到大排序，第二段随意，第三段是按照 $b$ 从大到小排序， 所以实际上就是枚举最后一个人是谁，然后用线段树维护排完序的结果即可，支持区间修改什么的
2025.1.28 - Hello 2025
怎么又脑塞，感觉除了 dp 啥都不会了 前三题还行，但是 C 是很有趣的 对于 C 题，不难发现一个性质，实际上答案大多数都很大， 比如如果答案是 $U=2\cdot (11111111)_2$ 那么只要满足 $l\le x,y\le r$ 且 $x|y=U$ 即可，这个条件十分松散 然后考虑什么样的 $l,r$ 是无法做到上述这个东西的，然后就可以得出一个按位分治的做法了 对于 D 题，纯脑塞 不难发现答案还可以规约成另外一个形式：
$$\max\{a_x-a_y-|x-y|\}$$然后令 $A_i=a_i+i,B_i=i-a_i$ 那么答案就是
$$\max_{i<j}\{\max(A_i-A_j,B_i-B_j)\}$$然后我以为要维护什么扫描线的东西从而符合 $i<j$ 的偏序关系，但是实际上在线段树上一起维护就行了，纯脑塞
关于 E2 题，考虑怎么对于 E1 进行优化 E1 的时间复杂度为 $\mathcal O(n^2m+mQ)$ 但是从势能的角度出发，初始化的时候所有的有序对 $(i,j)$ 有 $dist(i,j)=n$ 所以我们定义势能为 $\delta=\sum_{i,j}dist(i,j)=n^3$ 然后如果我们能保证每次更新的时候都使得势能会减少，那么时间复杂度就是对的了 然后手玩一下会发现前几次把边从一变成零会影响大量的势能，这个时候从并查集来考虑 如果两个点之间的边权为零，那么将这两个点视为一体的， 显然，如果某次更新把一体的两个点间的边权变为零，那么这样更新是无意义的，换句话说，我们只在有机会合并两个块的操作上更新即可 而每次更新会使连通块减一，所以有效的操作数是非常少的，是 n-1 次， 所以用一个并查集来维护一下当前的连通块即可
2024.1.30 - Codeforces Round 997 (Div. 2)
我真服了，脑塞已经不是一天两天的事了 前三题很简单，然后 D 题卡了很久， 实际上 D 题正过来计数是很困难的，因为要维护一个绝对值状物的东西，但是考虑反过来，怎么样的序列是不合法的呢 充要条件是：存在 x 使得将所有小于等于 x 的元素变成 -1，而把所有大于 x 的元素变成 1，则区间和为 0 充分性和必要性都是很好证的，并且假如一个序列是不合法，那么这样的 x 是唯一的，所以不会算重，这个题真的nb 对于 E 题，这个题我觉得很简单， 实际上要么包含要么不交的线段构成一棵树的关系，然后增加线段最多的就是变成一个二叉树，所以就是卡特兰数 然后这个题是钦定了某些节点必须出现，那么实际上把二叉树转化成括号序列就更好理解了，钦定一个节点就相当于钦定某一段一定是合法的括号序 那么一种双射的映射方法是：把这个区间取出来，然后先把非这个区间的情况给做完了，再把这个区间插回去 所以如果把树建出来，那么答案就是：
$$ans=\prod_{i}Catalan(r_i-l_i-(\sum_{x\in son[i]}r_x-l_x))$$