非常好的一道题
起初没看数据范围，以为是类似于区间的子区间性质的问题，口胡了一个扫描线+主席树的做法，然后发现要重排
首先读题，要重排后为回文串
然后发现数据范围很小，考虑根号算法。发现对于一个回文串，区间里的数要么都出现两次，要么有一个出现一次。这很类似于异或操作
于是我们考虑先对数状压一下，然后做一个前缀异或，则对于询问区间 \([x,y]\) 可以表示成找有多少个二元组 \((i,j)\) 满足 \(i,j \in [x-1,y],i < j,a_i \oplus a_j=2^k\ or\ a_i \oplus a_j=0\) ，这个就可以很方便的莫队啦
最终复杂度 \(O(Dn \sqrt n)\) ，其中 \(D = 26\)
标签：一天,异或,美好,P3604,重排,区间,oplus,回文 From： https://www.cnblogs.com/fox-konata/p/17761690.html