250722 模拟赛

T1 multiples

给定一个序列，你需要支持两种操作：

• 单点修改；
• 查询一个区间中有多少个数字满足区间中所有数字都是它的倍数。

\(n,q\le 5\times 10^5,\ a_i\le 10^9\)

不难发现这个数字一定是区间 \(\operatorname{gcd}\)，现在问题转化为求 \(\operatorname{gcd}\) 出现的次数。注意到当 \(\operatorname{gcd}\) 在区间中出现的时候，它一定是区间最小值。因此我们只需记录最小值和最小值出现的次数即可。

不难发现单点修改和区间 \(\operatorname{gcd}\) 都是 \(\log n+\log V\) 的，建树时间复杂度是 \(O(n\log V)\) 的（考虑斐波那契数的相邻两项 \(F_k,F_{k+1}\) 交替出现，可以卡满 \(O(n\log V)\)）。因此总时间复杂度 \(O(n\log V)\)（假设 \(n,q\) 同阶，\(n\) 的阶数不高于 \(V\)）。

T2 sort

给定一个序列，询问它有多少个子段满足第一项是非严格最小值，最后一项是非严格最大值。

\(n\le 10^6\)

我们枚举序列的最后一项 \(a_i\)，注意到子段的开头一定是前缀的非严格后缀最小值，并且一定在 \(i\) 左侧第一个大于 \(a_i\) 的数右边，容易使用单调栈求出。第二个限制使用二分即可，可以做到 \(O(n\log n)\)。

T3 matrix

称一个 \(n\times m\) 的矩阵合法，当且仅当对于任意一行一列 \((i,j)\)，要么该行的和非零，要么该列的和非零。给定一个 \(0/1\) 的 \(n\times m\) 的稀疏矩阵，每次询问给定 \(l_1,r_1,l_2,r_2\) 询问 \(i\in [l_1,r_1],\ j\in [l_2,r_2]\) 子矩阵是否合法。

\(n,m,q\le 10^5\)，记 \(k\) 为矩阵中 \(1\) 的数量，\(k\le 2\times 10^5\)

矩阵合法等价于，要么每行的和非零，要么每列的和非零。这样一次查询转换为两个子问题。现在只考虑行的子问题。

考虑每行的 \(0\) 的极长连续段，若存在一行的一个全 \(0\) 连续段包含当前询问的 \([l_2,r_2]\)，那么就存在一行的和为 \(0\)。不难发现这是一个三维偏序问题，使用 cdq 分治即可。时间复杂度 \(O(n\log ^2n)\)。

实际上我们有更优的解法。考虑从左往右扫描线，每个询问都挂在 \(r_2\) 处，每个数字 \(1\) 都挂在 \(j\) 处。然后用线段树维护每一行上一个 \(1\) 的位置，支持区间求最小值即可。时间复杂度 \(O(n\log n)\)。