题目链接

loj#2016. 「SCOI2016」美味

题解

对于不带x的怎么做....可持久化trie树

对于带x，和trie树一样贪心

对于答案的二进制位，从高往低位贪心，

二进制可以表示所有的数，那么每一位的选取情况，对于之后的可选区间也是一定的

贪心时，判断当前位，是否可以为1，

用线段树维护一下，每次走左儿子代表这一位选了1，走又儿子为选了0，这样区间是不交

对于b的限制，改一下查询的区间就行了

代码

#include<cstdio>

#include<algorithm>

inline int read() {

	int x = 0,f = 1;

	char c = getchar();

	while(c < '0' || c > '9')c = getchar();

	while(c <= '9' && c >= '0') x = x * 10 + c - '0',c = getchar();

	return x * f;

}

const int maxn = 200007;

int n,m;

int a[maxn];

int rt[maxn],tot = 0 ;

int ls[maxn * 20 + 7],rs[maxn * 20 + 7],sz[maxn * 20 + 7];

void insert(int y,int &x,int l,int r,int k) {

	x = ++ tot; ls[x] = ls[y],rs[x] = rs[y]; sz[x] = sz[y] + 1;

	if(l == r) return ;

	int mid = l + r >> 1;

	if(k <= mid) insert(ls[y],ls[x],l,mid,k);

	else insert(rs[y],rs[x],mid + 1, r,k);

}

int query(int x,int y,int l,int r,int L,int R) {

	if(l >= L && r <= R) return (sz[y] - sz[x] > 0);

	int mid = l + r >> 1;

	int res = 0;

	if(L <= mid) res |= query(ls[x],ls[y],l,mid,L,R);

	if(mid < R ) res |= query(rs[x],rs[y],mid + 1,r,L,R);

	return res;

}

int main() {

	n = read(),m = read();

	for(int i = 1;i <= n;++ i) {

		a[i] = read();

	 	insert(rt[i - 1],rt[i],0,(1 << 19) - 1,a[i]);

	}

	for(int i = 1;i <= m;++ i) {

		int x,b,l = 0,r = (1 << 19) - 1, ans = 0,L,R;

		x = read(),b = read(), L = read(),R = read();

		for(int i = 18;i >= 0; -- i) {

			int s = (x & (1 << i)) 	,mid = l + r >> 1;

			int tl = s ? l : mid + 1,tr = s ? mid : r ;

			if(query(rt[L - 1],rt[R],0,(1 << 19) - 1,std::max(tl - b,0),std::max(tr - b,0))) ans |= (1 << i), l = s ? l : mid + 1,r = s ? mid : r;

			else l = s ? mid + 1 : l,r = s ? r : mid;

		}

		printf("%d\n",ans);

	}

	return 0;

}