不会tarjan不会广义串并联图……
赛时
T1 看上去很可做。
看到中位数首先想到二分。在二分的背景下，问题转化为求当前最多能使多少个元素大于等于某个定值。
我们不妨先让所有的元素都选择 \(a\) 值，然后相当于要选择一段连续的 \(b\) 替换一些 \(a\)，要求最后总和最大。所以可以新设一个代价数组 \(v\)，并令：
\[v_i= \left\{ \begin{array}{lc} 0 &a_i\le x\operatorname{and} b_i\le x\\ 0 &a_i\ge x \operatorname{and} b_i\ge x\\ 1 &a_i\le x \operatorname{and} b_i\ge x\\ -1 &a_i\ge x \operatorname{and} b_i\le x\\ \end{array} \right. \]然后跑一个最大连续子段和就可以了。
T2 第一眼看上去以为 \(n.m\le 10^3\) 以为不可做。然后问了旁边的人他说 \(n,m\le 15\)。
因为 \(2^{15+15}=1,073,741,824>>300,000,000\)，所以我猜正解是类似状压什么的东西。旁边的人告诉我没有部分分，所以我只能去推正解了。
但是推着推着这道题变成了子序列和为定值的存在性问题，这个显然没有非指数级做法，不会了，我又问了一遍旁边的人，他说没有部分分。
大概 9:30 的时候题目终于下发部分分了，当我看见 T2 的部分分表格时，我直接红了啊，然后去把旁边的人
标签：le,06,NOIP,T2,T3,定值,ge,2024.11,operatorname From： https://www.cnblogs.com/Lydic/p/18530290