题目#
耳廓狐亚砜在观测豺狼座时收到了一些神秘信号。每个信号都是一个从 到 的整数。他好奇如何将这些信号整齐地记录下来,于是设计了一套不同寻常的排序规则。
对于一个由两两不同的信号组成的数组 ,以及 的任意一个排列 ,定义 为按照以下比较规则对 排序后得到的数组:
- 比较两个不同的信号 和 时,考虑它们恰好 位的二进制表示,位的编号从 (最低位)到 (最高位)。它们的顺序由使得 和 在第 位不同的最小 决定,其中第 位为 的信号排在前面。
然后,对于 中的一个元素 ,记 为满足 的唯一下标 。如果对于所有 种可能的排列 , 都相同,则称 为锚定值。
亚砜现在有一个由源自豺狼座的 个两两不同的信号组成的数组 。他想回答 次相互独立的询问。每次询问包含两个整数 和 。仅考虑连续子数组 ,求 中锚定值的个数。
输入格式
第一行包含三个整数 、 和 (,),分别表示数组的长度、二进制位数和询问次数。
第二行包含 个互不相同的整数 (),表示这些信号。
接下来 行,每行包含两个整数 和 (),描述一次询问。
输出格式
对于每次询问,输出一行一个整数,表示锚定值的个数。
思路#
题目较晦涩,但是按照题意模拟后不难发现:对于两个不同的元素 ,若 全部二进制为1的位置上 的二进制表示也为1,则 始终会排在 之前,反之亦然,容易证明该结论。
进一步推广,可得到一个元素为锚定值的等价条件,形式化的,有:若 为锚定值,则等价于对 ,有 或 .
我们不妨令 L[i] 为 a[i] 左边第一个让其不锚定的值,令 R[i] 为 a[i] 右边第一个让其不锚定的值,不存在则分别记为 0 和 n+1。接下来可转化为计数问题,对于 ,统计满足 的个数即为,后续为数据结构。
此处预处理看似是 实则为 ,下给出证明:
直接考虑扫描确实可能扫过整个数组,但是如果考虑对于某一特定位置 会有多少指针扫过该位置,若有 均可扫过 ,则容易推出 也有包含关系。并且又由于两两不同,考虑二进制表示中的 ,则知道 最多被扫过 次,因为可以证明不可能有两个 相同的数扫过同一个 ,故考虑 从 0 到 ,知有 次。
整体复杂度 .
代码#
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll lowbit(ll x) {
return x & (-x);
}
vector<int> bit;
void add(int x, int d) {
for (; x < (int)bit.size(); x += lowbit(x)) {
bit[x] += d;
}
}
int sum(int x) {
int res = 0;
for (; x > 0; x -= lowbit(x)) {
res += bit[x];
}
return res;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m, q;
cin >> n >> m >> q;
vector<ll> a(n + 1);
vector<int> L(n + 1), R(n + 1);
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
for (int i = 1; i <= n; i++) { // O(nm)
int l, r;
l = r = i;
while (l >= 1 && (((a[l] & a[i]) == a[i]) || ((a[l] | a[i]) == a[i]))) {
l--;
}
while (r <= n && (((a[r] & a[i]) == a[i]) || (a[r] | a[i]) == a[i])) {
r++;
}
L[i] = l, R[i] = r;
}
vector<vector<int>> c(n + 1);
for (int i = 1; i <= n; i++) {
c[L[i] + 1].push_back(i);
}
vector<vector<pair<int, int>>> qu(n + 1);
vector<int> ans(q);
int id = 0;
while (q--) {
int l, r;
cin >> l >> r;
qu[l].emplace_back(r, id++);
}
bit.resize(n + 1);
for (int l = 1; l <= n; l++) {
if (l > 1) {
add(l - 1, -1);
add(R[l - 1], 1);
}
for (int i : c[l]) {
add(i, 1);
add(R[i], -1);
}
for (auto [r, idx] : qu[l]) {
ans[idx] = sum(r);
}
}
for (int x : ans) {
cout << x << '\n';
}
return 0;
}
cpp