2024 四川省选 游记
day -?
得知是联合省选，好耶，不用背计算几何了。
day -1
教练组织了省选动员会，还请了吃肯德基（甚至疯狂星期四），晚自习中间就放了。
其中有一个学长寄语环节，印象最深的是 zjk 说省选前一天不要背板子，最好就不要学习，可以打一天游戏。
day 0
所以我打了一天游戏（某六字游戏版本更新，把主线推了，还搞了点其他的），感觉省选前一天不适合抽卡啊。
下午吃了晚饭就提前去考场附近酒店了。
day 1
带了六条（小块装）士力架，这次绝对不会低血糖了，准备每隔 40 分钟吃一根（结果最后只吃了四根）。
T1 很简单，仔细推以下发现若中位数出现了 $p$ 次，那么比它大的数个数和比他小的数个数之差要小于 $p$（或者等于 $p$，就是大的比小的多时，需要特殊处理），那么显然 $p$ 越大越好。直接对值域离散化，显然离散化后的每个区间要么都能要么都不能，从小往大扫时可以简单维护有多少个区间包含了当前的数，以及多少个一定更小/更大（注意这个个数的取值也是区间），然后简单算一算就行了。大概九点十分就写完了。
T2 一眼没思路，于是先去看 T3 了。
T3 发现特殊性质 $C$（森林）很好构造，一开始想的是类似于 dfs 序的东西。后面发现可以先搞子树最小值然后往上跳，并且树根不一定要在子树最前面。对于多个连通块就按最小值排序，然后每次更新答案时假如下一个连通块插在这里更优就插进去，显然连通块之间要么包含要么不交。
然后把 T2 的 $O((n+m)q)$ 暴力写了，后面尝试骗分发现过不了大样例。
估分 $100+20+52=172$，感觉是高档大众分啊。
day 2
T1 想了一会儿，对于性质 B 可以 Hall 定理。正解可以将所有极长下降段翻转变成性质 C，于是考虑性质 C。首先一个转化是点 $i$ 的 $a,b$ 都减去 $i-1$ 转化成可以重叠。然后可以对每个箱子设置 $n$ 个时间节点转化成性质 B，就能 $O(n^2)$ 了，不难发现只需要在 $t$ 的递增子序列设置时间结点，并且用时是每个点减去上一个点。可以在单调队列上打 tag 维护。
T2 看了一眼感觉很可做，于是把 T3 的 $8$ 分暴力打了开始冲 T2。
首先性质 B 就是说树的形态是确定的，有简单容斥：在树上换根，每个点计算在当前根合法，但是上一个根（父亲）不合法的方案，强制钦定指向父亲的边是有向边即可，不难发现除去树根的合法概率是 $2^{-(n-1)}$ 以外，其它都是 $2^{-n}$，可以直接算。
感觉正解就是把最小生成树求出来，然后每次计算在且仅在包含当前非树边的树形上合法的方案，但是没调出来，可能假了。
总分 $100+24+8=132$。省选总计 $268+172+132$，感觉没挂就有希望啊。
这两天吃了八条士力架，要长肉了。
接下来一周其他同学要去川大网安班，于是我要选择是跟着高一的补课还是自行学习（这不就是放假）还是单独找老师。我倾向于放一周假吧。
最后结果是折中一下，准了两天假。