Larunatrecy：信心赛。
赛时
T1 求中位数，想起前两天做过的 [ABC203D] Pond，考虑了二分答案。
看出二分答案后不会做了，罚坐 \(20\) min。
然后发现我傻逼了，选出一个区间翻转，可以通过钦定右端点，找到最优的左端点得到，神仙 Heldivis 就出过一道这样的题。
写完后调了下二分边界过了大样例。大概是 8:20。
T2 看到数据范围只有 \(15\times 2=30\)，感觉是搜索，盲猜一波正解复杂度为 \(O(\dfrac{2^{n+m}}{w})\)。
没什么思路，就硬搜，应该能过个几十分。
写完大样例跑 \(30\) 秒跑不完......
T3 删边考虑倒着加边，发现要求的就是两个点在不在一个边双里面。
会了 \(O(nq)\) 的做法，每次修改暴力求出所有边双。
还有一个无修改的 \(10\) pts，只需最初求一次边双即可。
想到了做过的 network，先缩点，每次加边，将两个点之间路径并查集一下，感觉很对，开始写。
写完后过不了大样例，还发现复杂度仍为 \(O(nq)\)，难绷，扔那了。大概是 10:50。
T4 对于每个测试点都有对应数据范围，感觉能拿不少。
发现 \(m-n\) 很小，感觉很广义串并联，但是我不会，寄。
\(n=2\) 很快会了。
\(O(k^n)\) 做法会了。
\(O(nk)\) 的树会了。
开写。
写完了，每档都和暴力造了组数据拍过了。
交题，估分：\(100+?+30+50\)。
得分：\(100+58+30+35=223\)。
T4 怎么挂了 \(15\)，我擦减法忘记加上 \(P\) 再取模了。改过后有了 \(50\) 分。
题解
一句话。
T1 二分答案，对修改造成的变动做前缀和，钦定右端点，求最优左端点，时间复杂度 \(O(n\log n)\)。
T2 先搜选哪些行，对于剩下的列双向搜索，时间复杂度 \(O(2^{n+\frac{m}{2}})\)。
T3 倒着加边，求最小生成树，然后每次并查集将路径上的点合并，时间复杂度 \(O(\alpha (n)\times n)\)。
T4 不会。
当前订正：\(100+100+100+50=350\)。
标签：15,复杂度,30,50,NOIP2024,端点,100,模拟 From： https://www.cnblogs.com/zhujiangyuan/p/-/NOIP2024_15