联合省选 2025 游记
Day 0 (2.28)
试机，按照惯例试了一下 \(2000\) 的 ULL Floyd，8s。
Day 1
进场、发密码、看题。
怎么输入里有测试点编号，这么良心？
看完 T1
感觉可能的中位数应该是一段连续区间，这样两个二分就做完了，至于
check，可以 \(O(n)\) 计算最多有多少个
mid，比 mid 小的数和比 mid
大的数的个数差的最小值，简单判一下。
写写写，发现不对劲，这东西可能会把不存在的数算进答案里。
至少 check 的思路没问题，那就直接离散化把值域搞成 \(O(n)\) 个区间，每个数能不能成为中位数只和它所属的区间有关，check 可以用一个扫描线和一堆树状数组做到总共 \(O(n\log n)\)。
T2 先写了一个 \(O(nq)\) 暴力。
看一看，发现它时间 6s，空间 2G。算一算，发现 \(10^{10}\) 个 bit 比 2G 小。
那就 bitset 处理能否到达。然后怎么做呢？看一眼部分分，AB
性质可以分块做，赶紧写了，拼上 \(O(nq)\)
20pts，有测试点编号就是好写！
T3 根本不会！暴力只会 \(O(Tn!m^2)\)，算下来 \(n \le 10\) 卡满都 \(10^{10}\) 了，不太能过。
然后还是写上去了，发现样例跑得飞快，完全不像 \(10^{10}\)，不管了。
Day 499122178
出考场，听说 T2 是根号重构，太强啦！但我怎么不会？
Day 2
一看 T1 怎么这么熟悉？ABC 原题？线段树维护 \(pos_i-i\)，写几个线段树上二分和区间推平秒了。
第二个样例怎么错得离谱？哦原来还可以往前推的啊。往线段树里加了个区间最小值之后标记下传又错得离谱了，调了不知道多久后过样例了。
完全不拍！相信大样例！开 T2！
性质 A 纯暴力，先写了个 \(O(4^m)\) 枚举边的存活状态，然后爆改 prim 再乘个 \(O(n^2)\)，一看怎么样例二第一组数据没过？\(1280\rightarrow 1256\)，重写了两遍还是不对，合理怀疑 prim 没正确性，直接枚举外向生成树的 \(n-1\) 条边过了。
性质 B 生成树唯一，容斥枚举哪些点能够到达其他所有点，样例能过。
试图将性质 A 与性质 B 进行对拍，发现每棵树拍出来的答案都一样，猜测树的形态没有影响，不过容斥都写完了。
开 T3，暴搜启动！
Day 3
还原了一下自己的 D1T1 和 D2T1，过洛谷民间数据了。
Day 6
\(100+24+8+100+24+8=264\)。感觉还行。
D1T2 \(O(nq)\) 有 88pts？