为什么会有傻子每次计算都初始化线段树一次 …… st = SegmentTree(n) 改成 st.mdf(1, n + 1, -1) 就 += 25pts 了……
T1
T2
类似上一场的 trick，筛法求质数。对于每个质数求最长的段，使得段内 \(1\) 的个数 \(\ge len/2\)。原始的想法是枚举两个 \(1\) 的位置 \(p_x,p_y(x>y)\)，若 \(p_x-p_y+1\le 2\cdot (x-y+1)\) 就可行。然后在可行的基础上先尽量往左拓展，再尽量往右拓展。
注意到如果 \(p_x\) 这个 \(1\) 与 \(p'_1,p'_2,\dots\) 这些位置的 \(1\) 都可行，必然取距离 \(p_x\) 最远的 \(1\) 是最小的。考虑枚举 \(i\) 为右侧 \(1\) 的位置，找到距离 \(i\) 最远的合法 \(1\) 的位置。
转化一下合法的要求，得到 \(p_x-2x\le p_y-2y+1\)。用一个线段树支持单点加和区间查询最小值，维护 \(p_i-2i\) 即可。用 BIT 也可以。