begin.lydsy.com/JudgeOnline/upload/201805.pdf 

mdzz真是气疯了 一开写的时候还想 有没有可能全部数字都是出现奇数次啊 那怎么没让我输出-1啊 claris 一定是非常好让我们少麻烦

md然后调试了几个小时 如果都没有说明答案是2e5+1

考虑如何快速判断异或 我们可以unsigned long long随便随机一些数字 然后假设为x1,x2,x3

那么他们异或出来的数基本都是独一无二的所以我们可以考虑在主席数上的区间把这些值记录下来 那么我就可以用这些值快速判断一个区间内是否所有的数都出现了奇数次 只需要主席树建立根到这个节点的信息 然后 用lca fa[lca],x,y互相异或下出结果即可

 

分类: 主席树

elijahqi

辣鸡蒟蒻一枚qwq 欢迎加qq qwq 2922945330

发表评论