SCOI 2016 美味（主席树+贪心）

发表于 |
字数统计: 921字 | 阅读时长 ≈ 5min

[SCOI2016]美味

问题描述

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

输入格式

第1行，两个整数，n，m，表示菜品数和顾客数。

第2行，n个整数，$a_1，a_2，…，a_n，$表示每道菜的评价值。

第3至m+2行，每行4个整数，b，x，l，r，表示该位顾客的期望值，偏好值，和可以选择菜品区间。

输出格式

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

样例输入

4 4

1 2 3 4

1 4 1 4

2 3 2 3

3 2 3 3

4 1 2 4

样例输出

9

7

6

7

提示

$1≤n≤2×10^5,$

$0≤a_i,b_i,x_i<10^5,$

$1≤l_i≤r_i≤n(1≤i≤m),$

$1≤m≤10^5$

令$Ans=b_i\ XOR\ (a_j+x_i)$，那么$Ans\ XOR\ b_i=a_j+x_i$，我们考虑按照二进制位贪心，那么如果当前讨论到从高到低的第$k$位，考虑$Ans$这一位能否取1，那么由于第$k$位以前的二进制位已经确定，我们令$Ans$的前$k$位和$b$的前$k$位异或的结果为$tmp$，其余未确定的位都取0，如果$b$的二进制第$k$位为$1$，那么$Ans$的第$k$位要为1，就有$Ans\ XOR\ b$的第$k$位要为0，只需要存在一个$a_j+x_i$在$[tmp,tmp|((1<<(Max-k))-1)]$之间就行了，$tmp|((1<<(Max-k))-1)$表示未确定的位（除第$k$位）均取1,这个查询可以用主席树来搞。

如果$b$的二进制第$k$位为0，那么$Ans\ XOR\ b$的第$k$位为1，同样只需要用主席树查找一下就行了。具体可以看代码。核心就是按位贪心看能否取到。

代码：

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
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cstring>
#define N 200005
#define M 10000005
using namespace std;
int n,m,A[N],T;
int tot,ls[M],rs[M],v[M],rt[N];
int CP(int p)
{
	int o=++tot;
	ls[o]=ls[p];
	rs[o]=rs[p];
	v[o]=v[p];
	return o;
}
int ADD(int p,int l,int r,int k)
{
	int o=CP(p);v[o]++;
	if(l==r)return o;
	int mid=l+r>>1;
	if(k<=mid)ls[o]=ADD(ls[o],l,mid,k);
	else rs[o]=ADD(rs[o],mid+1,r,k);
	return o;
}
int GS(int lp,int rp,int l,int r,int x,int y)
{
	if(x<=l&&y>=r)return v[lp]-v[rp];
	int mid=l+r>>1,sum=0;
	if(x<=mid&&y>=l)sum+=GS(ls[lp],ls[rp],l,mid,x,y);
	if(x<=r&&y>mid)sum+=GS(rs[lp],rs[rp],mid+1,r,x,y);
	return sum;
}
int main()
{
	int i,j,k,x,y,a,b,l,r,Ans,tmp,L,R;
	scanf("%d%d",&n,&m);
	for(i=1;i<=n;i++)scanf("%d",&A[i]),T=max(T,A[i]);
	for(i=1;i<=n;i++)rt[i]=ADD(rt[i-1],0,T,A[i]);
	for(i=1;i<=m;i++)
	{
		scanf("%d%d%d%d",&b,&x,&l,&r);
		for(j=20,Ans=0;j>=0;j--)
		{
			if(b>>j&1)
			{
				if(!GS(rt[r],rt[l-1],0,T,Ans-x,Ans+(1<<j)-1-x))Ans|=1<<j;
			}
			else
			{
				Ans|=(1<<j);
				if(!GS(rt[r],rt[l-1],0,T,Ans-x,Ans+(1<<j)-1-x))Ans^=1<<j;
			}
		}
		printf("%d\n",Ans^b);
	}
}