题目看着很方啊，难道要树套树？
但数据范围提醒我们，是nlogn的复杂度
Sort(S)的定义是不是很鬼畜
但我们不动脑子的打表容易发现
连续区间[1，n]内为连续的奇数
（其实这里直接用初中的完全平方公式就好）
我们再次打表又发现了
连续的奇数的异或和，很有规律的嘛
可以直接O（1）求出

根据异或的性质(a^a=0)
我们就能计算出任意连续一段的ans了，^
虽说允许重复的集合S
但区间如果重叠，他也只计算一次答案，手玩一下很容易看出
也就是集合S还是不允许重复的(重复的删掉是不影响答案的)
合并直接算就好了
我们现在需要一个只需要支持区间更改贡献的数据结构
lsh+线段树真香

ps：可能我的线段树调试的时候打了太多补丁，肯定有比我写的好得多的代码
但也是不难理解的，重要部分我们加以注释
关于int，是会炸的，反正我的数据灰渣
另外提醒
千万别开小了数组,一组询问是两个数偶，我一直报WA