前置知识:可持久化线段树(主席树)
问题
有一个长度为 \(n\) 的序列 \(a_1,a_2,...,a_n\)。每次询问给你 \(b\)、\(x\),你需要求出 \(\max\{a_i+x \bigoplus b\}\)。
\(1 \le l \le r \le n \le 2\times 10^5, 0 \le a_i,b,x < 10^5\)
首先,有 \(l,r\) 应该要可持久化。然后……01trie?行不通啊。
没有头绪的话,先来看一道比较经典的题。
经典の问题
有一个长度为 \(n\) 的数列 \(a_1,a_2,...,a_n\)。有 \(m\) 次询问,给你一个数 \(k\),求出 \(k \bigoplus a_i\) 最大的 \(a_i\)。
\(1 \le n,m,a_i \le 10^5\)
你肯定知道这是 01Trie 板子,但是我想介绍另一个东西——
Technology
还是考虑贪心,从高位往低位贪。
假设 \(w_x(i)\) 表示数 \(x\) 二进制下的第 \(i\) 位,当前的答案(即确定了前几位)是 \(ans\)。
以一个例子来说明:
k: 01100100101
ans: 1010???????
假如我们当前已经考虑完了前 \(4\) 位(从高往低),那我们肯定想要让 \(w_{ans}(5) \ne w_k(5)\),即 \(w_{ans}(5) = 1\)。那我们怎么知道是否存在这样的 \(ans\)?显然,此时需要满足的是:\((10101000000)_2 \le ans \le (10101111111)_2\)。权值线段树上查即可。
那么再来看这个题大家就都会做了,把范围再缩小 \(x\) 就行。由于需要限制区间,将权值线段树可持久化即可。
代码
#include <bits/stdc++.h>
using namespace std;
#define lson son[u][0]
#define rson son[u][1]
const int N = 2e5 + 5, ND = N << 6;
struct segtree
{
int tot, son[ND][2], cnt[ND];
void pushup(int u)
{
cnt[u] = cnt[lson] + cnt[rson];
}
int update(int v, int l, int r, int it)
{
int u = ++tot;
if (l == r)
{
cnt[u] = cnt[v] + 1;
return u;
}
lson = son[v][0], rson = son[v][1];
int mid = (l + r) >> 1;
if (it <= mid)
lson = update(son[v][0], l, mid, it);
else
rson = update(son[v][1], mid + 1, r, it);
pushup(u);
return u;
}
int query(int u, int l, int r, int L, int R)
{
if (L <= l && r <= R)
return cnt[u];
if (R < l || r < L)
return 0;
int mid = (l + r) >> 1;
return query(lson, l, mid, L, R) + query(rson, mid + 1, r, L, R);
}
} t;
int n, Q, a[N], root[N];
/*
if b_i == 0
a in [ans + (1 << i) - x, ans + (1 << i + 1) - 1 - x]
else
a in [ans - x, ans + (1 << i) - 1 - x]
*/
int main()
{
#ifdef aquazhao
freopen("data.in", "r", stdin);
freopen("data.out", "w", stdout);
#endif
cin >> n >> Q;
for (int i = 1; i <= n; i++)
scanf("%d", a + i), root[i] = t.update(root[i - 1], 0, 1e5, a[i]);
int b, x, l, r;
while (Q--)
{
scanf("%d%d%d%d", &b, &x, &l, &r);
int ans = 0;
for (int i = 17; i >= 0; i--)
{
int cnt;
if (!(b & (1 << i)))
{
int L = max(0, ans + (1 << i) - x), R = min((int)1e5, ans + (1 << (i + 1)) - 1 - x);
cnt = t.query(root[r], 0, 1e5, L, R) - t.query(root[l - 1], 0, 1e5, L, R);
ans += cnt > 0 ? 1 << i : 0;
}
else
{
int L = max(0, ans - x), R = min((int)1e5, ans + (1 << i) - 1 - x);
cnt = t.query(root[r], 0, 1e5, L, R) - t.query(root[l - 1], 0, 1e5, L, R);
ans += cnt > 0 ? 0 : 1 << i;
}
}
printf("%d\n", b ^ ans);
}
return 0;
}
标签:10,le,int,题解,线段,ans,SCOI2016,美味
From: https://www.cnblogs.com/avalaunch/p/18542507