[bzoj4571]-[SCOI2016]美味

主席树是个厉害玩意儿……

题目(BZOJ)

题目(洛谷)

 

来说说这题吧~

首先题目是要求异或和最大,然后再看数据范围:都是1e5以内,由于(1<<17)=131,072明显大于1e5,又没有修改操作,所以我们考虑贪心来求。

前面的b是给定的,我们来考虑后面的式子:aj+x

我们从高到低贪心二进制每一位,看这一位异或上b在[l,r]内能否为1,也就是说看在[l,r]内是否存在(aj+x)的这一位与b的这一位不相等。

所以,我们可以对[0,(1<<18)-1]建一棵权值线段树(注意可能这17位上每一位都为1),这棵线段树用来维护aj(x每次给定,可以不维护),在值域[max(0,ans-x), ans+(1<<i)-1-x]上查找该数即可。

考虑差分,查找[l,r]内是否存在就是看sum[r]-sum[l-1]是否等于0,如果不等于就说明找到了,等于就说明这个区间内没有这个数。

这个用主席树就可以解决。

 

发表评论