251221 模拟赛
T1
给定 \(2n\) 个三维向量 \(a_{1\sim n}\) 和 \(b_{1\sim n}\)，你需要匹配 \(a,b\)，使得 \(\forall i\ne j,~|a_i-a_j|\le |(a_i+b_i)-(a_j+b_j)|\)。构造方案。
\(n\le 500\)
将式子化简：
考虑什么时候不合法，即上式小于 \(0\)。由于 \((b_i-b_j)^2\ge 0\)，因此 \((a_i-a_j)(b_i-b_j)<0\)。发现不合法时，交换 \(b_i,b_j\) 会让 \(\sum a_ib_i\) 更大，因此 \(\sum a_ib_i\) 取最大值时一定全都合法。于是跑最大权匹配即可，可以用原始对偶写。
搞出不合法的对然后直接暴力交换好像也是对的，最多交换 \(n^2\) 次，每次交换 \(O(n)\) 更新新产生的对。
T2
平面上有 \(n\) 条线段 \((i,l_i)\to (i,r_i)\)。有 \(m\) 次操作，每次操作给定 \(x_j,p_j,q_j\)，对于所有 \(i\in [p_j,q_j]\)，如果第 \(i\) 条线段经过了 \(x_j\)，那么将其在 \(x_j\) 处断成两半，并保留较长的一半。如果均分，则保留左侧。输出所有操作结束后每条线段的 \(l_i,r_i\)。
\(n\le 10^5,~m\le 10^6\)
要想将一组操作在很短的时间内一次作用到线段上，难点在于不知道每次操作会删掉哪一半。考虑将线段等分成三份，如果切在两边的两段上，则一定是中间的一段被保留；如果切在中间的段上，那么长度至少缩小为原先的 \(2/3\) 倍。于是依次处理每一条线段，用线段树维护所有修改操作，发现上面的操作都可以用线段树简单维护。时间复杂度 \(O(n\log^2 n+m\log n)\)。