[SCOI2016]美味 题解
题目地址:洛谷:【P3293】[SCOI2016]美味 – 洛谷、BZOJ:Problem 4571. — [Scoi2016]美味
题目描述
一家餐厅有 n 道菜,编号 1…n ,大家对第 i 道菜的评价值为 ai(1<=i<=n)。有 m 位顾客,第 i 位顾客的期望值为 bi,而他的偏好值为 xi 。因此,第 i 位顾客认为第 j 道菜的美味度为 bi XOR (aj+xi),XOR 表示异或运算。
第 i 位顾客希望从这些菜中挑出他认为最美味的菜,即美味值最大的菜,但由于价格等因素,他只能从第 li 道到第 ri 道中选择。请你帮助他们找出最美味的菜。
题意简述
给一个长为n的数列a,每次查询给b、x、l、r,查询使得b xor (ai + x)最大的a数列中[l, r]这些数字中的ai。
输入输出格式
输入格式:
第1行,两个整数,n,m,表示菜品数和顾客数。
第2行,n个整数,a1,a2,…,an,表示每道菜的评价值。
第3至m+2行,每行4个整数,b,x,l,r,表示该位顾客的期望值,偏好值,和可以选择菜品区间。
输出格式:
输出 m 行,每行 1 个整数,ymax ,表示该位顾客选择的最美味的菜的美味值。
输入输出样例
输入样例#1:
4 4 1 2 3 4 1 4 1 4 2 3 2 3 3 2 3 3 4 1 2 4
输出样例#1:
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
题解
参考资料:[BZOJ4571][SCOI2016]美味 – 租酥雨 – 博客园
异或相关信息用Trie树方便,区间无修查询用主席树方便。这里二选一,我们选择主席树。
那么主席树应该怎么做呢?我们依然按位贪心,让bi尽量跟(aj + xi)每一位都不同,假设枚举到代表2^i的一位,且假设ans是之前已经确定的位加起来的总和,那么其实当该位为1的时候,枚举更低的位数构成的集合是一个长为2^i的区间 [ans, ans + 2^i - 1] ,我们只需要在主席树上查这个区间内有没有数字就好了。
总复杂度是O(n \log^2 n)。
代码
// Code by KSkun, 2018/5
#include <cstdio>
#include <cctype>
#include <algorithm>
typedef long long LL;
inline char fgc() {
static char buf[100000], *p1 = buf, *p2 = buf;
return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++;
}
inline LL readint() {
register LL res = 0, neg = 1;
register char c = fgc();
while(!isdigit(c)) {
if(c == '-') neg = -1;
c = fgc();
}
while(isdigit(c)) {
res = (res << 1) + (res << 3) + c - '0';
c = fgc();
}
return res * neg;
}
const int MAXN = 200005;
struct Node {
int lch, rch, val;
} tr[MAXN * 100];
int rt[MAXN], tot;
inline void insert(int &o, int l, int r, int x) {
tr[++tot] = tr[o]; o = tot;
tr[o].val++;
if(l == r) return;
int mid = (l + r) >> 1;
if(x <= mid) insert(tr[o].lch, l, mid, x);
else insert(tr[o].rch, mid + 1, r, x);
}
inline int query(int o1, int o2, int l, int r, int ll, int rr) {
if(l >= ll && r <= rr) return tr[o2].val - tr[o1].val;
int res = 0;
int mid = (l + r) >> 1;
if(ll <= mid) res += query(tr[o1].lch, tr[o2].lch, l, mid, ll, rr);
if(rr > mid) res += query(tr[o1].rch, tr[o2].rch, mid + 1, r, ll, rr);
return res;
}
int n, m, a[MAXN];
int main() {
n = readint(); m = readint();
for(int i = 1; i <= n; i++) {
a[i] = readint();
rt[i] = rt[i - 1];
insert(rt[i], 0, 100000, a[i]);
}
for(int i = 1, b, x, l, r; i <= m; i++) {
b = readint(); x = readint(); l = readint(); r = readint();
int ans = 0;
for(int i = 19; i >= 0; i--) {
int ql, qr, now;
if(b & (1 << i)) {
ql = ans; qr = ans + (1 << i) - 1; now = 0;
} else {
ql = ans + (1 << i); qr = ans + (1 << (i + 1)) - 1; now = 1;
}
if(!query(rt[l - 1], rt[r], 0, 100000,
std::max(0, ql - x), std::min(qr - x, 100000))) now ^= 1;
ans += now << i;
}
printf("%d\n", ans ^ b);
}
return 0;
}