The 2024 Sichuan Provincial Collegiate Programming Contest vp 记录

· · 题解

The 2024 Sichuan Provincial Collegiate Programming Contest vp 记录

组队 vp，只写我想出来和改出来的。

A

给定排列 a_{1\dots n}，若 (a_i,a_j) 为逆序对，染黑网格图上点 (i,a_j)，求网格图中连通块数，n\le 3\times 10^5。

Sol

网格图连通块个数统计，考虑以一个点代表一个连通快，例如最靠上一行中最靠左的一个点，统计时：

  • 先统计出(i,j) 染黑同时 (i,j-1) 不染黑的点。
  • 再在这些点中筛选出满足“不存在 (i,k) 满足 k>j 且 (i,j+1\dots k) 和 (i-1,k) 均染黑的情况”的 (i,j)。
  • 需要结合具体题目分析网格图的性质，例如本题中每个连通块最靠上的一排中最左点和最靠左的一行中最上点必重合 ^*。

如上，分析网格图性质，先对 ^* 证明：若存在 (i,j)，(i+x,j) 和 (i,j+y) 同时为黑 (x,y>0) 且 (i,j) 为白，其需要分别满足 i<pos_j\land a_i>j 不成立，i+x<pos_j\land a_{i+x}>j 和 i<pos_{j+y}\land a_i>j+y 同时成立，这是不可能的，其中 pos_i 代表 i 在 a 中的位置。

这样你先统计出所有 ^1(i,j) 黑 (i-1,j) 白的点，再在其中筛选出 ^2(i,j-1) 白即可。对于 ^1，相当于 i<pos_j\land a_i>j 成立，同时 i-1<pos_j\land a_{i-1}>j 不成立，即 a_{i-1}\le j<a_i 且 i<pos_j。^2 即 i<pos_{j-1}\land a_i>j-1 不成立。

问题转化为求 pos_{j-1}\le i<pos_j 且 a_{i-1}\le j<a_i 的 (i,j) 对数。

两维的偏序关系计数一定树状数组维护，计算满足第一维情况下哪些对象 i\prec j，用树状数组维护 i 的第二维，按 j 统计贡献，查询 i 第二维满足的范围即可。

则若 pos_{j-1}<pos_j，在 pos_{j-1} 统计贡献之前将 j 统计到树状数组中，pos_j 统计贡献之前将其撤销，再按 i 统计贡献，查询区间内 j 的个数，复杂度 O(n\log n)。

C

我复习完网络流再补。

G

给定 x_{1\dots n}，对于一组 (a,b)，记 f(i)=(a\oplus x_i)-b。q 次询问 (a,b)，求最小的 i 满足 f(i)\cdot f(i+1)\le 0 或判断无解（原题中为任意一个 i），n,q\le 3\times 10^5,1\le a_i\le 10^9。

Sol

记 g(i)=a\oplus x_i，你发现只需要求出首个 g(i)<b 的位置 p，首个 g(i)>b 的位置 q，和首个 g(i)=b 的位置 r，若 p=1 则答案为 \min(q,r)-1，q=1 则为 \min(p,r)-1，否则为 1。

要求解 p,q,r，先将所有 x_i 插入 01Trie。从根开始位从高到低，若 b 这一位为 1 则走与 a 这一位相反的儿子，否则走相同。若 b 这一位为 0，与上述相反走必定导致 >b；若 b 该位为 1，反走必定 <b，想到用子树内编号最小 x_i 更新 p,q。

对 Trie 中每个点记录结束点在其子树内的所有 x_i 中 i 的最小值，可以O(\log V) 得到 p 和 q，r 走到尽头用这个点最小编号更新即可，复杂度 O((n+q)\log V)。

写法上，Trie 的好习惯是从 1 开始编号。

I

网格图，格子编号从 (1,1) 到 (l,h)（左下到右上），n 个矩形，第 i 个大小 x_i\times y_i。按编号从前往后放置，每次放置的左下角在能放置位置中行编号最小的位置中列编号最小的位置，输出这个值或判断不能放置，n\le 50,l,h\le 10^9。

Sol

直接计算答案是很难的事，但是你可以 O(n) 判断一个位置能否放置当前矩形（不与之前矩形交且在 l\times h 范围内），你需要缩小答案的范围。

记录之前放置矩形的上边界行数的集合 S_x 和右边界列数 S_y，则当前矩形的左下角 (p,q) 必然满足 p-1\in S_x,q-1\in S_y，暴力枚举复杂度 O(n^4)。

实现中需要注意，判断是否与之前矩形交的过程中，只看成功放置的矩形。