bzoj4571: [Scoi2016]美味

4571: [Scoi2016]美味

Time Limit: 30 Sec Memory Limit: 256 MB

Submit: 275 Solved: 141

[Submit][Status][Discuss]

Description

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

Input

第1行，两个整数，n，m，表示菜品数和顾客数。
第2行，n个整数，a1，a2，...，an，表示每道菜的评价值。
第3至m+2行，每行4个整数，b，x，l，r，表示该位顾客的期望值，偏好值，和可以选择菜品区间。
1≤n≤2×10^{5，0≤ai,bi,xi＜10}5，1≤li≤ri≤n(1≤i≤m)；1≤m≤10^5

Output

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

Sample Input

4 4

1 2 3 4

1 4 1 4

2 3 2 3

3 2 3 3

4 1 2 4

Sample Output

9

7

6

7

题解

此题很明显可以用主席树。以权值为节点建树，然后每次二分判断每一位可否为1。

这道题有学长当时用区间建树过了，我硬是没想出来他怎么做的。

#include <cstdio>
#include <cstring>

const int N = 2e5 + 5, M = N * 50;
int totNode, root[N], ls[M], rs[M], siz[M];

int ina; bool insign; char inc;
inline int geti() {
	insign = 0; while ((inc = getchar()) < '0' || inc > '9') insign |= inc == '-'; ina = inc - '0';
	while ((inc = getchar()) >= '0' && inc <= '9') ina = (ina << 3) + (ina << 1) + inc - '0';
	return insign ? -ina : ina;
}

void Update(int l, int r, int last, int &cur, int val) {
	cur = ++totNode;
	ls[cur] = ls[last]; rs[cur] = rs[last]; siz[cur] = siz[last] + 1;
	if (l == r) return;
	int mid = l + r >> 1;
	if (val <= mid) Update(l, mid, ls[last], ls[cur], val);
	else Update(mid + 1, r, rs[last], rs[cur], val);
}

bool Query(int l, int r, int last, int cur, int x, int y) {
	if (!(siz[cur] - siz[last])) return false;
	if (x <= l && r <= y) return true;
	int mid = l + r >> 1;
	if (y <= mid) return Query(l, mid, ls[last], ls[cur], x, y);
	else if (x > mid) return Query(mid + 1, r, rs[last], rs[cur], x, y);
	else return Query(l, mid, ls[last], ls[cur], x, mid) || Query(mid + 1, r, rs[last], rs[cur], mid + 1, y);
}

int main() {
	int n, m, b, l, r, x, L, R, i, mid;
	n = geti(), m = geti();
	for (x = 1; x <= n; ++x) 
	  Update(0, N, root[x - 1], root[x], geti());
	while (m--) {
		b = geti(), x = geti(), l = geti(), r = geti();
		L = 0, R = (1 << 19) - 1;
		for (i = 18; ~i; --i) {
			mid = L + R >> 1;
			if (b & (1 << i)) Query(0, N, root[l - 1], root[r], L - x, mid - x) ? (R = mid) : (L = mid + 1);
			else Query(0, N, root[l - 1], root[r], mid - x + 1, R - x) ? (L = mid + 1) : (R = mid);
		}
		printf("%d
", b ^ L);
	}
	return 0;
}