• Solved 3 out of 11 problems
• Rank 255 / 1033 in official records
• Solved 4 out of 11 afterwards

(√ for solved, O for upsolved, - for tried but not solved)

相当于每一条边在一段时间内，将所有边加在线段树上，在线段树维护并查集以及记录并查集上的操作，返回上一层时撤销这些操作即可 场上想了LCT的做法，LCT上连边，如果已经是一棵树结构，就删掉树上最早要删除的边再加入该边，这样可以维护树结构，顺便统计连通块个数，然而码力太弱~

$\Theta(n^2)$ 本地跑 14s，估计过不了，考虑打表。

打表输出长度 1.3 MB，远超限制，考虑压缩。

二分查询得到牛客代码限制约为 100KB。

将答案数列差分，发现奇偶项规律迥异，按奇偶项做二阶差分。

观察二阶差分序列，发现数字均很小（绝对值 100 以内）。

省去换行，二阶差分序列表长约 300KB。

依旧远超限制。现在考虑压缩。

我们按照这样的方法进行压缩：

for(int i = 36000; i <= N; ++i) {
	if(diffff[i] >= -26 && diffff[i] <= -1) fprintf(out, "%c", 'a' - 1 - diffff[i]);
	else if(diffff[i] >= 10 && diffff[i] <= 35) fprintf(out, "%c", 'A' + diffff[i] - 10);
	else if(diffff[i] >= 0 && diffff[i] <= 9) fprintf(out, "%c", 35 + diffff[i]);
	else fprintf(out, "%lld,", diffff[i]);
}

这样可以将大部分数字压缩到一个字符。

这样压缩之后表长达到了 140K。

这样我们直接把前三分之一砍掉即可。

前 36000 暴力，后面直接解码即可。

直接用一个 unsigned long long can[256][256][4] 保存 $(i, j, k)$ 能否凑成一个 $\mathsf{set}$。

这个直接 $\Theta(n^3)$ 预处理即可。

后面查找的时候按照这样的算法查找即可：

$id := \left[encode(x)\;\;\mathtt{for}\;\;x\;\;\mathtt{in}\;\;input\right]$
$has := \varnothing$
$\mathtt{for}\;\;i\;\;\mathtt{from}\;\;1\;\;\mathtt{to}\;\;n$
$\qquad\mathtt{for}\;\;j\;\;\mathtt{from}\;\;i+1\;\;\mathtt{to}\;\;n$
$\qquad\qquad\mathtt{if}\;\;can[id[i]][id[j]]\cap card\neq\varnothing$
$\qquad\qquad\qquad\mathtt{output}(k, i, j)\qquad\qquad\qquad//\;\;id[k]\in can[id[i]][id[j]]\cap card$
$\qquad\qquad\qquad\mathtt{return}$
$\qquad\qquad\mathtt{end\;if}$
$\qquad\mathtt{end\;for}$
$\qquad has = has\cup\{id[i]\}$
$\mathtt{end\;for}$

前缀和+单调递减序列 卡在爆long long上

ptw:

• 可惜这个一血 G 了
• 今天这个 E 应该早点写，应该就过了。或者应该更早考虑打表。
• 再再再次提醒我们注意模板的鲁棒性 （I）
• 建议引入 double-check 机制，一个做法写之前由第二个人验证（除极水的水题）
• 小 心 数 据 范 围（K）
• 小 心 Python 大 常 数（K）
• 罚时还是很贵的，三发罚时等于晚过一小时
• 自强不息，稳中求胜，一起加油

Withinlover:

• E 的暴力其实好好写就过了。
• I 网络流是可过的，貌似是非递归的ISAP。（还不是你手上没板子了）
• 不要过度相信本地测试结果，本地TLE牛客AC（E）

Gary：

• K数据范围没仔细算，爆longlong了
• K最开始写的线段树，虽然也能过，但是麻烦点而且线段树也写错了两处
• A码力太弱了，LCT根本写不出来，看着自己的板子都手生，并查集+线段树也没想出来
• H的串题最先看到，当时觉得要长度拓宽几倍在做，但是不太会证也没想到例子，尤其没人做就没细想了，感觉当时猜波结论枚举一下拓宽的倍数大概率就过了？