【题解】四月训练日记

CF1709E. XOR Tree

*2400 Code

注意到操作时改成的正整数没有大小限制，不妨改成 \(2^{k}\)（\(k\) 充分大），这样经过该点的路径的权值绝对不可能为 \(0\)。

指定一个根节点（不妨为 \(1\)），假定路径 \(x\leftrightarrow y\) 是坏的（也就是异或和为 \(0\)），那么容易说明修改 \(z=\text{LCA}(x,y)\) 是最优的。

考虑这么一个过程：从根节点开始向下 dfs，回溯时判断当前节点 \(z\) 是否能作为一条坏的路径的 \(\text{LCA}\)。若能，答案 \(+1\)；否则不做修改。

问题转换为如何进行这个判定。设 \(f_x\) 代表从根节点开始的前缀异或和，即路径 \(1\leftrightarrow x\) 的权值。那么，路径 \(x\leftrightarrow y\) 是坏的等价于 \(f_x\oplus f_y\oplus a_{\text{LCA}(x,y)}=0\)。

对每一个顶点 \(z\) 维护一个 std::set，存储以 \(z\) 为根的子树里的节点的 \(f\) 集合。这样当我们合并 \(z\) 的一个儿子（设为 \(p\)）的信息时，只用遍历 \(z,p\) 中较小的一个集合，在另一个集合里查有没有符合要求的元素。

若当前节点需要修改，就清空当前节点的 std::set，否则合并儿子的信息。

这是一个启发式合并的过程，时间复杂度 \(O(n\log^2 n)\)。

CF1981D. Turtle and Multiplication

*2400 Code

当所有 \(a_i\) 都是质数时，\(a_i\cdot a_{i+1}\not=a_j\cdot a_{j+1}\) 的充要条件是无序对 \((a_i,a_{i+1})\) 和无序对 \((a_j,a_{j+1})\) 不同。当 \(a_i\) 不都是质数时，充要条件会退化成必要条件，更劣，故优先思考 \(a_i\) 都是质数时是否能构造。

将无序对 \((a_i,a_{i+1})\) 看作一条无向边，那么问题转换为找到一个最小的 \(m\)，满足 \(m\) 个点构成的完全图存在一条覆盖 \(n-1\) 条边（每条边至多被覆盖一次）的路径。

当 \(m\) 为奇数时，图上所有顶点的度数都是偶数，存在一条长 \(\frac{m(m-1)}{2}+m\) 的欧拉回路（\(+m\) 是因为每个点都有自环，算一条边）。

当 \(m\) 为偶数时，图上所有顶点的度数都是奇数。无向图存在欧拉路径的条件是有 \(0/2\) 个点是奇度点，其它为偶度点。考虑删边，只留下两个奇度点，一种留下最多边的方式是删 \((2,3),(4,5),(6,7),\ldots,(m-2,m-1)\)。剩余边数是 \(\frac{m(m-1)}{2}+m-\frac{m}{2}+1\)。

二分出最小满足条件的 \(m\)，构造出对应的 \(m\) 个点的完全图（若 \(m\) 是偶数还要按上述规则删边），跑出一条欧拉路径。若路径上第 \(i\) 个点是 \(x\)，对应到序列上 \(a_i\) 就是第 \(x\) 小的质数。

当 \(m=1500\) 时，构造出的图有 \(1125001>10^6\) 条边，而第 \(1500\) 小的质数是 \(12553<3\cdot 10^5\)，满足条件。

时间复杂度 \(O(n)\)。

CF1981E. Turtle and Intersected Segments

*2600 Code

对于三条两两相交的线段 \([l_1,r_1,a_1],[l_2,r_2,a_2],[l_3,r_3,a_3]\)，设 \(a_1\le a_2\le a_3\)，那么可以仅保留边 \(1\leftrightarrow 2,2\leftrightarrow 3\)。（因为 \(|a_1-a_3|=|a_1-a_2|+|a_2-a_3|\)，选第 \(3\) 条边肯定不优）

不难发现对于每一条线段 \([l_i,r_i,a_i]\)，我们只用保留两条边：

1. 与该线段相交的线段中，权值（设为 \(a_j\)）最大且满足 \(a_j\le a_i\) 的边。
2. 与该线段相交的线段中，权值（设为 \(a_j\)）最小且满足 \(a_j\ge a_i\) 的边。

扫描线，维护一个 std::set，扫描到一条线段的左端点时就把线段的权值加进去，扫描到右端点时就把对应的权值删掉。保留的边相当于线段在容器中的前驱和后继。

最终处理出的侯选边有 \(O(n)\) 条，跑最小生成树即可。

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

abc399e. Replace

Code

连边 \(S_i\to T_i\)。

首先每个点至多有一条出边，否则 -1。\(26\) 个点都有入度，也为 -1。

否则答案的下界是图上的边数（不含自环）。

对于一个环，分两种情况：

• 环上存在入度为 \(2\) 的点。说明存在一条边 \(x\to y\) 满足 \(y\) 在环上而 \(x\) 不在。设 \(y\) 的另一条入边是 \(z\to y\)，此时可以花 \(1\) 的代价将 \(z\) 改为 \(x\)，破环成链，且不花费额外次数（即用 \(1\) 次操作断了一条边，与预设 "答案是图上的边数" 相符）。
• 环上所有点入度为 \(1\)。此时只能将环上任意一点 \(x\) 替换为图中的一个孤点，最后再改回来，花费了 \(1\) 点额外次数。

于是答案是图上的边数 \(+\) 第二类环的数量。

时间复杂度 \(O(n)\)。

CF1139E. Maximize Mex

*2400 Code

考虑没有人离开社团的情况。此时二分答案，设二分的 \(\text{mex}\) 是 \(mid\)，那么只需要保留潜力值 \(<mid\) 的学生。

建出一个二分图，左部图是 \(m\) 个社团，右部图对应 \(0\sim mid - 1\) 这 \(mid\) 个潜力值。对于一个学生，我们可以连出一条边，最终只要看最大匹配是否为 \(mid\)。

若有学生离开了，相当于删掉一条边，这是不好处理的。但我们想到 Dinic 可以动态加边，于是离线下来倒着做。

但每加一条边就要重新二分枚举 \(\text{mex}\) 就太低效了。注意到加边的时候 \(\text{mex}\) 只增不减，换句话匹配数只增不减。我们可以从 \(1\) 开始枚举 \(\text{mex}\)，每次将 \(p[i]=\text{mex}-1\) 的学生加到图上，若匹配数恰好为 \(\text{mex}\)，就 \(\text{mex}\leftarrow \text{mex}+1\)，重复这个流程。

此时，一个学生 \(i\) 加入社团，分两种情况处理：

1. 加入时枚举的 \(\text{mex}\ge p[i]\)。直接加边即可。
2. 加入时枚举的 \(\text{mex}<p[i]\)。将学生 \(i\) 加进备选名单里，等 \(\text{mex}\) 枚举到的时候再加边。

时间复杂度 \(O(\text{MaxFlow}(m, n))\)。

CF1746F. Kazaee

*2800 Code

先将所有数（包括原有的 \(a_i\) 与每次修改后的 \(x\)）进行离散化。

一个暴力的做法是对每个数都维护一个树状数组，这样整道题能在 \(O(n^2+qn\log n)\) 内解决。

面临的困难无非只有一点：对于一个区间，时间复杂度不允许我们 check 区间里每一个数的出现次数。

一个关键点是，一段区间中，如果所有数字的出现次数都是 \(k\) 的倍数，其出现次数之和也一定为 \(k\) 的倍数，但这是必要不充分条件。

随机化，在值域内随机选出 \(B\) 个子集，对于一个询问，逐一 check 每一个子集，看每个子集里的数的出现次数之和是否为 \(k\) 的倍数。

而单点修改时，遍历这 \(B\) 个子集，若当前子集包含修改前/修改后的数，就相应在树状数组上修改。

为了保证正确性，每个子集按照以下方式随机：

• \(\forall i\in [1,W]\)，\(i\) 有 \(\dfrac{1}{2}\) 的概率选进子集。其中 \(W\) 为离散化后的值域。

错误率分析：最坏情况下，判错当且仅当存在一对数 \(x,y\)，满足 \(k\mid cnt_x+cnt_y\) 且 \(k\not\mid cnt_x\)，\(k\not\mid cnt_y\)。四种情况：选 \(x\) 没选 \(y\)，选 \(y\) 没选 \(x\)，没选 \(x\) 没选 \(y\)，选 \(x\) 选 \(y\)，它们在概率上各占 \(\dfrac{1}{4}\)，其中仅第三第四种会犯错，占 \(\dfrac{1}{2}\)。取 \(B=30\)，错误率就是 \(\dfrac{1}{2^{30}}\)，足够低了。

时间复杂度 \(O(nB\log n+qB\log n)\)。

abc401f. Add One Edge 3

Code

记 \(G\) 为树 \(1\)，\(H\) 为树 \(2\)。

记 \(d_1,A_1,A_2\) 为 \(G\) 的直径及其两个端点，\(d_2,B_1,B_2\) 为 \(H\) 的直径及其两个端点。

记 \(f_x/g_x\) 为以 \(G/H\) 中的点 \(x\) 为端点的最长的路径的长度，显然有 \(f_x=\max(dis(A_1,x),dis(A_2,x))\)，\(g_x=\max(dis(B_1,x),dis(B_2,x))\)。

对于一条连接了 \(G\) 中点 \(i\) 和 \(H\) 中点 \(j\) 的边，新图直径变为 \(\max(\max(d_1,d_2),f_i+g_j+1)\)。

将 \(f_x,g_x\) 升序排序，枚举 \(f_i\)，就能二分或双指针求出有多少个满足 \(f_i+g_j+1>\max(d_1,d_2)\) 的 \(g_j\)，贡献就是一段 \(g\) 的后缀和。

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

CF1749E. Cactus Wall

*2400 Code

转化：相当于寻找一条 # 构成的路径，这条路径从第一列开始，到最后一列结束，且每次只能走对角线的四个方向。

先把图上所有可以放置 # 的位置找出来（包括原来就有的 #），称作关键点。

建图，源点 \(S\) 向第一列的关键点连边，每个关键点向四个对角线方向的关键点连边，最后一列的关键点向汇点 \(T\) 连边。

一条边 \((u,v)\) 的边权取决于 \(v\)，若 \(v\) 为汇点或原来就有 # 的位置，边权就是 \(0\)；否则边权是 \(1\)（代表需要在此处新放置一个 #）。

跑最短路即可，记一下路径方案也就有了。

时间复杂度：\(O(nm\log nm)\)。若使用 01bfs 还可以省去 \(\log\)。

CF2096E. Wonderful Teddy Bears

*2400 Code

将 B 看作 \(0\)，P 看作 \(1\)。

对一个长为 \(3\) 的子串操作，分为以下四种情况。

1. \(010\to 001\)；
2. \(100\to 001\)；
3. \(101\to 011\)；
4. \(110\to 011\)。

我们将操作 \(1,3\) 归为一类，称为 \(A\)；操作 \(2,4\) 归为一类，称为 \(B\)。

之所以这么分，是因为观察到如下性质：

• \(A\) 类操作能将逆序对数 \(-1\)，而 \(B\) 类操作能将逆序对数 \(-2\)。
• \(A\) 类操作能改变一个 \(0\) 的下标奇偶性，而 \(B\) 类操作不能。

令 \(c_0,c_1\) 分别表示序列中 \(0/1\) 的个数，\(rev\) 表示逆序对数，\(tot\) 表示下标为偶数的 \(0\) 的数量。

想象一个排好序的的 \(01\) 串：有 \(\left\lfloor\frac{c_0}{2}\right\rfloor\) 个 \(0\) 的下标为偶数（1-index）。

那么可以先用 \(\left|tot-\left\lfloor\frac{c_0}{2}\right\rfloor\right|\) 次 \(A\) 类操作调整奇偶性，再用 \(B\) 类操作减少逆序对数。

可以预见的是调整奇偶性后逆序对数一定是偶数，故最后不必再用 \(A\) 类操作减少逆序对数。

答案是 \(\left|tot-\left\lfloor\frac{c_0}{2}\right\rfloor\right| + \dfrac{(rev-\left|tot-\left\lfloor\frac{c_0}{2}\right\rfloor\right|)}{2}=\dfrac{rev+\left|tot-\left\lfloor\frac{c_0}{2}\right\rfloor\right|}{2}\)。

时间复杂度 \(O(n)\)。

CF1977D. XORificator

*2300 Code

注意到当我们钦定某个点 \((x,y)\) 为那一列（即第 \(y\) 列）唯一的 \(1\) 时，每一行是否需要翻转就被唯一确定了（或者说整个矩阵都被确定了）。

考虑枚举每个点作为那一列唯一的 \(1\)，问题转换为如何快速知道该状态下有多少列仅有一个 \(1\)。

反向思考，钦定一个点作为那一列唯一的 \(1\) 时，把此时的 XORificator 记录下来（题解里用的 Zobrist hashing，implement 非常精悍短小），答案就是出现次数最多的 XORificator 的出现次数。

时间复杂度 \(O(nm\log nm)\)。

CF1622D. Shuffle

*2000 Code

要求本质不同看起来十分困难，但有个 trick 是你枚举所有区间，然后钦定这个区间的左端点和右端点都一定发生了变化，这样计数不重不漏，考虑起来就轻松很多。

先特判掉整个串的 \(1\) 都不足 \(k\) 个的情况。

首先，枚举的区间需要满足 "区间内 \(1\) 的个数 \(\le k\)"，为什么是小于等于？因为我们实际操作的区间恰有 \(k\) 个 \(1\)，但相对原来发生变化的区间可以是一个子集。

接着，区间两侧的数必须发生变化，非两侧的数任意排列，贡献就是一个组合数。

时间复杂度 \(O(n^2)\)。

CF1622E. Math Test

*2200 Code

trick：拆绝对值。\(|x_i-r_i|\) 可以拆成 \(x_i-r_i\) 和 \(r_i-x_i\) 两种，时间复杂度允许我们 \(O(2^n)\) 枚举每一种拆法。

贪心，我们可以统计出每道题被多少个人解决了（如果那个人是 \(x_i-r_i\)，\(r_i\) 的贡献是负的，就当作 \(-1\) 个人；反之 \(r_i-x_i\) 就看作 \(+1\) 个人），给被更多人解决的题赋值一个大的 \(p_j\)。

因为绝对值被拆掉了，\(\{p\}\) 确定之后最终答案也确定了，取 \(\max\) 即可。

时间复杂度 \(O(nm2^n)\)。

CF1354E. Graph Coloring

*2100 Code

注意到 \(1,3\) 作为一组，\(2\) 作为一组，组间连边组内不连边，构成二分图。

故 YES 的必要条件是给定的图的每一个连通分量均是二分图。

接着考虑数量限制：我们只用关心 \(2\) 的数量能否得到满足，\(2\) 满足了 \(1,3\) 自然满足。

设给定的图有 \(m\) 个连通分量，第 \(i\) 个连通分量有 \(L_i\) 个左部点，\(R_i\) 个右部点。

现在我们要对每个连通分量选出左部或者右部填 \(2\)，另一部 \(1,3\) 任意填。

抽象出来相当于有 \(m\) 个集合，每个集合可以选 \(L_i\) 或 \(R_i\) 中的恰好一个，判断是否存在一种选择方案使得选出的 \(m\) 个数的总和是 \(n_2\)。

令 \(dp[i][j]\) 表示前 \(i\) 个集合选出的数是否能凑成 \(j\)，还需另开一个数组记录方案。

时间复杂度 \(O(n^2)\)。

CF1354F. Summoning Minions

*2500 Code1 Code2

对于一个将来需要销毁的仆从，将它升级没有意义，故选择召唤之后马上销毁。

于是，最佳策略应该形如：

1. 从 \(n\) 个仆从中选择 \(k-1\) 个召唤。
2. 从剩下的 \(n-k+1\) 仆从中选择 \(n-k\) 个召唤后立即销毁。
3. 召唤剩下的那 \(1\) 个仆从。

在第一步中，假设仆从 \(i\) 在第 \(j\) 个被召唤，则贡献是 \(a_i+b_i (j-1)\)。

在第二步中，仆从 \(i\) 被召唤的贡献固定为 \(b_i(k-1)\)。

在第三步中，仆从 \(i\) 被召唤的贡献为 \(a_i+b_i(k-1)\)，可以和第一步的贡献合并。

建立二分图，左部点代表仆从，右部点代表被召唤时的顺序，问题转化为一个满二分图的最大权匹配，跑最大费用最大流即可。

时间复杂度 \(O(T\cdot \text{MinCostMaxFlow}(n, n^2))\)。

另一种方法是注意到在第一步中，选定的 \(k\) 个仆从（与第三步合并了，所以是 \(k\) 个）一定按 \(b_i\) 升序召唤。

令 \(dp[i][j]\) 表示前 \(i\) 个仆从选出 \(j\) 个放在第一步的最大答案。 \[ dp[i][j] = \max(dp[i-1][j]+b_i(k-1),dp[i-1][j-1]+a_i+b_i(j-1)) \] 回溯以记录方案。

时间复杂度 \(O(Tnk)\)。

CF555E. Case of Computer Network

*2800 Code

位于同一个边双连通分量中的点总是可以互相到达。（指总是存在一种可行的定向方案）

边双缩点，对于一组 \((s_i, d_i)\)，若 \(s_i\) 和 \(d_i\) 在同一个边双内，则可以忽略。

否则，\(s_i\to d_i\) 上的边的方向就被固定了。（此处的 \(s_i,d_i\) 指的都是其所在边双的编号，下同）

固定一个根，对每个点维护两个标记 \(up\) 和 \(down\) 分别表示上下两个方向。

对于一组询问，\(s_i\to \text{LCA}(s_i,d_i)\) 上的点的 \(up\) 标记 \(+1\)，\(\text{LCA}(s_i,d_i)\to d_i\) 上的点的 \(down\) 标记 \(+1\)，这个操作可以用树上差分简单实现。

最后，若有一个点同时有非零的 \(up\) 和 \(down\) 标记，就是 No。

此题有若干细节：

• 图不连通，缩点后是一个森林，处理 LCA 时要小心。
• 若询问中的两个点不在一个连通分量内，直接就是 No。
• 有重边。若两个点之间有重边，则它们属于同一个边双。

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

abc399f. Range Power Sum

Code

令 \(s_i=\sum\limits_{j=1}^{i} s_j\)，则： \[ \begin{align} \sum_{1\le l\le r\le N}\left(\sum_{l\le i\le r}a_i\right)^k &= \sum_{l=1}^{n}\sum_{r=l}^{n}\left(s_r-s_{l-1}\right)^k \\ &= \sum_{l=1}^{n}\sum_{r=l}^{n}\sum_{i=0}^{k}(-1)^{k-i}\binom{k}{i}s_r^{i}s_{l-1}^{k-i} \\ &= \sum_{i=0}^{k}(-1)^{k-i}\binom{k}{i}\sum_{l=1}^{n}\sum_{r=l}^{n}s_r^{i}s_{l-1}^{k-i} \\ &= \sum_{i=0}^{k}(-1)^{k-i}\binom{k}{i}\sum_{r=1}^{n}\sum_{l=1}^{r}s_r^{i}s_{l-1}^{k-i} \\ &= \sum_{i=0}^{k}(-1)^{k-i}\binom{k}{i}\sum_{r=1}^{n}s_r^{i}\sum_{l=1}^{r}s_{l-1}^{k-i} \\ \end{align} \] 枚举 \(i,r\)，而 \(\sum\limits_{l=1}^{r}s_{l-1}^{k-i}\) 可以预处理前缀和 \(O(1)\) 求。

时间复杂度 \(O(nk)\)。

CF2104G. Modulo 3

Code

每个点至多有一条出边，意味着这个图由若干环和链组成。并且，这种特殊的结构使得同一个环上的点的颜色一定相同，而链上的每个点都能取 \(k\) 种颜色中的任意一种。

具体的，设图中环的数量为 \(c\)，第 \(i\) 个环的长度为 \(l_i\)，对于一个给定的 \(k\)，答案是： \[ k^c\cdot k^{(n-\sum\limits_{i=1}^{c}l_i)}=k^{n+c-\sum\limits_{i=1}^{c}l_i} \] 根据欧拉定理，对于任意互质的 \(a,p\)，有 \(a^{\varphi(p)}\equiv 1\pmod{p}\)，进一步对于任意 \(x\) 有 \(a^x\equiv a^{x\bmod \varphi(p)}\pmod {p}\)。于是： \[ k^{n+c-\sum\limits_{i=1}^{c}l_i}\equiv k^{(n+c-\sum\limits_{i=1}^{c}l_i)\bmod 2}=k^{n\bmod 2+c\bmod 2+\sum\limits_{i=1}^{c}l_i\bmod 2}\pmod{3} \] 注：当 \(k\) 和 \(3\) 不互质时，\(k\) 为 \(3\) 的倍数，答案一定是 \(0\)，可以特判掉。

令 \(M = c\bmod 2+\sum\limits_{i=1}^{c}l_i\bmod 2\)，注意到奇环对 \(M\) 是没有任何贡献的，于是 \(M\) 等价于 "偶环个数\(\bmod 2\)"。

有向图偶环是不好维护的，但这题中只要有偶环就一定连通（指存在一个点，环上的所有点都能从该点到达），故实际上我们可以当作无向图偶环来处理，用一个并查集维护。

因为是动态图，所以还要套一个线段树分治。

时间复杂度 \(O(q\log^2 q)\)。

qoj7653. Balloon Darts

Code

枚举一条直线都会用掉 \(O(n^2)\) 的复杂度，启发我们并不需要枚举所有 \(n\) 个点。

依据抽屉原理，\(k\) 条直线（这里 \(k=3\)）上任取 \(k+1\) 个点，必然有两点满足确定的直线是 \(k\) 条中的一条。

或者反证法，如果选出的 \(k+1\) 个点不存在两点组成目标直线中的一条，则这 \(k+1\) 个点需要 \(k+1\) 条直线才能消除。

于是我们的做法是：

• 对于当前 \(k\)，从前 \(k+1\) 个点里选两点构成一条直线，遍历所有剩下的点，消除在这条直线上的点。
• 将问题递归到 \(k-1\)。边界条件是点数 \(\le 2k\) 返回 true。

时间复杂度 \(O(n)\)。

CF1437E. Make It Increasing

*2200 Code

trick：令 \(a_i\leftarrow a_i-i\)，则最长上升子序列 \(\to\) 最长不下降子序列。

令 \(a_0=-\infty,a_{n+1}=+\infty\) 并将 \(0\) 和 \(n+1\) 加进 \(\{b\}\) 中，则整个数列被划分为若干可以修改的段。

每个段分开考虑，设当前段为 \([l,r]\)，则需要修改的位置数量是 \((r-l+1)-cnt\)，其中 \(cnt\) 是 \([l,r]\) 中值在 \([a_{l-1},a_{r+1}]\) 里的最长不下降子序列长度。

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

CF1440D. Graph Subset Problem

*2600 Code

将一个 \(k\) 个点的 clique 称作 \(k\)-clique，满足题意的子集称作 good-subset。

注意到一个点如果度数 \(<k-1\)，那么它既不可能组成 \(k\)-clique，也不可能组成 good-subset，我们可以把这个点删掉。

当一个点被删掉时，它的邻居的度数就会 \(-1\)，进而可能出现新的度数 \(<k-1\) 的点，所以我们是按照类似拓扑序的方式删点（当一个点度数 \(<k-1\) 时被加进队列）。

最终，图上所有点的度数都至少是 \(k-1\)（如果至少是 \(k\)，那么所有点一定组成 good-subset，直接输出）。此时，要满足 \(\frac{n(k-1)}{2}\le m\)，剩余点数 \(n\) 满足 \(n\le \frac{2m}{k-1}\)。

我们可以枚举每个度数为 \(k-1\) 的点作为 \(k\)-clique 的一部分，标记它和它的 \(k-1\) 个邻居，\(O(k^2\log k)\) 验证这个 \(k\)-clique 是否合法。（\(\log\) 是在邻接表中二分查找的复杂度，如果使用 unordered_map 或其它哈希方法则可以省去）

最多验证 \(n\) 个点，故复杂度 \(\le \frac{2m}{k-1}\cdot k^2\log k\approx O(mk\log k)\)。又由 \(\frac{k(k-1)}{2}\le m\)，故 \(k\le \sqrt{2m}\)，也就是 \(O(m\sqrt{m}\log m)\)，可以接受。

若找到了一个 \(k\)-clique，就可以退出。否则，将这个点删掉。最终如果没有删光，仍旧得到一个点度数至少为 \(k\) 的图，一定是 good-subset。

注意到找 \(k\)-clique 的过程和一开始一样需要删点，删点后要跑拓扑，那么不如将一个点加进队列条件调整为度数 \(<k\)，一遍拓扑一边验证当前点是否可能组成 \(k\)-clique。

写代码之前务必想清楚实现的细节，本题容易枚举不当导致复杂度退化。

时间复杂度 \(O(m\sqrt{m}\log m)\)。

CF1440E. Greedy Shopping

*2600 Code

操作一不会破坏序列的单调性，\(\{a\}\) 始终单调递减。

对于操作 1 x y，我们可以二分出第一个 \(a_i< y\) 的下标 \(i\)，转换为将区间 \([i,x]\) 修改为 \(y\)。

对于操作 2 x y，一个直观的想法二分出 \(x\) 右侧第一个满足 \(\sum\limits_{i=x}^{p} a_i>y\) 的 \(p\)，然后贡献就是区间 \([x,p-1]\) 的长度。但注意到并不是只有这一段区间有贡献，实际可以是 \(x\) 右侧的若干段区间。

可以证明，区间个数至多是 \(O(\log y)\) 级别的。我们用 \(1\) 表示选中的区间，\(0\) 表示未选中的区间，那么 \(x\) 右侧形如 \(101010\ldots\)，左数第一个 \(0\) 的 \(\sum a_i\)（设为 \(A\)）比左数第一个 \(1\) 的 \(\sum a_i\)（设为 \(B\)）要小，那么这一组 \(10\) 存在就说明 \(y-A < B < A\to y<2A\to A>\frac{y}{2}\)，即每次 \(y\) 都至少消费掉自身的一半，得证。

回到证明之前，当找到 \(p\) 后，累加贡献，\(y\) 减去区间 \([x,p - 1]\) 的和，就可以继续在 \(p\) 右侧二分出第一个 \(a_j\le y\) 的 \(j\)，再在 \(j\) 右侧二分出第一个满足 \(\sum\limits_{i=j}^{p_2}a_i> y\) 的 \(p_2\)，得到区间 \([j,p_2-1]\)，以此类推...

操作一用线段树区间赋值，操作二在线段树上二分，可以少一个 \(\log\)，共二分 \(O(\log y)\) 次。

时间复杂度 \(O((n+q)\log n +q\log n\log w)\)，\(w\) 是值域。