「BZOJ-4571」[Scoi2016]美味

一家餐厅有 n 道菜,编号 1…n ,大家对第 i 道菜的评价值为 ai(1≤i≤n)。有 m 位顾客,第 i 位顾客的期望值为 bi,而他的偏好值为 xi 。因此,第 i 位顾客认为第 j 道菜的美味度为 bi XOR(aj+xi),XOR 表示异或运算。第 i 位顾客希望从这些菜中挑出他认为最美味的菜,即美味值最大的菜,但由于价格等因素,他只能从第 li 道到第 ri 道中选择。请你帮助他们找出最美味的菜。

链接

bzoj-4571

输入

第1行,两个整数,n,m,表示菜品数和顾客数。
第2行,n个整数,a1,a2,…,an,表示每道菜的评价值。
第3至m+2行,每行4个整数,b,x,l,r,表示该位顾客的期望值,偏好值,和可以选择菜品区间。

输出

输出 m 行,每行 1 个整数,ymax ,表示该位顾客选择的最美味的菜的美味值。

样例

输入

1
2
3
4
5
6
4 4
1 2 3 4
1 4 1 4
2 3 2 3
3 2 3 3
4 1 2 4

输出

1
2
3
4
9
7
6
7

$1≤n≤2×10^5,0≤ai,bi,xi<10^5,1≤li≤ri≤n(1≤i≤m);1≤m≤10^5$

题解

考虑没有加上那个xi的做法,显然,我们可以用贪心策略,高位取1显然比低位取1更优,这时可以利用可持久化trie树维护出每个状态是否能够选1。
然而这道题有xi的偏好值,可持久化trie树就无能为力了,
运用主席树来维护,同样高位向低位贪心,由于高位的选择会确定某个状态的选择区间 ( 实际的选择区间为不考虑偏好值的选择区间的l和r均减去xi ) ,而这个区间必然是连续的,所以可以在权值线段树中查找这段区间是否能取1。
(然而naive的蒟蒻并没有想到)

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
#include <iostream>
#include <cstring>
#include <ctime>
#include <cmath>
#include <cctype>
#include <cstdio>
#include <cstdlib>
using namespace std;
const int M = 100000;
inline void read(int &v) {
static char ch;
v = 0;
bool p = 0;
do {
ch = getchar();
if (ch == '-')
p = 1;
} while (!isdigit(ch));
while (isdigit(ch)) {
v = (v + (v << 2) << 1) + (ch ^ 48);
ch = getchar();
}
if (p)
v = -v;
}
int a[200005];
int root[200005];
int tot;
struct node {
int ls, rs, cnt;
} tr[8000005];
inline void build(int prev, int now, int l, int r, int x) {
tr[now].cnt = tr[prev].cnt + 1;
if (l == r) {
return;
}
int mid = l + r >> 1;
if (x <= mid)
{
tr[now].rs = tr[prev].rs;
tr[now].ls = ++tot;
build(tr[prev].ls, tr[now].ls, l, mid, x);
}
else {
tr[now].ls = tr[prev].ls;
tr[now].rs = ++tot;
build(tr[prev].rs, tr[now].rs, mid + 1, r, x);
}
}
inline bool query(int prev, int now, int l, int r, int L, int R) {
if (!(tr[now].cnt - tr[prev].cnt)) {
return 0;
}
if (l >= L && r <= R) return 1;
int mid = l + r >> 1;
int ret = 0;
if (L <= mid)ret |= query(tr[prev].ls, tr[now].ls, l, mid, L, R);
if (R > mid) ret |= query(tr[prev].rs, tr[now].rs, mid + 1, r, L, R);
return ret;
}
int main() {
//freopen("in.in","r",stdin);
int n, m;
read(n);
read(m);
for (int i = 1; i <= n; ++i) {
read(a[i]);
}
for (int i = 1; i <= n; ++i) {
root[i] = ++tot;
build(root[i - 1], root[i], 0, M, a[i]);
}
int l, r, b, x;
int s[30], t;
int L, R, mid;
int ans = 0;
for (int i = 1; i <= m; ++i) {
ans = 0;
//R(b);
read(b), read(x), read(l), read(r);
t = b;
L = 0, R = (1 << 20) - 1;
for (int j = 20; j >= 1; --j) {
s[j] = t & 1;
t >>= 1;
}
for (int j = 1; j <= 20; ++j) {
mid = L + R >> 1;
if (!s[j]) {
if (query(root[l - 1], root[r], 0, M, mid + 1 - x, R - x)) {
L = mid + 1;
}
else {
R = mid;
}
}
else {
if (query(root[l - 1], root[r], 0, M, L - x, mid - x)) {
R = mid;
}
else {
L = mid + 1;
}
}
}
cout << (b ^ L) << '\n';
}
return 0;
}
文章目录
  1. 1. 链接
  2. 2. 输入
  3. 3. 输出
  4. 4. 样例
    1. 4.1. 输入
    2. 4.2. 输出
  5. 5. 题解
  6. 6. 代码