Day 1

【CCO 2023】Flip it and Stick it

又是大缝合怪！但每种情况想起来都蛮有意思的。

• $|T|=1$。只需要判断 $|S|$ 中是否有对应字符。
• $|T|=2,T_1 \neq T_2$。令 $T=01$，目标串一定是，所有 $1$ 构成一个前缀，所有 $0$ 构成一个后缀，答案为，所有不为前缀的 $1$ 构成的极长连续段数量（每次操作将一个连续段移到前面）。
• $|T|=2,T_1 \neq T_2$。令 $T=00$，意味着不能出现相邻的 $0$，先特判 $0$ 的个数超出 $\lceil n/2\rceil$，在有解的情况下，令 $l_1,l_2,\cdots,l_k$ 是所有 $0$ 构成的极长连续段长度，每次操作可以看做把一个 $1$ 插到两个 $0$ 中间，则答案为 $\sum_{i=1}^{k} (l_i-1)$。
• $|T|=3,T_1 \neq T_3$。此时 $T$ 在 $S$ 中所有出现位置均不交，一次操作可以破坏一个出现位置，故答案为 $T$ 在 $S$ 中的出现次数。
• $|T|=3,T_1 \neq T_2$。令 $T=010$，目标串不能出现一个长度为 $1$ 的，不为前后缀的，$1$ 构成的极长连续段。一次操作可以合并两个长度为 $1$ 的连续段，或者将一个长度为 $1$ 的连续段和更长的段合并，令 $cnt$ 表示长度为 $1$ 的，不为前后缀的，$1$ 构成的极长连续段的数量，则答案为 $\lceil cnt/2 \rceil$。
• $|T|=3$ 的其余情况。令 $T=000$，目标串不能出现一个长度 $\ge 3$ 的 $0$ 连续段，先特判 $0$ 的个数超出 $\lfloor n/3 \rfloor+n \bmod 3$。观察一次操作之后连续段长度会发生什么变化：即删除两个长度为 $x,y$ 的连续段，加入两个 $x',y'(0 \le x',y' \le x+y,x'+y'=x+y)$ 的连续段。初始状态可以看做，若干个连续段可以增加 $1$ 或 $2$ 个长度，若干连续段需要减少若干个长度。我们需要最大化“一次增减 $2$ 个长度”的操作次数，贪心即可。

【CCO 2023】Travelling Trader

咕

【CCO 2023】Triangle Collection

假设我们钦定要组成 $x$ 个等腰三角形，可以贪心的凑出最大的 $x$ 对腰。检查是否合法是一个二分图匹配状物，考虑 Hall 定理，令 $a_x$ 表示长度 $\le x$ 的腰选了几对，$b_x$ 表示长度为 $x$ 的腰总共能选出多少个合法的底，则对于所有 $x$ 有 $a_x \le b_x$。

二分 $x$ 特别不好做，查询 $a_x,b_x$ 很麻烦，我们有更好的解法。

考虑这样一个过程：先不管是否合法，配出最多的腰，然后拆散一些腰作为底使其合法。

用支持区间加，全局 max 的线段树维护 $a_x-b_x$，查询时找到最大值，拆散一对腰会使得最大的 $a_x-b_x$ 减去 $3$（$a_x$ 减去 $1$，$b_x$ 加上 $2$），复杂度 $O((n+q) \log n)$。

Day 2

【CEOI2005】Depot Rearrangement

对于所有 $M$ 种物品各建立一个点，所有 $N$ 段区间各建立一个点。考虑连出一个二分图：物品连向区间表示这个区间需要一个这种物品，区间连向物品表示这个区间多出一个这种物品（如果多出多个就连多条边），更形象的说，就是用边去刻画物品的流向。

显然每个点的入度等于出度，每一个联通分量都有欧拉回路，找出后构造是容易的。

复杂度 $O(NM)$。

【KOI2023】野餐

令 $L,M,R$ 表示 left_num, my_num, right_num。

先忽略下午和晚上，我们需要找到一个函数 $f(x,y)$，满足对于任意 $x,y,z(x \neq y,y \neq z)$，有 $f(x,y) \neq f(y,z)$，每个人在上午只需要返回 $f(M,R)$。

考虑 $x,y$ 的二进制表示，找到任意一位 $x,y$ 不同的二进制位，令其为第 $d$ 位，$x$ 在这一位上的数是 $b$，令 $f(x,y)=2d+b$，如果 $f(x,y)=f(y,z)$，则 $x$ 的第 $d$ 位和 $y$ 的第 $d$ 位是相同的，与定义矛盾。

$f(x,y)$ 的值域是 $[0,2 \lceil\log A\rceil)$，其中 $A$ 是 $x,y$ 的值域。

上午下午晚上都返回 $f(M,R)$，值域是 $10^5 \rightarrow 34 \rightarrow 12 \rightarrow 8$。

但是我们没有用 $L$，如果在下午晚上返回 $f(f(L,M),f(M,R))$，值域是 $10^5 \rightarrow 34 \rightarrow 12 \rightarrow 8 \rightarrow 6 \rightarrow 6$。

这个方法有一个明显的弊端，因为 $2 \lceil \log 6 \rceil = 6$，有再多次的操作也无法缩小值域。

一个特别天才的想法：将每个数映射到一个 $01$ 个数相等的串，虽然会扩大串长，但是由于一定能找到一个不同的二进制位满足 $x$ 在这一位为 $0$，故 $f(x,y)$ 只需要返回 $d$，可以突破 $6$。

早上，值域是 $10^5$，$\binom{20}{10}=184,756$，可以映射到 $20$ 位。

下午，计算 $f(L,M),f(M,R)$ 的时候，值域是 $20$，$\binom{6}{3}=20$，可以映射到 $6$ 位。

下午，计算返回值的时候，值域是 $6$，$\binom{4}{2}=6$，可以映射到 $4$ 位。

晚上的想法比较简单，如果 $M \le 2$ 直接返回 $M$，否则返回一个不是 $L$ 也不是 $R$ 的数，这个数一定可以在 $0,1,2$ 中找到，得到满分做法。

【KOI2023】外环路 2

没有奇环，说明是二分图。

删掉最少的权值的边，变成二分图，可以看成在保持是二分图的情况下保留尽可能多的权值。

考虑 dp，$dp(i,0/1,0/1,0/1)$ 表示，考虑子树 $i$，$i$ 填了什么颜色，$i$ 子树内最左边和左右边的叶子填了什么颜色。合并 $u$ 的所有儿子的时候，令 $f(j,0/1,0/1,0/1)$ 表示，目前合并了 $j$ 棵子树，我们即将要在 $u$ 上填什么颜色，目前合并的子树中，最左边和最右边的叶子填了什么颜色。

复杂度 $O(n)$。

Day 3

【RMI 2020】Peru

假设我们已经确定了要拍哪些区间和对应的力度，按照力度降序排列，令它的影响范围为目前没有被拍的所有位置，由于所有区间长度相等，这个范围也是一个区间。

将整个序列的所有影响区间抠出来，容易发现一个影响区间所需要的力度是区间内的最大值，也就是说问题转化成：将序列 $S$ 划分成若干连续段，每一段的长度 $\le K$，最小化每一段最大值之和。

令 $dp(i)$ 表示前缀 $[1,i]$ 的答案，转移 $dp(i)=\min_{j \in [i-K,i-1]} dp(j)+\max\{S_{j+1},\cdots,S_i\}$。

再观察这个式子，发现只需要考虑 $i-K$ 的决策和 $S_j$ 是 $[j,i]$ 中的最大值的 $j$ 的决策（理由：$dp(i)$ 显然不降，在保证 $\max$ 不变的时候，选取更小的 $j$ 不劣）。把这些 $j$ 拿出来，令其为 $a_1,a_2,\cdots ,a_m$，则 $dp(i)=\min_{i \lt m} dp(a_i)+S_{a_{i+1}}$。

$i-K$ 的转移可以用滑动窗口维护；$a$ 的变化仅有：右边 push/pop，左边 pop，可以用双栈维护，复杂度 $O(n)$。

【2022 克罗地亚国家队选拔】这么牛

写了大半天的随机化，卡在了 Test #52，为什么过不去后面再说。

将所有数按模 $4$ 意义分组，令 $S_0,S_1,S_2,S_3$ 表示四个集合。

考虑全是偶数的情况，此时一定有解，因为两个 $S_0$ 中的元素，或两个 $S_2$ 中的元素，对其操作之后一定产生一个偶数，不断这样操作，不能操作的时候要么已经操作完，要么 $|S_0|=|S_2|=1$，此时将剩余两个数操作即可。全是奇数同理。

对于一般情况，先要证明一个引理：

• 若 $|S_0|,|S_2| \ge 1$ 或 $|S_1|,|S_3| \ge 1$，则能构造出解。

证明：以 $|S_0|,|S_2| \ge 1$ 为例，保留两个集合各一个元素 $x_0,x_2$，将剩下的奇数和剩下的偶数随便操作，可能会得到：

• 剩余一个奇数：此时操作 $x_0,x_2$，得到奇数，和剩下的奇数操作。
• 剩余一个偶数：偶数要么属于 $|S_0|$，要么属于 $|S_2|$，取两个属于相同集合的元素操作，得到偶数，再和剩下的偶数操作。
• 剩余一个奇数和一个偶数：将所有数设成 $4a+b$ 的形式：不妨设我们有四个数：$4a_1+0,4a_2+0,4a_3+2,4a_4+1$。
  • 可以操作 $4a_2+0,4a_3+2$，得到 $2(a_2+a_3)+1$，然后和 $4a_4+1$ 操作得到 $a_2+a_3+2a_4+1$，若 $a_2+a_3$ 为奇数，则可以和 $4a_1+0$ 操作构造出解。
  • 若将上述方法的第一步换成操作 $4a_1+0,4a_3+2$，则若 $a_1+a_3$ 为奇数，则可以和 $4a_3+0$ 构造出解。
  • 令 $a_1,a_2$ 奇偶性相同，操作 $4a_1+0,4a_2+0$，得到 $2(a_1+a_2)$，其一定属于 $S_0$，可以用上文“剩余一个奇数”的方式处理。

如果我们能构造出一个 $S_0$ 中的元素和一个 $S_2$ 中的元素，或者构造出一个 $S_1$ 中的元素和一个 $S_3$ 中的元素，随便操作后暴力解剩下的四个数，问题得以解决。

以 $S_0$ 和 $S_2$ 为例，找出所有偶数中最低的二进制位 $d$ ，满足所有数在这一位上不全部相同。任意找出两个不相同的数，不妨设两个数为：$a_12^{d+1}+b$ 和 $a_22^{d+1}+2^d+b$，操作这两个数，得到 $(a_1+a_2)2^d+2^{d-1}+b$，此时第 $d-1$ 位一定改变，将 $d$ 减去 $1$ 继续进行同样的过程，注意先判断数够不够。

复杂度 $O(n \log A)$，$A$ 是值域。

随机化过不去的原因：在 Test #52 中，$d$ 比较大，严格限定了其中很多步操作。

【2022 克罗地亚国家队选拔】这么不牛

将图看做 $100$ 个点的完全图，每条边染成了黑色或白色。

先取出任意五个节点，解出这个大小为 $5$ 的团。每三个询问一下，得到了 $10$ 个未知数和 $10$ 个方程，把它解出来。由于未知数不多，可以暴力枚举。

每次选一个点 $u$ 加入团，将团中的节点随机打乱，得到排列 $p_1,p_2,\cdots,p_k$，令 $i=1$，询问 $(u,p_i,p_{i+1})$，将其减去边 $(p_i,p_{i+1})$ 的贡献，有两种情况。

• 边 $(u,p_i)$ 和 $(u,p_{i+1})$ 同色，我们可以知道具体的颜色，令 $i=i+2$，重复此过程。
• 边 $(u,p_i)$ 和 $(u,p_{i+1})$ 异色，令 $i=i+1$，重复此过程直到找到一对同色边，找到之后可以推出前面的一些边。

有一些细节：如果找完了都没有找到同色边，那么可以任意取一个 $j$，询问 $(u,p_j,p_{j+2})$ 或 $(u,p_1,p_j)$，得到 $(u,p_j)$ 和 $(u,p_{j+2})$ 的颜色，由于 $k \ge 5$，一定能找到一个合适的询问。

我们已经将团里面的点随机打乱了，每次问到同色的概率至少是 $0.5$。即，一次询问在最坏情况下，有 $0.5$ 的概率确定两条边，有 $0.5$ 的概率确定一条边，期望确定 $1.5$ 条边，询问次数期望大约为 $\frac{n^2}{2 \times 1.5}=\frac{n^2}{3}$。

Day 4

【CCO 2021】Travelling Merchant

令 $dp(u)$ 表示从节点 $u$ 出发，最少需要多少的起始资金才能无限行走下去。转移 $dp(u)=\min_{(u,v,r,p) \in G}\{\max\{r,dp(v)-p\}\}$。

图中有环，不好处理。先考虑不断将所有出度为 $0$ 的点删掉，这个可以在反图上用拓扑排序解决。然后我们得到的图满足，只要有足够的钱，在任意节点都可以无限走下去。找出 $r$ 最大的一条边 $(u,v,r,p)$，用 $r$ 去更新 $dp(u)$，并把这条边删去。此时可能会出现出度为 $0$ 的点，继续在反图上拓扑排序更新 $dp$。

复杂度除排序外 $O(n+m)$。

【CCO 2023】Real Mountains

称一个数在山谷里，当且仅当在左边和右边都有严格比它大的数。

观察这样一个过程，将所有在山谷里的数的最小值整体 $+1$。

每次操作 $(i,j,k)$，$h_j$ 带来的代价是固定的，我们需要尽可能最小化 $h_i,h_k$ 带来的代价。先将这些数中最左边和最右边的数 $+1$，然后操作中间的数就可以令 $h_i,h_k=h_j+1$，非常划算。为了最小化最左边和最右边的数操作的代价，可以算出先左后右，先右后左的代价。这是一个求一段前缀/后缀中某个数后继的问题，可以选用自己喜欢的数据结构维护。

然而 $h$ 的值域非常大，令 $x$ 为目前的山谷里的最小值，$y$ 为 $x$ 在所有 $h_i$ 中的后继，将所有山谷里的最小值从 $x$ 加到 $y$ 的过程中，由于需要改变的数的集合不变，可以整体处理，而这个集合只会改变 $O(n)$ 次，故复杂度是 $O(n \log n)$ 的。

【CCO 2023】Line Town

部分分在暗示做法。

最关键的一个性质：考虑第 $i$ 个数 $h_i$ 在最后被换到了 $p_i$ 的位置，那么最终状态下，第 $p_i$ 个数是 $(-1)^{i-p_i}h_i$，且操作次数是 $p_i$ 的逆序对数。

先考虑 $|h_i| \neq |h_j|$ 的部分分，按绝对值从大往小枚举，当前枚举到的数，要么丢到末尾且符号为正，要么丢到开头且符号为负。令 $dp(i,0/1)$ 表示，已经枚举了前 $i$ 个数，开头的数模 $2$ 是什么。转移只需要用 BIT 优化一下计算逆序对。

再考虑 $|h_i| \le 1$，由于符号翻转很烦，需要一点点的转化去掉它。令初始状态为 $a_1,\cdots,a_n$，目标状态为 $b_1,\cdots,b_n$，对于所有奇数（偶数也行）的 $i$，将 $a_i,b_i$ 取相反数，操作就变成了“交换相邻数，没有符号翻转”（理由：转化前后对于符号的要求均为，若 $|i-p_i|$ 为偶数，需要 $a_i,b_{p_i}$ 符号相同；若 $|i-p_i|$ 为奇数，需要 $a_i,b_{p_i}$ 符号相反）。

在转化后的问题上，需要对于一个 $-1,0,1$ 的序列求出，变成某个序列（中间一段为 $0$，左右两段 $+1,-1$ 交替排列）所需要的最小交换次数。

先做单组询问：给最终状态用 $[1,n]$ 顺次标号，给初始状态中的标号满足：对于所有 $x,y$，第 $x$ 个数 $y$ 在两个状态中的标号相同。操作次数就是初始状态标号的逆序对。

对于多组询问需要一点分讨，一个稍微简单的做法是，分 $0$ 左边的数有奇数还是偶数两种情况。对于同种情况，将 $0$ 的区间往右移动两步后，标号序列的变化也仅仅是将两个数的标号移到中间一段 $0$ 的前面，很容易用 BIT 计算逆序对的变化量。

考虑满分做法：$dp$ 状态一样，按绝对值 $x$ 从大到小枚举的时候，将 $+x$ 看成 $+1$，$-x$ 看成 $-1$，绝对值小于 $x$ 的看成 $0$。有时候 $0$ 会很多，但是计算逆序对的时候只需要分别计算：$(-1,0),(1,0),(-1,1)$ 之间的贡献，额外用 BIT 维护 $0$ 的位置即可。

复杂度 $O(n \log n)$。

Day 5

【IzhO 2017】Hard route

令 $u,v$ 为我们选的两个叶子，在点 $w$ 取到所有点到 $u,v$ 路径距离的最大值（即取到题目中 $H$ 的最大值），令 $x$ 为 $u,v$ 路径上到 $w$ 距离最小的点。

枚举 $x$，将 $x$ 的所有子树（注意定根后不要漏掉上面的那棵子树）按子树内最深叶子的深度从大到小排序。取出前三个子树中最深的叶子，令深度为 $a,b,c(a \le b \le c)$，最大化 $hardness$ 一定是令 $u=a,v=b,w=c$，此时 $hardness=c(a+b)$（理由：$hardness$ 可以写成 $ab+ac+bc-(作为u,v的点的乘积)$，最小化减去的部分即可）。

计算方案数有点麻烦，先换根 dp 预处理出每个节点子树内和子树外，距离最远的叶子和叶子个数。计数的时候数出 $a,b,c$ 有多少个可选方案，分 $a,b$ 是否相等，$b,c$ 是否相等讨论。

幸运的是，计算取到最大值的方案时不会被重复计算。证明只需要证对于任意取到最大值的 $u,v$，只有一个合法的 $w$。若有多个，则将 $u,v$ 其中之一替换成另一个 $w$，能变的更优。

复杂度 $O(n)$ 或 $O(n \log n)$，取决于实现，均可过。

【IOI2009 中国国家队选拔】$N^2$ 数码游戏

对于测试点 $1$，可以爆搜，复杂度 $O((N^2)!poly(N))$。

对于测试点 $2,6$，可以剪十六个小纸片玩，观察发现前若干次操作一定是转矩形的最外面一圈，类似于 UUULLLDDDRRRUUULLLDDDRRR... 的过程，当把 $1,2,3,4$ 转到最上面的时候，剩余部分可以暴力或者用下文方法解。

考虑 bfs，设计一个估价函数，每一层只保留一些可能比较优的状态，可以试试如下几个。

• 每个数到终点的曼哈顿距离，的和/平方和/立方和/平方根和。
• 重新定义距离：$(x_1,y_1),(x_2,y_2)$ 的距离为 $(|x_2-x_1|+1)(|y_2-y_1|+1)$，算和/平方和/立方和/平方根和。
• 将距离乘上 $0$ 到这个数的距离，算和/平方和/立方和/平方根和。

实测和/平方根和比较优秀。

这样子会出现一个现象，目前队列中估价函数最低的会在两个数中反复横跳，每次扰动一步显然是不够的。可以在模 $2/3/4=0$ 的某一轮中删减状态。

需要调一调删除的频率和保留的状态数。

当然估价函数并不是特别合理的，比如有两个相邻但位置相反的数，空格又隔得特别远。其实这种状态是很劣的，但这几种估价都会认为这种状态很优秀。或者说多个路径交错在一起，也是特别劣的，但很难设计函数把它们区分开，欢迎各位来交流更好的估价函数。

题外话：关于多项式复杂度的构造方法，也是我的赛时做法：

• 大概思路是按照 $1,2,\cdots,N^2$ 的顺序归位，已经归位的不去动它。
• 对于前 $N-2$ 行的前 $N-2$ 列，记录状态 $(ux,uy,ex,ey)$，表示目前需要归位的数和空格分别在什么位置，爆搜就行。
• 对于前 $N-2$ 行每一行的最后两列，并不能保证上一条能跑出解，但是我们一定可以把棋盘变成下面的形状之一（. 表示空格，? 表示没被归位的数字）：

1 2 . 3
? ? ? 4

1 2 4 .
? ? 3 ?

所以记录状态时记录两个数的位置和空格的位置，也一定能得到解。

• 对于后两行，由于最后一行极有可能顺序不对，上述方法不能使用。从左往右枚举列，同时归位这一列的两个数，假设 $N=4$，目前归位 $9,13$，只需要在第三行令 $13$ 和 $9$ 挨在一起，然后转下来就行，也可以记录三个坐标爆搜。

1 2 3 4
5 6 7 8
? 13 9 ?
? ? ? .

复杂度 $O(n^7)$。肯定有更优的做法。

但这样构造，我只在测试点 $9$ 得到了 $3$ 分，其余均为 $2$ 分。

【2022 克罗地亚国家队选拔】Mapa

直觉上特别违背信息论，因为只能传递 $3000$ bits，而传递 $y_i$ 已经需要 $3000$ bits。

假设解密时知道了所有 $x_i$，那么只需要在加密的时候按 $x_i$ 排序后传递 $y_i$，正好符合要求。

怎么不传递 $x_i$ 呢？或者将给定的键值对转化成一些固定的 $x_i$，比如将所有 $x_i$ 变成 $[1,n]$ 的排列。

拉格朗日插值！

由于 $n$ 个键值对 $(x,y)$，唯一确定了一个 $n-1$ 次多项式，将这个多项式求出来，传递 $[1,n]$ 的点值（传系数也行），解码的时候插值一下，由于插值有除法，可以在模 $10^9+7$ 下算，需要的位数不变。

Day 6

【KOI 2023】出租车

一个非常直观的结论：换乘一定是从 $B_i$ 大的换到 $B_i$ 小的，也就是说经过的所有点（除了终点），$B_i$ 是递减的。

将所有 $i$ 按 $B_i$ 从大到小排序，令 $dp(u)$ 表示到达点 $u$ 所需的最小代价，转移：$dp(u)=\min_{v|B_v \gt B_u}\{ dp(v)+A_v+B_v \cdot dist(u,v)\}$。

将 $dp(v)+A_v+B_v\cdot dist(u,v)$ 中，$B_v$ 看成斜率，$A_v+dp(v)$ 看成截距，$dist(u,v)$ 看成自变量 $x$。考虑点分树，在点分树上的所有点上维护一个凸包，计算完 $dp(v)$ 之后，在点分树上所有 $v$ 的祖先 $fa$ 上的凸包，加入直线 $y=B_vx+(B_v \cdot dist(v,fa)+A_v+dp(v))$，因为 $B$ 是递减的，用单调栈维护凸包，查询时二分查询 $x=dist(u,fa)$ 处的 $y$，复杂度 $O(n \log^2 n)$。

有个小细节，路径上经过的所有点中，终点不保证是 $B_i$ 递减的，需要额外计算最后一步，可以用一样的方法计算。

【UOI 2023】乌克兰

非常直观的感觉，操作次数不会特别的多，考虑证明上界为 $3$。

令 $a_i$ 为给定的数组，$s_i$ 为 $a_i$ 的前缀和，令 $s_x,s_y$ 分别为 $s_i$ 的最小值和最大值。

• 若 $x \gt y$，则用操作 $1$ 令 $x \lt y$。
• 不妨令 $s_x \lt 0,s_y \gt 0$，先用操作 $2$ 操作 $[x+1,n]$，被操作的所有数 $u$ 会变成 $s_u-s_x$，是非负的，因为 $s_x \lt 0$，故最大值的位置仍然在 $[x+1,n]$ 中，令 $y$ 为新的最大值出现位置，用操作 $3$ 操作 $[1,y]$，被操作的所有数 $v$ 会变成 $s_y-s_{v-1}$，同样非负。

分情况讨论：

若答案为 $0$，当且仅当所有 $a_i \ge 0$。

若答案为 $1$，不妨要么进行一次 $1$ 操作，要么存在一个区间满足前/后缀和 $\ge 0$，且区间外的所有数 $\ge 0$。而在区间左右两端加上非负数是不劣的，故只要判断前/后缀和数组是否都 $\ge 0$。

若答案为 $3$，直接构造。

若答案为 $2$，分两种操作类型相同/不同讨论。

若相同，令两次都为 $2$ 操作，我们需要找到一个区间，满足将这个区间替换成前缀数组后，整个序列的前缀数组均 $\ge 0$。令第一步操作的区间为 $[l,r]$，则 $[1,l-1]$ 的前缀数组需要 $\ge 0$，令 $l=1$，是不劣的，故第一次操作一定是操作一个前缀。枚举这个前缀，需要维护：单点修改，求前缀和数组最小值。用线段树维护前缀和数组，单点修改对应了区间加减，查询对应了全局最小值。

若不同，不妨令第一次为 $3$ 操作，第二次为 $2$ 操作，考虑分治，令当前区间为 $[l,r]$，中点为 $mid$，令 $a_i$ 为原数组，$s_i$ 为前缀和。

对于所有 $i \in [mid+1,r]$ 计算：

• $A_i$：若第一次操作的右端点为 $i$，则操作完后 $a_{mid+1}=A_i$。计算是容易的。
• $B_i$：若右端点为 $i$，第一次操作完之后，$[1,mid]$ 的和至少是多少才能保证对于所有 $j \in [mid+1,n]$，有 $s_j \ge 0$。$B_i$ 由两部分：$[mid+1,r],[r+1,n]$ 确定，$[r+1,n]$ 是容易计算的，预处理原数组中 $s_i$ 的后缀最小值，计算 $[mid+1,r]$ 中后缀和的和即可。$[mid+1,r]$ 有点麻烦，考虑一个位置 $j$，第一次操作完之后，$[mid+1,j]$ 中的和 $t_j$ 会随着 $r$ 的增加发生什么变化：令新加入的数为 $a_r$，则对于所有 $j \in [mid+1,r-1]$，$t_j$ 会增加 $(j-mid)\cdot t_j$。将所有 $j$ 看成一条直线 $y=(j-mid) \cdot x+b$，计算 $B_i$ 可以看做查询凸包上 $x=s_i-s_{mid}$ 处的 $y$ 值。可以用李超树或单调栈维护。

对于所有 $i \in [l,mid]$ 计算：

• $D_i$：原序列中 $[i,m]$ 后缀和之和。
• $E_i$：第一次操作完之后，若左端点为 $i$，则 $a_{mid+1}$ 至少为多少才能保证 $[1,mid]$ 中所有前缀和非负。同样的考虑将 $l$ 减少 $1$ 之后，所有位置 $j$ 的前缀和 $t_j$ 会发生什么变化，这个也可以写成一条直线 $y=(j-i+1)\cdot x+b$，我们需要找到一个最小的 $x$ 使得对于所有直线均有 $y \ge 0$，即 $(j+1)x+b \ge i \cdot x$，可以看做求直线 $y=i \cdot x$ 和凸包的交点，用单调栈+二分维护，如果不介意多个 $\log$ 的话也可以用李超树维护+二分，也能擦着时限过。
• $F_i$：原序列中 $[1,i-1]$ 的和。

一个合法的第一次操作区间 $[L,R]$ 需要满足：

• $[1,L-1]$ 的前缀和数组均 $\ge 0$，很好判断。
• $A_R \ge E_L$
• $D_L+F_L+A_R(mid-L+1) \ge B_R$。

三个限制条件分别令 $[1,L-1],[L,mid],[mid+1,n]$ 三段满足条件。将所有满足第一条限制的 $L$，和所有 $R$ 搞出来，按 $A_R$ 或 $E_L$ 排序。第三个限制，对于所有 $L$ 可以看成直线 $y=(mid-L+1) \cdot x+(D_L+F_L)$，对于所有 $R$ 可以看做查询 $x=A_R$。

复杂度 $O(n \log^2 n)$。

【2022 克罗地亚国家队选拔】喝喝粥

将每个所有人帽子颜色的状态 $u$ 拆成两个节点 $u_0,u_1$。若两个状态 $x,y$ 仅有一位 $d$ 不同，不妨令 $x$ 的第 $d$ 位为 $0$，则在 $x_0,y_1$ 之间连一条无向边，含义是第 $d$ 个人无法区分 $x,y$ 这两个状态，需要给这条边定向：指向 $x_0$ 表示猜 $0$，指向 $y_1$ 表示猜 $1$。

定完向后，对于一个度数为 $deg$ 的节点，至少有 $\lfloor deg/2 \rfloor$ 条边指向它。我们可以想到欧拉回路：建立一个虚点，先对于所有度数为奇数的点（一定有偶数个）向这个虚点连边，跑出欧拉路，按照欧拉路定向，每个点入度和出度相等，均为 $\ge \lfloor deg/2 \rfloor$，符合题意。

复杂度 $O(2^NN)$。