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×105，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

题解

此题很明显可以用主席树。以权值为节点建树，然后每次二分判断每一位可否为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\n", b ^ L);

	}

	return 0;

}

美味