xy0v0's Blog

Back

题目#

耳廓狐亚砜在观测豺狼座时收到了一些神秘信号。每个信号都是一个从 00 到 (2m−1)(2^m-1) 的整数。他好奇如何将这些信号整齐地记录下来,于是设计了一套不同寻常的排序规则。

对于一个由两两不同的信号组成的数组 bb,以及 {0,1,…,m−1}\{0,1,\ldots,m-1\} 的任意一个排列 pp,定义 sort⁡p(b)\operatorname{sort}_p(b) 为按照以下比较规则对 bb 排序后得到的数组:

  • 比较两个不同的信号 xx 和 yy 时,考虑它们恰好 mm 位的二进制表示,位的编号从 00(最低位)到 (m−1)(m-1)(最高位)。它们的顺序由使得 xx 和 yy 在第 pip_i 位不同的最小 ii 决定,其中第 pip_i 位为 00 的信号排在前面。

然后,对于 bb 中的一个元素 xx,记 rank⁡p(x)\operatorname{rank}_p(x) 为满足 (sort⁡p(b))i=x(\operatorname{sort}_p(b))_i=x 的唯一下标 ii。如果对于所有 m!m! 种可能的排列 pp,rank⁡p(x)\operatorname{rank}_p(x) 都相同,则称 xx 为锚定值。

亚砜现在有一个由源自豺狼座的 nn 个两两不同的信号组成的数组 aa。他想回答 qq 次相互独立的询问。每次询问包含两个整数 ll 和 rr。仅考虑连续子数组 b=[al,al+1,…,ar]b=[a_l,a_{l+1},\ldots,a_r],求 bb 中锚定值的个数。

输入格式

第一行包含三个整数 nn、mm 和 qq(1≤n,q≤2×1051\le n,q\le 2\times 10^5,1≤m≤601\le m\le 60),分别表示数组的长度、二进制位数和询问次数。

第二行包含 nn 个互不相同的整数 a1,a2,…,ana_1,a_2,\ldots,a_n(0≤ai<2m0\le a_i<2^m),表示这些信号。

接下来 qq 行,每行包含两个整数 ll 和 rr(1≤l≤r≤n1\le l\le r\le n),描述一次询问。

输出格式

对于每次询问,输出一行一个整数,表示锚定值的个数。

思路#

题目较晦涩,但是按照题意模拟后不难发现:对于两个不同的元素 a,ba,b ,若 aa 全部二进制为1的位置上 bb 的二进制表示也为1,则 aa 始终会排在 bb 之前,反之亦然,容易证明该结论。

进一步推广,可得到一个元素为锚定值的等价条件,形式化的,有:若 aka_k 为锚定值,则等价于对 ∀ai\forall a_i ,有 ai&ak=aka_i \& a_k = a_k 或 ai∣ak=aka_i |a_k = a_k .

我们不妨令 L[i] 为 a[i] 左边第一个让其不锚定的值,令 R[i] 为 a[i] 右边第一个让其不锚定的值,不存在则分别记为 0 和 n+1。接下来可转化为计数问题,对于 (l,r)(l,r) ,统计满足 R[i]>r,L[i]<l,i∈[l,r]R[i]>r,L[i]<l,i\in[l,r] 的个数即为,后续为数据结构。

此处预处理看似是 O(n2)O(n^2) 实则为 O(nm)O(nm) ,下给出证明:

直接考虑扫描确实可能扫过整个数组,但是如果考虑对于某一特定位置 jj 会有多少指针扫过该位置,若有 i1<i2i_1<i_2 均可扫过 jj ,则容易推出 ai1,ai2a_{i1},a_{i2} 也有包含关系。并且又由于两两不同,考虑二进制表示中的 popcountpopcount ,则知道 jj 最多被扫过 m+1m+1 次,因为可以证明不可能有两个 popcountpopcount 相同的数扫过同一个 jj ,故考虑 popcountpopcount 从 0 到 mm ,知有 m+1m+1 次。

整体复杂度 O(nm+(n+m)log⁡n)O(nm+(n+m)\log n) .

代码#

补题 | 2026沈阳 J

https://www.xy0v0.top/blog/shenyang-2026-j
Author xy0v0 Published at Copyright CC BY-NC-SA 4.0