「NOI Online 2021 #1」岛屿探险
题目大意
给定一排 (n) 个元素，每个元素有两个属性：(a_i, b_i)。
有 (q) 次询问，每次询问给出四个参数 (l_j, r_j, c_j, d_j)。问区间 ([l, r]) 里满足 (a_ioperatorname{xor} c_j leq min{b_i, d_j}) 的 (i) 有多少个。
数据范围：(1leq n,qleq 10^5)，(1leq l_jleq r_jleq n)，(0leq a_i, b_i, c_j, d_jleq 2^{24} - 1)。
本题题解
0. 约定
设 (m = max{a_i, b_i, c_j, d_j})，这是分析复杂度用的。
1. 分析一次询问
对于一次询问 (l_j, r_j, c_j, d_j)，考虑把 (i) 分为 (b_i > d_j) 和 (b_ileq d_j) 两类，分别统计答案。
1.1. b[i] > d[j] 的 i
对于 (b_i > d_j) 的 (i)，答案是 (sum_{i} [a_i operatorname{xor} c_jleq d_j])。此时的特点是：答案与 (b_i) 无关。考虑把这些 (a_i) 插入到一个 ( ext{01 trie}) 中：也就是按二进制从高位到低位的顺序，把 (a_i) 当成一个 (01) 串。我们在 ( ext{01 trie}) 上从根往下走（也就是按二进制从高位向低位走），对于当前节点，假设它深度为 (h)，那么它代表的值等于 (c_joperatorname{xor}d_j) 的前 (h) 高位。考虑下一位：
- 如果 (d_j) 的下一位为 (0)，那么说明 (a_i) 的下一位必须和 (c_j) 的下一位相等（否则 (a_i operatorname{xor} c_j > d_j)，不满足要求），我们直接向这个方向走即可。
- 如果 (d_j) 的下一位为 (1)，那么有两种可能：
- 如果 (a_i) 的下一位和 (c_j) 的下一位相等，那么无论 (a_i) 后面更低的位上填什么，都一定满足：(a_ioperatorname{xor} c_j < d_j)。所以 (a_i) 后面的位可以任意填，方案数就是这一整棵子树里 (a_i) 的个数之和。
- 如果 (a_i) 的下一位和 (c_j) 的下一位不相等，那么此时 (a_i) 仍然是等于 (c_j operatorname{xor} d_j) 的。我们向这个方向走过去，然后考虑更低的位即可。
1.2. b[i] <= d[j] 的 i
对于 (b_i leq d_j) 的 (i)，答案是 (sum_{i} [a_i operatorname{xor} c_jleq b_i])。看到限制里既有 (a_i)，又有 (b_i)，我们难以把它们放到同一个数据结构里去，所以很难实现查询。换个角度考虑：观察 (a_ioperatorname{xor} c_j leq min{b_i, d_j}) 这个式子，你会发现 ((a, b)) 和 ((c, d)) 是对称的。那么，把修改当成询问做，询问当成修改做，是不是就和 1.1. 的情况一样了呢？
具体来说，我们将询问离线，把所有 (c_j)，按上述方法（和上面的 (a_i) 一样）插入一个 ( ext{01 trie}) 中。然后对每组 ((a_i, b_i))，把它当成上面的 ((c_j, d_j))，在 ( ext{01 trie}) 上“查询”。当然，我们其实不是要查询一个结果，而是要把它“贡献”到符合条件的 (c_j) 里。在 1.1, 里，我们遇到一整棵符合条件的子树，就把这个子树里 (a_i) 的数量加入答案中；而现在，我们遇到一整棵符合条件的子树，就在该节点处打一个标记，表示令子树里所有 (c_j) 的答案加上 (1)。最后，每个 (j) 的答案，就是 (c_j) 到根路径上的标记之和。
2. 多次询问时
当然我们不可能每次询问都重新建两个 ( ext{trie})，那样时间复杂度是 (mathcal{O}(qnlog m))，还不如暴力。
考虑一个简化的问题：如果只有 (b_i > d_j) 的 (i)（也就是测试点 (5sim 7)），那么可以在所有询问开始前，先建好一个可持久化 ( ext{trie})。则查询时，将 (r_j) 和 (l_j - 1) 两个时刻的 ( ext{trie}) 上查询的结果相减即可。时间复杂度 (mathcal{O}(qlog m))。
考虑另一个简化的问题：如果只有 (b_i leq d_j) 的 (i)（也就是测试点 (8sim 11)），那么可以先将询问离线，建出所有 (c_j) 的 ( ext{trie})。然后将询问拆成两个：([1, r_j]) 和 ([1, l_j - 1])（相减得到答案）。现在所有询问的左端点都是 (1)。将询问按右端点排序，从小到大扫描。每次加入当前的 (i)（如前文所述，这个加入操作有点像 1.1. 里的查询操作，只不过把查询变成了打标记），然后对右端点为 (i) 的询问统计答案。时间复杂度 (mathcal{O}(qlog m))。
上述两种情况我们都会做了，那么现在唯一的问题是，怎么把 (b_i > d_j) 的 (i) 和 (b_ileq d_j) 的 (i) 分离出来。考虑把所有 (b_i, d_j) 放在一起排序（特别地，(b_i, d_j) 相等时，(b_i) 放在前）。然后做 ( ext{cdq}) 分治。那么每次只需要考虑右半边对左半边的贡献。具体来说，取出右半边的所有 (a_i)，左半边的所有 ((c_j,d_j))，按情况 1.1. 的方法做一次；再取出右半边的所有 (c_j)，左半边的所有 ((a_i,b_i))，按情况 1.2. 的方法做一次。就求出所有答案了。
每层分治时，做问题 1.1. 和 1.2.，时间复杂度是 (mathcal{O}(mathrm{len}log m))（(mathrm{len}) 是当前分治区间的长度），所以总时间复杂度 (mathcal{O}((n + q)cdot log (n + q)cdot log m))。
参考代码
因为里面有一个快读的板子，所以有点长，小伙伴们不要被长度吓到哦 QAQ
// problem: C
#include <bits/stdc++.h>
using namespace std;
#define mk make_pair
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
template<typename T> inline void ckmax(T& x, T y) { x = (y > x ? y : x); }
template<typename T> inline void ckmin(T& x, T y) { x = (y < x ? y : x); }
/* --------------- fast io --------------- */ // begin
namespace Fread {
const int SIZE = 1 << 21;
char buf[SIZE], *S, *T;
inline char getchar() {
if (S == T) {
T = (S = buf) + fread(buf, 1, SIZE, stdin);
if (S == T) return '
';
}
return *S++;
}
} // namespace Fread
namespace Fwrite {
const int SIZE = 1 << 21;
char buf[SIZE], *S = buf, *T = buf + SIZE;
inline void flush() {
fwrite(buf, 1, S - buf, stdout);
S = buf;
}
inline void putchar(char c) {
*S++ = c;
if (S == T) flush();
}
struct NTR {
~ NTR() { flush(); }
} ztr;
} // namespace Fwrite
// #ifdef ONLINE_JUDGE
#define getchar Fread :: getchar
#define putchar Fwrite :: putchar
// #endif
namespace Fastio {
struct Reader {
template<typename T>
Reader& operator >> (T& x) {
char c = getchar();
T f = 1;
while (c < '0' || c > '9') {
if (c == '-') f = -1;
c = getchar();
}
x = 0;
while (c >= '0' && c <= '9') {
x = x * 10 + (c - '0');
c = getchar();
}
x *= f;
return *this;
}
Reader& operator >> (char& c) {
c = getchar();
while (c == ' ' || c == '
') c = getchar();
return *this;
}
Reader& operator >> (char* str) {
int len = 0;
char c = getchar();
while (c == ' ' || c == '
') c = getchar();
while (c != ' ' && c != '
' && c != '
') { //
in windows
str[len++] = c;
c = getchar();
}
str[len] = ' ';
return *this;
}
Reader(){}
} cin;
const char endl = '
';
struct Writer {
template<typename T>
Writer& operator << (T x) {
if (x == 0) { putchar('0'); return *this; }
if (x < 0) { putchar('-'); x = -x; }
static int sta[45];
int top = 0;
while (x) { sta[++top] = x % 10; x /= 10; }
while (top) { putchar(sta[top] + '0'); --top; }
return *this;
}
Writer& operator << (char c) {
putchar(c);
return *this;
}
Writer& operator << (char* str) {
int cur = 0;
while (str[cur]) putchar(str[cur++]);
return *this;
}
Writer& operator << (const char* str) {
int cur = 0;
while (str[cur]) putchar(str[cur++]);
return *this;
}
Writer(){}
} cout;
} // namespace Fastio
#define cin Fastio :: cin
#define cout Fastio :: cout
#define endl Fastio :: endl
/* --------------- fast io --------------- */ // end
const int MAXN = 1e5;
int n, a[MAXN + 5], b[MAXN + 5];
int q, ans[MAXN + 5], ql[MAXN + 5], qr[MAXN + 5], c[MAXN + 5], d[MAXN + 5];
pii e[MAXN * 2 + 5];
int vals[MAXN + 5], cnt_val;
pii ee[MAXN * 3 + 5];
int cnt_ee;
int root[MAXN + 5], ch[MAXN * 50 + 5][2], sum[MAXN * 50 + 5], cnt_node;
int new_node(int old) {
++cnt_node;
ch[cnt_node][0] = ch[old][0];
ch[cnt_node][1] = ch[old][1];
sum[cnt_node] = sum[old];
return cnt_node;
}
void insert1(int& rt, int y, int v) {
rt = new_node(y);
int x = rt;
sum[x]++;
for (int i = 23; i >= 0; --i) {
int t = ((v >> i) & 1);
ch[x][t] = new_node(ch[y][t]);
sum[ch[x][t]]++;
x = ch[x][t];
y = ch[y][t];
}
}
int query1(int x, int y, int c, int d) {
assert(x != 0);
int res = 0;
for (int i = 23; i >= 0; --i) {
if (!x) break;
int cc = ((c >> i) & 1);
int dd = ((d >> i) & 1);
if (dd) {
res += sum[ch[x][cc]] - sum[ch[y][cc]]; // 严格小于 d
}
x = ch[x][cc ^ dd];
y = ch[y][cc ^ dd]; // 等于 d
}
res += sum[x] - sum[y];
return res;
}
void insert2(int x, int v) {
// 不可持久化
assert(x != 0);
for (int i = 23; i >= 0; --i) {
int t = ((v >> i) & 1);
if (!ch[x][t]) {
ch[x][t] = new_node(0);
}
x = ch[x][t];
}
}
void make_contrib2(int x, int c, int d) {
for (int i = 23; i >= 0; --i) {
if (!x) break;
int cc = ((c >> i) & 1);
int dd = ((d >> i) & 1);
if (dd) {
if (ch[x][cc])
sum[ch[x][cc]]++;
}
x = ch[x][cc ^ dd];
}
if (x)
sum[x]++;
}
int query2(int x, int v) {
int res = 0;
for (int i = 23; i >= 0; --i) {
assert(x != 0);
res += sum[x];
int t = ((v >> i) & 1);
x = ch[x][t];
}
assert(x != 0);
res += sum[x];
return res;
}
void cdq(int l, int r) {
if (l == r) {
return;
}
int mid = (l + r) >> 1;
cdq(l, mid);
cdq(mid + 1, r);
// CASE1: b[i] > d[j], 右边位置对左边询问贡献
cnt_val = 0;
for (int i = mid + 1; i <= r; ++i) {
if (e[i].se > n)
continue;
int idx = e[i].se;
vals[++cnt_val] = idx;
}
sort(vals + 1, vals + cnt_val + 1); // 离散化
cnt_node = 0;
for (int i = 1; i <= cnt_val; ++i) {
int idx = vals[i];
insert1(root[i], root[i - 1], a[idx]);
}
for (int i = l; i <= mid; ++i) {
if (e[i].se <= n)
continue;
int idx = e[i].se - n;
int L = lower_bound(vals + 1, vals + cnt_val + 1, ql[idx]) - vals;
int R = upper_bound(vals + 1, vals + cnt_val + 1, qr[idx]) - vals - 1;
if (L > R)
continue;
assert(L >= 1 && L <= cnt_val);
assert(R >= 1 && R <= cnt_val);
// for (int j = L; j <= R; ++j) {
// ans[idx] += ((a[vals[j]] ^ c[idx]) <= d[idx]);
// }
ans[idx] += query1(root[R], root[L - 1], c[idx], d[idx]);
}
// CASE2: d[j] >= b[i], 右边的询问被左边位置贡献
cnt_node = 0;
new_node(0); // root
cnt_ee = 0;
for (int i = mid + 1; i <= r; ++i) {
if (e[i].se <= n)
continue;
int idx = e[i].se - n;
insert2(1, c[idx]);
ee[++cnt_ee] = mk(ql[idx] - 1, idx + n);
ee[++cnt_ee] = mk(qr[idx], idx + n + q);
}
for (int i = l; i <= mid; ++i) {
if (e[i].se > n)
continue;
int idx = e[i].se;
ee[++cnt_ee] = mk(idx, idx);
}
sort(ee + 1, ee + cnt_ee + 1);
for (int i = 1; i <= cnt_ee; ++i) {
if (ee[i].se <= n) {
int idx = ee[i].se;
make_contrib2(1, a[idx], b[idx]);
} else if (ee[i].se <= n + q) {
int idx = ee[i].se - n;
ans[idx] -= query2(1, c[idx]);
} else {
int idx = ee[i].se - n - q;
ans[idx] += query2(1, c[idx]);
}
}
}
int main() {
// freopen("island.in", "r", stdin);
// freopen("island.out", "w", stdout);
cin >> n >> q;
for (int i = 1; i <= n; ++i) {
cin >> a[i] >> b[i];
e[i] = mk(b[i], i);
}
for (int i = 1; i <= q; ++i) {
cin >> ql[i] >> qr[i] >> c[i] >> d[i];
e[i + n] = mk(d[i], i + n);
}
sort(e + 1, e + n + q + 1);
cdq(1, n + q);
for (int i = 1; i <= q; ++i) {
cout << ans[i] << endl;
}
return 0;
}