欢迎来到我的博客！

因为本人太菜所以放一点可能相关的思考在这里（自己都不一定能记得啥时候回来看

有二元关系时可以尝试连边

字符集小就考虑枚举字符关系

位置关系不重要就先排序

T1-空洞骑士（bit）​

题面​

多组询问，每组询问给定一对正整数 $a,b(a\leq b)$，在闭区间 $[a,b]$ 内所有整数中，找到二进制表示中 $1$ 个数最少的数。如果有多个这样的数，找到其中最小的那一个。

$1\leq T\leq2\times10^5,1\leq a\leq b\leq10^{18}$。

题解​

考虑直接按位贪心求解。

从最高位开始，在保证 $\leq b$ 的情况下，尽量在高位放 $1$，并且得到的值一旦 $\geq a$ 就跳出。

此时可以保证最终得到的数可以保证在 $[a,b]$ 区间内，并且 $1$ 的数量最少。

再考虑如何求出最小值。

从最高位开始枚举，显然尽量要将 $1$ 往低位放，故除非后续位数全部在最高位放 $1$ 直到放完也 $<a$，否则不放，显然一定最优。

复杂度 $O(T\log V)$。

T2-丝之歌（infected）​

题面​

有一棵 $n$ 个节点的树，选择两个节点将树切断，得到三个连通块。

设三个连通块的大小分别为 $a,b,c$，求出 $\max\{a,b,c\}-\min\{a,b,c\}$ 的最小值。

$3\leq n\leq2\times10^5$。

题解​

三个连通块不好求解，考虑固定其中一个连通块的断点。

此时显然使另外两个连通块大小尽量接近最优，因此我们将所有点的子树大小（记为 $siz$）存入 $\text{multiset}$ 二分求解。

然而当另一个断点是当前断点祖先时，其 $siz$ 包含当前点的 $siz$，所以我们开两个 $\text{multiset}$，分别存储祖先节点和非祖先节点，祖先节点更新答案时减去当前节点的 $siz$ 即可。

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

T3-即将于今晚（skill）​

题面​

有编号为 $1,2,3$ 的三个值，初始时都为 $0$。

可以用 $n$ 次操作对值进行修改，每次操作为：

• 选择其中一个值，设选择的值为 $j$，使其值增加 $a_{i,j}$。
• 对于另外两个值，如果已经有 $x$ 次没有进行操作，则使其值减少 $x$。
• 三个值都不会小于 $0$，会始终和 $0$ 取 $\max$。

求在 $n$ 次操作结束后，三个值之和的最小值。

• $1\leq n\leq 1000$。
• $\forall i,0\leq a_i\leq 10000$。

题解​

我们注意到两个性质：

• 如果一个值被修改过，那么将它重新修改到 $0$ 显然不优（可以将修改它的操作变为修改其他值）。
• 对于一个数，它修改后最多被搁置的轮数是 $\sqrt{V}$ 级别的，因为被搁置 $x$ 轮后产生的减值是 $\frac{1}{2}x(x+1)$，而值不会被减到 $0$。

因此我们可以设计状态为 $f_{i,j,k_1,k_2}$，表示进行到第 $i$ 次操作时，本次操作选择的是第 $j$ 个值，下一个值被搁置了 $k_1$ 轮，下下个值被搁置了 $k_2$ 轮。

每个状态向下一个状态的转移显然只有三种可能：

1. 仍选择当前点。
2. 选择下一个点。
3. 选择下下一个点。

此时的转移是显然的。

注意：一个点没有被修改过之前不会产生减法，所以如果 $k_1$ 或 $k_2$ 为 $0$，其转移方向应该为 $0$。

最后我们注意到 $i$ 状态只会从 $i-1$ 转移过来，所以采用滚动数组。

复杂度 $O(n\sqrt{V}^2)=O(nV)$。

T4-十点发售（orandgcd）​

题面​

给序列 $a_1,\cdots,a_n$，$b_1,\cdots,b_n$，$b_1,\cdots,b_n$。

定义区间 $[l,r]$ 的价值为 $a_l,\cdots,a_r$ 按位与，$b_l,\cdots,b_r$ 按位或，$c_l\cdots,c_r$ 的最大公因数，这三者的乘积。

$m$ 次查询，每次查询给出区间 $[l,r]$，查询满足 $l\leq l'\leq r'\leq r$ 的 $[l',r']$ 的价值之和。

结果对 $2^{32}$ 取模。

$1\leq a_i,b_i,c_i\leq n\leq10^6,1\leq l,r\leq n,1\leq m\leq5\times10^6$。

题解​

考虑扫描线，扫到 $r$ 时维护 $A_i,B_i,C_i$ 表示区间 $[i,r]$ 对应运算的答案，$s_i$ 表示左端点在 $[1,i]$ 内，右端点在 $[1,r]$ 内的区间的权值和（相当于 $A_kB_kC_k(k\leq i)$ 的历史和，虽然这道题并不需要用到历史和），那么询问 $[l,r]$ 的答案可以拆分为扫到 $r$ 时的 $s_r−s_{l−1}$。

一个并不是很显然的结论是：扫描线 $r\rightarrow r+1$，$A_iB_iC_i$ 的值只有一段 $[r−p,r]$ 会 改变，然后这个 $p$ 的大小是均摊 $O(\log V)$ 的。具体证明可以考虑拆位，每一位会在什 么时候改变这个乘积。

于是我们就可以维护 $D_i=A_iB_iC_i$ 这个数组了，对于 $[1,r−p)$ 这一段的 $D_i$ 没有发生改变，但是 $s_i$ 改变了，直接历史和复杂度又太巨大了，可以考虑将 $s_i$ 的定义式改为 $s_i=val_i+D[1,i]*r$，这样只要前缀 $D$ 不改变，$s$ 也不用修改，需要求值的时候算一下就行。

总复杂度 $O(n\log V+m)$。另外本题有一个数据不变，时限 3s->1s 的版本（P9335）。

T1-那头与出题（data）​

题面​

那头在出题时发现他不会写一道题的 generator，需要你进行帮助。

我们称一个对无限大网格图的黑白染色方案是合法的当且仅当所有黑色点四联通，所有白色点也四联通。

具体的，我们在 $(x_1,y_1)$ 与 $(x_2,y_2)$ 之间连边当且仅当 $|x_1-x_2|+|y_1-y_2|=1$ 且两个点颜色相同，如果得到的图的联通块数为 $1$ 或 $2$，那么染色方案合法，否则不合法。

初始时所有点都是白色的，你需要维护 $q$ 次修改。

第 $i$ 次修改有两个参数 $x_i,y_i$ 表示尝试把 $(x_i,y_i)$ 涂黑（保证这个点当前是白色)。如果涂黑后染色依然合法则执行该操作，否则放弃该操作。

你需要求出每次操作是否被执行。

$1\leq q,x_i,y_i\leq3\times10^5$。

题解​

每次新加入的点是否能让黑色保持联通是易于判断的，判断新加入的黑点上下左右是否有其他黑点即可。

考虑如何判定白色能否保持联通，注意到只需要考虑新加入点周围 $3\times3$ 九宫格内的情况即可，九宫格外的白点并不会受到影响。

因此每次检查新加入一个点后九宫格内黑色白色的连通性即可。

T2-那头与分值（score）​

题面​

那头需要完成 $n$ 道题目，第 $i$ 道题目难度为 $a_i$。那头有一个智慧值 $X$，他完成所有题目需要 $(a_1+X)\oplus(a_2+X)\oplus\cdots\oplus(a_n+X)$ 的时间。

那头会 $q$ 次调整自己的智慧值，你需要每次告诉他完成所有题目会完成的时间。即给定 $x_i$，你需要求出 $(a_1+x_i)\oplus(a_2+x_i)\oplus\cdots\oplus(a_n+x_i)$ 的值。那头不希望等待，所以本题部分测试点要求强制在线。

$n\leq2\times10^5,q\leq5\times10^5,t\in\{0,1\},a_i,x_i'<2^{60}$。

题解​

考虑决策答案每一位是 $0$ 还是 $1$。对于第 $i$ 位，需要查询有多少个 $i$ 满足 $a_i+X$ 的第 $i$ 位为 $1$。可以转化为统计进位次数。这相当于查询 $a_i\&(2^i−1)$ 在一个区间内的值的个数， 可以预处理 $b_{k,i}=a_i\&(2^k−1)$ 并对 $b_k$ 排序然后二分查询。

复杂度 $O((n+q)\log n\log V)$， 期望得分 $60$ 分。

尝试优化以上算法。预处理部分容易优化，可以通过归并做到 $O(n\log V )$（但这部分 不是瓶颈，不优化也可以通过）。难点在于优化询问。如果允许离线，可以对于每个 $x$ 也预处理 $x\&(2k−1)$ 并排序，然后双指针扫描回答询问，复杂度 $O((n+q)\log V)$，期望得分 $85$ 分。

如果要求强制在线，我们无法对 $x_i$ 排序预处理，所以只能尝试通过本次询问第 $k$ 位 的结果推出 $k+1$ 位的结果。考虑一次询问是要求 $b_{k,i}<2^{k+1}−x\&(2^{k+1} − 1)$ 的最大的 $i$ 的位置。当 $k\leftarrow k+1$，式子左侧的值要么不变，要么增加 $2^k$。这启发我们预处理 $c_{k,i,0}=\max{x|b_{k+1,x}\leq b{k,i}}$，$c_{k,i,1}=\max{x|b_{k+1,x}\leq b_{k,i}+2^k}$ 辅助转移。如果可以得到以上数组，每次 $k\leftarrow k+1$ 可以直接通过调用 $c$ 完成。$c$ 可以和 $b$ 一起在归并时求出。

复杂度 $O((n+q)\log V)$，期望得分 $100$ 分。

T3-那头与观测（observation）​

题面​

那头住在一棵 $n$ 个点的树上。

那头在树的每个节点上都放置了一个头。其中 $i$ 号节点上的头为 $i$ 号头，其高度为 $i$。对于整数 $1\leq h\leq n$，称两个不同的头在视线高度为 $h$ 时可以互相望见当且仅当：

• 两个头的高度都 $\geq h$。
• 两个头所在节点的简单路径上没有其他头或其他头的高度都 $<h$。

对于每个整数 $1\leq h\leq n$，求有多少个有序三元组 $(i,j,k)$ 满足：

• $i,j,k$ 互不相同。
• 在视线高度为 $h$ 时，$i$ 号头和 $j$ 号头可以互相望见且 $j$ 号头和 $k$ 号头可以互相望见。

$2\leq n\leq10^5$。

题解​

考虑按编号从小到大删点。时刻维护一个 $n−h+1$ 个点的无向图 $G$。$G$ 中 $(u,v)$ 有边当且仅当 $u,v$ 在视线高度为 $h$ 时可以互相望见。令 $u$ 在 $G$ 中的度数为 $d_u$，则答案为 $\sum_{u} d_u(d_u−1)$。

直接建边边数过多，且维护图并不方便。考虑建一些虚点让图变成一棵树。删点开始前，对于原树上的一条边 $(u_i,v_i)$，在新树上连接 $(u_i,n+i)$ 和 $(v_i,n+i)$。设编号 $>n$ 的为白点，$\leq n$ 的为黑点。删除 $u$ 相当于把 $u$ 的子白点与它的父白点合并，可以使用并查集维 护。容易发现新树上的点是黑白相间的，且对于 $G$ 中的边 $(u,v)$，新树上一定存在恰好一个白点 $x$ 满足 $(u,x),(x,v)$ 这两条边在新树上存在。为了方便，以 $n$ 作为新树的根，这样根一定不会被删掉。

考虑如何算答案。把三元组 $(a,b,c)$ 变成 $(a,x,b,y,c)$（$x,y$ 是白点）。令 $f_u$ 为白点 $u$ 的 黑儿子个数，分情况讨论：

• 当 $x=y$ 时，相当于在 $x$ 的邻点中选 $a,b,c$，$x$ 的邻点有 $f_x+1$ 个（因为要算上他的 父亲）。故对答案的贡献为 $\sum_{x\in W}(f_x+1)f_x(f_x−1)$，其中 $W$ 为白点点集。
• 当 $x\not=y$ 且 $x,y$ 为 $b$ 的儿子时，相当于分别在 $x,y$ 的儿子中选 $a,c$，贡献为 $\sum_{b\in B}\sum_{x,y\in son_b,x\not=y}f_xf_y$。 即 $\sum_{b\in B}\left(\sum_{x\in son_b}f_x\right)^2−\sum_{x\in son_b}f^2_x$。其中 $son_u$ 为 $u$ 的儿子集合，$B$ 为黑点点集。
• 当 $x$ 为 $b$ 父亲，$y$ 为 $b$ 儿子时，相当于在 $x$ 的邻点中选 $a$，在 $x$ 的儿子中选 $b\not=a$，$y$ 中选 $c$。答案为 $\sum_{x\in B}2(f_x + 1 − 1) \sum_{b\in son_x}\sum_{y\in son_b}f_y$。乘二是因为三元组是有序的，$(a,c),(c,a)$ 应该被算两遍。

每次删除一个点会影响其下一级儿子与上三级父亲。因此对于一个白点维护其下一级， 下三级信息，对于一个黑点维护其下两级信息即可。具体地，可以令 $g_u=\sum_{v\in son_u}f_v$，$h_u=\sum_{v\in son_u}g_v$。删除 $u$ 的复杂度为并查集的复杂度加上遍历 $u$ 的儿子的复杂度。

T4-那头与方程（equation）​

题面​

给定正整数 $n,a,b,c,d$。

请判断是否存在非负整数 $x$，使得对于所有 $k=0,1,\cdots,n-1$，都有 $x\equiv a+kb(\bmod c+kd)$。如果存在，请输出所有满足条件的 $x$ 中最小的一个对 $998244353$ 取模的结果；如果不存在，请输出 $-1$。

$2\leq n\leq 10^6,1\leq a,b,c,d\leq 2\times10^6$。

题解​

先考虑 $\gcd (c,d)=1$ 的情况。

将式子两端同乘 $d$，得到 $xd\equiv ad+bdk (\bmod c + dk)\rightarrow xd\equiv ad − bc (\bmod c + dk)$。

此时题目条件为 $xd\equiv ad − bc (\bmod M)$，其中 $M = \text{lcm}^{n−1}_{i=0}(c+d_i)$。

即找到一个最小的 $y$ 使得 $S=My+((ad−bc)\bmod M),S\geq 0,S\equiv0(\bmod d)$，则此时 $x=\frac{S}{d}$。

我们尝试将 $M$ 的质因子筛出来。 若 $\gcd (c+d_i,c+d_j)\not=1(i<j)$，则存在 $p,p|(c+d_i),p|(c+d_j)$，则 $p|d(j−i)$。

若 $p|d$，则根据 $p|(c+d_i)$ 显然有 $p|c$，与条件 $\gcd(c,d)=1$ 矛盾。

所以 $p|(j−i)$，即每个 $c+dk$ 仅存在 $\leq n$ 的质因子，以及有可能含有唯一的 $>n$ 的质因子。

对于 $\leq n$ 的质因子 $p$，我们只需找到最小的 $k$ 使得 $p|(c+dk)$（这个可以 $\text{exgcd}$ ），然后任意满足 $p|(c+dx)$ 的 $x$ 一定可以表示为 $x=k+p·t$。

求出了 $M$ 的质因子表示后，因为有 $\gcd(M,d)=1$，我们就可以枚举 $y\in [0,d]$ 来试了。这里需要分讨 $M$ 的大小以及 $ad−bc$ 的正负性，具体可详见 std。

最后的问题是，$\gcd (c,d)\not=1$ 怎么办？令 $\gcd(c,d)=s$，容易发现 $b\equiv0(\bmod s)$，这是判断是否有解的充要条件。

然后可以求得子问题 $x'\equiv \lfloor \frac{a}{s}\rfloor+k·\frac{b}{s}(\bmod\frac{c}{s}+k·\frac{d}{s})$，最终答案为 $x=x'·s+(a\bmod s)$。

T1-删树游戏（game）​

题面​

有一棵由编号为 $1\sim n$ 的 个节点构成的有根树，其中 $1$ 为根节点，$i$ 号点的父亲为 $p_i$。此外，每个节点都有一个互不相同的整数权值，$i$ 号节点的权值为 $a_i$ 。保证 $a$ 为 $1\sim n$ 的一个排列。

我们从 $1$ 出发，每次移动到当前节点的子节点中权值最小的一个。如此重复，直到到达某个叶子节点。这样得到的路径记作 $S=[S_1,S_2,\cdots,S_k]$，我们称其为特殊路径。

定义一次删除操作如下：

• 设当前树的特殊路径为 $S=[S_1,S_2,\cdots,S_k]$。
• 令 $i$ 从 $1$ 到 $k-1$ ，依次执行：交换 $a_{S_i}$ 与 $a_{S_{i+1}}$。
• 删除树中 $S_k$ 与其父亲相连的边。

我们对这棵树进行 $n$ 次删除操作，你需要在每次操作前求出 $1$ 号点的权值 $a_1$。

$1\leq n\leq3\times10^5$。

题解​

定义删除序列 $S$，$S_i$ 为这一棵树第 $i$ 操作前根节点的权值。

对于一个点 $u$，设它操作选中了子节点 $son$ 多次，那么 $a_{son}$ 的变化一定形如 $son$ 子树的删除序列。

那么求 $u$ 子树的操作序列相当于先加入 $a_u$，然后把子节点的删除序列归并起来。

注意到这个删除序列就是 $u$ 子树的一个 BFS 序，而且我们要最小化这个 BFS 序的权值的字典序。

用堆维护 BFS 即可。每次取出最小权值点后加入所有的子节点。

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

T2-身份猜测（identity）​

题面​

这是一道交互题。

现有 $n=a+b$ 个人，编号为 $0\sim n-1$。其中恰有 $a$ 个人是诚实的，$b$ 个人是不诚实的。每个人都清楚所有人的身份，但你知道的仅有 $a$ 和 $b$ 的值。你需要去确定每个人的身份。

如果你在已知 $a,b$ 的情况下无法通过询问确定所有人的身份，则报告不可能。

否则，你可以进行不超过 $n^2$ 次询问。每次给定 $x$ 和 $y$，向 $x$ 询问 $y$ 的身份，交互库返回规则如下：

• 如果 $x$ 是诚实的，那么 $x$ 会如实返回 $y$ 的身份。
• 如果 $x$ 是不诚实的，$x$ 会任意选择回答。注意 $x$ 可以按照某种策略回答。

交互库会通过你的询问次数评分。

• 如果你未能正确判断有无解，或交互过程不合法，得 $0$ 分。
• 如果无解，得 $100$ 分。
• 否则，如果你返回的身份不正确，得 $25$ 分。
• 否则，你的得分由查询次数 $q$ 决定：

$a+b\leq 1000$ 且 $a,b\geq 1$。

题解​

一个观察是，我们能分辨身份当且仅当 $a>b$。

如果 $a\leq b$，那么我们可以从 $b$ 个假的人中选出 $a$ 个人，对这 $a$ 个人询问时按照这 $a$ 个人为真，其他都为假来回答。然后就无法判断这 $a$ 个人是真是假。

如果 $a>b$，那么对于每个人 $i$，我们询问其他所有人对他的评价。如果有 $>b$ 个人认为他是真的，那 么就是真的，否则即为假。注意到我们可以认为 $i$ 声称 $i$ 是真的，那么只要做 $2bn$ 次。

考虑去找一个真的人，然后再通过他问出所有人的身份。

因为 $a>b$，考虑类似摩尔投票的思路。

如果 $x$ 认为 $y$ 是假的，那么 $x$ 和 $y$ 中有至少一个为假，可以直接删除。

否则，如果 $x$ 和 $y$ 都认为对面是真的，那么 $x$ 和 $y$ 的种类相同。

于是有一个 $3n$ 次的做法：

• 我们维护集合 $S$，满足 $S$ 中的人的种类相同。加入一个人 $i$ 时，讨论和集合中任意一个人 $j$ 的关系。
• 如果 $i$ 认为 $j$ 假或 $j$ 认为 $i$ 假，那么可以直接删除 $i$ 和 $j$。
• 如果 $i$ 和 $j$ 都认为对面是真的，那么就把 $j$ 加入 $S$。

考虑优化。我们不需要维护一个身份相同的集合，而是维护一条链 $S_1,S_2,\cdots,S_k$，满足 $S_i$ 认为 $S_{i+1}$ 是真的。

实际上，$S_{1\sim k}$ 的真实身份一定是一段前缀是假的，剩下一段后缀是真的。

那么每次我们加入 $i$ 时，只要看 $S_k$ 是否认为 $i$ 是真的。如果是，则加入 $S$，否则删除 $S_k$ 和 $i$。

因为 $a>b$，而我们每次删除的 $S_k$ 和 $i$ 中至少有一个是假的，因此最终的 $S$ 一定包含真人，即 $S_k$ 一 定为真。

那么我们再拿 $S_k$ 把所有人问一遍即可。询问次数 $2n$。

T3-序列计数（count）​

题面​

给定一个长度为 $n$ 的自然数序列 $a$，满足 $0\leq a_i\leq v$。

序列还需满足 $m$ 条限制。

第 $i$ 条限制为 $\max_{l_i\leq j\leq r_i}a_j=x_i$。

请输出合法的序列 $a$ 的个数，对 $10^9+7$ 取模。

题解​

对于第 $i$ 个限制，它首先约束了 $a_{l_i\sim r_i}$ 都是不超过 $x_i$ 的。

记 $lim_i$ 为 $a_i$ 的上界。这个可以直接并查集预处理。

考虑对值域扫描。

对于一个 $t$，我们在处理 $x_i=t$ 的限制时，$lim<t$ 的点都是不用管的。因为它们不可能成为一个区间的 $\max$。因此我们可以取出所有 $lim=t$ 的点和 $x_i=t$ 的限制。

那么这时限制就变成一个区间必须包含至少一个 $t$ 的点。

考虑 $dp_i$ 表示 $a_i=t$，此时 $i$ 之前的点方案数。

那么下一个 $=t$ 的点 需要满足不存在区间满足 $i\leq l\leq r\leq j$，这样的 $j$ 形如一段前缀，可以差分解决。

时间复杂度 $O(n\log n+V)$。

T4-树上查询（tree）​

题面​

有一棵由编号为 $1\sim n$ 的 $n$ 个节点构成的有根树，边有边权。$1$ 为根节点，节点 $i$ 的父亲为 $p_i$。对于 $2\leq i\leq n$，$i$ 与 $p_i$ 之间的边权为 $a_i$。

定义 $f(u)$ 为 子树内经过 $u$ 的最长链长度。

进行 $q$ 次操作，每次将一条边的边权加上一个正整数。

在第一次操作前和每次操作后，输出

• $1\leq n,q\leq10^5$。

• $2\leq i\leq n$ 时 $1\leq p_i<i,0\leq a_i\leq 10^9$。

• 每次操作 $1\leq x\leq n,1\leq v\leq 10^9$。

题解​

$f_u$ 是 $u$ 子树内以 $u$ 为端点的最长链和与最长链无公共边的次长链之和。

对于每一个点 $u$，我们记录 $mx_u,sec_u$ 为子树内与 $1$ 距离最大值和次大值。这里次大值到 $x$ 的链需要 $mx$ 和最大值的无公共边。

考虑动态维护长链剖分，那么子树的 $mx$ 就是实链上儿子的 $mx$，次长链 $sec$ 就是虚儿子的 $mx$ 的最大值。

对于一次修改 $x$，我们先对 $x$ 子树内的 $mx$ 和 $sec$ 整体加 $v$。

然后找到 $x$ 子树内最大的深度，对于 $x$ 的所有祖先去更新。它对于长剖的影响是把 $x$ 到根链上一段后缀 变成实链。

这个是和 LCT access 类似的，一个结论是虚实边变化次数是 $O(q\log n)$ 的。证明考虑轻重链剖分，这 个就是在 dfs 序上颜色段均摊。

那么考虑去数据结构统一维护实边，暴力修改虚边。

一条实链，操作相当于对一条链的 $mx$ 加上 $v$。

对于一条虚边，操作相当于对于单点查询 $mx$ 和 $sec$，然后进行单点改。

于是我们需要支持：

• 子树加，查子树最大深度。
• 对于 $mx$ 子树加、链加，查单点。
• 对于 $sec$ 子树加，查单点。
• 动态修改一个点是否是实儿子。
• 查询一个点所在长链顶点。

第一条线段树维护，第二三条可以树状数组维护。

第四五条 std 用了倍增树状数组维护，复杂度 $O(q\log^3n)$。常数较小，可以通过。

实际上也可以用一些办法去掉一个 $\log$，做到 $O(q\log^2n)$。

T1-序（ryvius）​

题面​

对于一个长度为 $n$ 的正整数数列 $a$，$a$ 是好的当且仅当对任意 $1\leq i<n,a_i\not=a_{i+1}$。

现在有一个好的数列 $a$，可以对这个数列执行以下操作：

• 选择一个位置 $i(1\leq i\leq n)$ 和一个正整数 $x$，将 $a_i$ 变为 $x$，需要保证每次操作后这个序列都是好的。

要让整个序列操作完之后只有两种不同的数值，求至少要操作多少次。

$1\leq T\leq10^5,1\leq n\leq2\times10^5,2\leq \sum n\leq 2\times10^5,1\leq a_i\leq n$。

题解​

考虑到序列的最终形态是两个数 $a,b$ 交替出现，于是将序列按位分为奇偶两部分。

考虑对于两个数，将序列调整到对应状态的最小次数，显然由两个部分组成：

• 序列中不满足最终形态的数的数量
• 存在这两个数相邻的情况数量

于是考虑枚举偶数位并统计奇数位贡献，对于不存在第二种情况的数对，可以直接选择出现次数最多的奇数位，显然此时结果最小。

对于存在第二种情况的数对，因为这样的数对显然不超过 $O(n)$ 个，因此可以用 map 维护，直接枚举。

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

T2-破（kon）​

题面​

放学后茶会的几人决定去毕业旅行！但是她们关于该去哪里旅行有一点小分歧，所以她们决定用阿弥陀签来抽签决定目的地。话虽这么说，但是 Yui 希望操纵抽签结果， 所以她来找你帮忙了！

上面是一个简化版的阿弥陀签的示例。一个阿弥陀签由 $n$ 条编号为 $1\sim n$ 的竖线和若于条高度互不相同的横线构成，每条横线在某个高度上连接相邻的两条竖线。简单来说，使用阿弥陀签抽签的流程如下：

1. 首先，选择一条竖线，将其最上端（高度最小的一端）作为起点；
2. 然后，从起点开始向下走，每次碰到一条横线的一端，都必须走到其另一端再继续向下走。
3. 这次抽签的结果就是到最下端时所在竖线的编号。

现在，Mio 正在制作一个阿弥陀签。目前签上已经画好了 $n$ 条竖线，还没有任何横线，接下来她将在这个阿弥陀签上修改 $q$ 次横线。每一次她会在某一个位置增加或者减少一条横线。Yui 在每次操作之后，想知道修改后的整个阿弥陀签至少删掉多少条横线，才能使得对于 $\forall 1\leq i\leq n$，以第 $i$ 条竖线的最上端作为起点时，到达最下端时也在第 $i$ 条竖线。你能帮帮她吗？

$1\leq x_1,x_2\leq n\leq 20,1\leq h,q\leq 2\times10^5,1\leq y\leq h,|x_1-x_2|=1$。

题解​

可以将这个过程转化为有 $n$ 个人分别从不同的起点开始走，每条横线视作将相邻的两个人交换，则我们的目标是使最终所有人回到原先的位置。

设每个人最后的位置为 $p_i$，则每次修改可以视为交换两个 $p_i$，最终的目标则转化为令 $\forall 1\leq i\leq n,p_i=i$。

注意到对于所有 $p_i\not=i$，必定存在 $k(k\leq n)$ 个置换环，而每个置换环都需要 $l_i-1$ 次删除操作（即删除其中一次置换对应的横线）来满足最终条件，因此最终的删除边数量就是 $n-k$。

所以我们只需要开一棵线段树维护置换环数量即可。

T3-Q（tamako）​

题面​

在一个 $n\times n$ 的方格纸上的某些格子有障碍，使得剩下的所有格子可以用 $1\times 2$ 的多米诺骨牌不重叠地填满。

将要在方格纸上额外选两个格子放置障碍，使得不再能用骨牌填满所有空格。有多少种选择两个格子的方案。

如果方案数超过 $10^6$，你需要输出 $10^6$ 而非方案数。

$1\leq n,m\leq 1000$。

题解​

假设空格数量为 $x$，对整个方格纸进行黑白间隔染色，那么会有 $\frac{x}{2}$ 个黑空格和 $\frac{x}{2}$ 个白空格。由于删除两个同色格子一定会导致方格纸无法再用多米诺骨牌填满，我们至少有 $\frac{x}{2}(\frac{x}{2}-1)$ 种方案，所以 $x>2000$ 时一定输出 $1000000$。

考虑 $x\leq2000$ 的情况。我们可以把输入中的所有空格当成点建一张二分图，两个点之间连无向边当且仅当它们对应的空格在方格纸上相邻。显然这个图一定存在一个完美匹配，我们先把这个匹配找出来。然后我们考虑数有多少个点对满足删完之后仍然存在完美匹配。

对于一对异侧点 $(u,v)$ 而言，假设它们在原图中分别匹配上了 $u',v'$，删除这对点之后是否仍然存在完美匹配可以这样判断：我们先取消 $u,v$ 在原图中的匹配，然后删掉这两个点，检查 $u'\rightarrow v'$ 是否是一条合法的增广路。具体来说就是，是否存在一条从 $u'$ 到 $v'$ 的路径 $(u',p_1,p_2,p_3,\cdots,p_k,v')$，满足 $(p_1,p_2),(p_3,p_4),\cdots,(p_k−1,p_k)$ 都是原图中的匹配。我们枚举所有的 $u'$，从 $u'$ 开始 bfs 所有可行的 $v'$ 即可。

记答案上限为 $R=10^6$，那么时间复杂度是 $O(R)$ 的。

T4-终（hotel）​

题面​

有一个由 A 和 S 构成的字符串。

这群史莱姆会进行以下四种操作：

1. A 进行分裂：在一个 A 的两端各增加一个 S。即将字符串中的某个 A 替换为 SAS。
2. S 进行分裂：在一个 S 的两端各增加一个 A。即将字符串中的某个 S 替换为 ASA。
3. A 组团逃跑：连续 $a$ 个 A 可以消失。即删除字符串中的连续 个 A。
4. S 组团逃跑：连续 $s$ 个 S 可以消失。即删除字符串中的连续 个 S。

给出两个常数 $a$ 和 $s$，有两个字符串 $R_1$ 和 $R_2$，求是否能将 $R_1$ 经过若干次操作转换为 $R_2$。

$1\leq T\leq100,1\leq a,s\leq10^9,1\leq|R_1|,|R_2|\leq50$。

题解​

记 $\varepsilon$ 表示空串，$R^k$ 表示字符串 $R$ 重复 $k$ 次。

经过足够的手玩，我们可以发现：

$ASA\rightarrow A^aSA^a\rightarrow S$，同理 $SAS\rightarrow A$。

$AA\rightarrow ASAS\rightarrow SS$，同理 $SS\rightarrow AA$。

$SA\rightarrow SSAS\rightarrow AAAS\rightarrow ASSS$，同理 $AS\rightarrow SAAA$。

$A\rightarrow SAS\rightarrow AAASS\rightarrow ASSSS$，同理 $S\rightarrow SAAAA$。

$A\rightarrow ASSSS\rightarrow AAAAA$，同理 $S\rightarrow SSSSS$。

所以，我们可以在一个非空串的任何位置添加 $A^4$ 和 $S^4$。也就是说：

$\varepsilon\rightarrow A^4$，同理，$\varepsilon\rightarrow S^4$。

$\varepsilon\rightarrow A^{4a}\rightarrow A^a$，同理 $\varepsilon\rightarrow S^s$。

就是说，所有操作都是可逆的，那么：

$\varepsilon\leftrightarrow Aa\leftrightarrow A4\leftrightarrow A\gcd (a,4)\leftrightarrow S \gcd (s,4)$。 显然答案只与 $\gcd(a,4)$ 和 $\gcd(s,4)$ 有关，所以下面只考虑 $a|4$ 且 $s|4$ 的情况。不妨设 $a\,|\,s\,|\,4$。

对于任意的 $a$，$s$ 和字符串 $R$，我们考虑以下对字符串 $R$ 的操作：

1. 首先，假如 R 中存在子串 SA，将其替换为 ASSS，直到所有 S 都在 A 右侧为 止。
2. 随后，消去所有连续的 A4 和 S 4。
3. 随后，如果有至少两个 S，将最前面的 SS 替换为 AA。如果有 A4 就消去。

显然，经过这样的操作后，R 一定是以下八个串之一：

$\varepsilon,A,AA,AAA,S,AS,AAS,AAAS$。我们将这些串称作标准串。

当然，$\varepsilon$ 之后并不能进 行任何操作，你可以把它当成 $A^4$，这并不重要。

那么，我们只需要考虑分类讨论一下，在不同的 $a$ 和 $s$ 下，这八个串之间哪些能互相转移即可。

对于 $a=s=4$ 的情况，这八个串之间并不能互相转移。证明也很简单：显然最后得到的串只跟上述第二步操作结束之后的字符串中，$A$ 和 $S$ 的个数 $\mod4$ 的值有关。 题目中的操作 $1,3,4$ 不会改变这两者的值，而操作 $2$ 会使得这两者同时 $+2$。无论如何都不会改变最终的结果。

$a=s=1$ 是平凡的。

$a=1,s>1$ 时，相当于所有的 $A$ 都不存在，那么 $SS$ 也不存在。此时只有 $\varepsilon$ 和 $S$ 两种情况。

$a=2$ 时，$AA$ 和 $SS$ 仍然不存在。有 $\varepsilon,A,S,AS$ 四种情况。由于 $2|a$ 时 $A$ 的数量的奇偶性不会改变，所以这些情况下所有情况之间不能转移是显然的。

所以，我们只需要求出 $R_1$ 和 $R_2$ 对应的标准串，并看它们能否互相转移即可。

时间复杂度 $O(|R1|+|R2|)$。

T1-运动会（sports）​

题面​

要将 $2n$ 个数分为两组，第 $i$ 个数的值为 $a_i$。

有 $m$ 对关系 $(x_i,y_i,b_i)$ 表示当第 $x_i$ 个数和第 $y_i$ 个数被分到同一组时，会产生额外 $b_i$ 的贡献。

求分组之后两组之间总和差的最大值是多少。

$1\leq t\leq5,1\leq n\leq10^5,1\leq m\leq2\times10^5,1\leq x_i,y_i\leq2n,1\leq a_i,b_i\leq 10^9$。

保证对 $\forall 1\leq i<j\leq m$，有 $(x_i,y_i)\not=(x_j,y_j)$ 且 $(x_i,y_i)\not=(y_j,x_j)$。

题解​

$a$ 全相等，此时只需考虑朋友关系的贡献。

考虑如下贪心过程：设与 $i$ 相关的朋友关系的默契度之和为 $s_i$，则选 $s$ 从大到小排序后的前 $n$ 个人分成一组，剩下的分成另一组，答案即为 $\frac{1}{2}\left(\sum_{i=1}^ns_i-\sum_{i=n+1}^{2n}s_i\right)$。

证明：对于朋友关系 $(x,y,b)$，如果 (x,y) 在同一组，则对答案的贡献为 $2b$ 或 $-2b$。否则，贡献为 $0$，即贡献被抵消掉了。\

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

考虑每个人的力量，则将每个 $s_i$ 额外加上 $2s_i$ 然后跑上述贪心即可。

T2-卡牌（card）​

题面​

有 $n$ 张卡牌，每张卡牌背面有一个数字 $a_i$，正面空白。

初始全部正面朝上，可以做以下操作任意次：

• 选择一个 $i$ 满足 $1\leq i\leq m$。
• 翻转从左到右第 $l_i,\cdots,r_i$ 张牌的正反面，代价为 $w_i$。

设最后背面朝上的卡牌写着的数的总和是 $S$，所有操作的代价总和为 $T$，则最终得分为 $S-T$。

求最大可能得分。

$1\leq t\leq5,1\leq n,m\leq2\times10^5,1\leq l_i,r_i\leq n,1\leq a_i,w_i\leq10^9$。

题解​

每个区间不交，对每个区间单独考虑，每个区间的贡献即为 $\max(0,\left(\sum_{i=l_i}^{r_i}a_j\right)-w_i)$。

显然每个 $l_i=1$ 和每个 $r_i=n$ 的区间都分别只会被操作其中一个。枚举翻转了 $l_i=1,r_i=x$ 这个前缀，考虑每个 $r_j=n$ 的区间。如果 $l_j>x$，则此时答案为 $\left(\sum_{k=1}^xa_k\right)+\left(\sum_{k=l_j}^na_k\right)-w_i-w_j$。

如果 $l_j\leq x$，则还需减去相交部分的和。分别维护即可。

考虑做如下转化：初始答案为 $\sum_{i=1}^na_i$。若最后无法翻转 $i$，视作花费 $a_i$ 的代价操作 $i$ 这个点。

因此，初始时先将每个 $(i,i,a_i)$ 加入操作中，即转化为操作若干次使所有卡片都被翻转的最小代价。\

我们考虑 建这样一张图：点集为 $1\sim n+1$，边为所有的 $(l_i,r_i+1,w_i)$ 和 $i,i+1,a_i$，然后求 $1$ 至 $n+1$ 的最短路即可。易证一条 $1$ 至 $n+1$ 的路径对应了一种将所有卡片翻转的操作方案。

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

T3-队形安排（formation）​

题面​

有 $n$ 个同学，第 $i$ 个同学的初始位置为 $x_i$，需要将每个同学的位置向左或向右移动 $d$ 个单位。

需要将同学分为若干排，设一共站成 $k$ 排，第 $i$ 排的同学的编号集合为 $S_i$，则定义凌乱程度为：

$a,b$ 为给定常数，求所有可能的队形的凌乱程度的最小值。

$1\leq t\leq5,1\leq n\leq100,1\leq d\leq30,1\leq a,b\leq10^6,1\leq x_i\leq 100$。

题解​

当 $d \leq9$ 时。我们先将题意转化为要求每个人不动或向右移动 $2d$。

为了方便计算，称第 $i$ 位置被覆盖，为当前位置有人，或者存在两个位置为 $l, r(l < r)$ 的人，使得这两个人被分在同一组，且 $l \leq i \leq r$。设 $v_i$ 表示位置 $i$ 最终是否被覆盖，则答案为 $a\times\sum_iv_i+\min(0,b-a)\times\sum_i(v_i\wedge v_{i-1})$。

我们的限制形如，对于一个位置 $x$ 的人，要求最后位置 $x$ 和 $x+2d$ 中至少有一个被覆盖。