【洛谷P5670】秘籍-反复异或
bitset，线段树
题目大意：
给定一个数列，有两个操作：
- 区间加上 $x$。
- 询问区间异或和的后 $m$ 个二进制位。
题解：
在我通过前，这题的正确代码都非常长而且思路比较复杂（也许）。这里说一种简单且易于理解的方法。
考虑到 $m$ 比较小，询问的时候又只考虑最后 $m$ 个二进制位，所以相当于对 $2^m$ 取模。所以数的种类只有 $2^m$ 种，是一个很小的范围。
异或运算是满足消去律的，所以如果一个数 $x$ 对答案产生了贡献，当且仅当它在区间中出现次数为奇数。
我们考虑用bitset维护一个数在一段区间中的出现次数。那么合并相邻两个区间的信息，只需要将两个bitset异或起来即可。
用线段树维护这些bitset，单次查询的时间复杂度为 $O(\frac{2^m}{\omega}\log n)$。
考虑对区间整体加上某个数对bitset的影响。那么，原来的第 $k$ 位的信息，现在对应的就是第 $(k+x)\bmod2^{m}$ 位的信息了。相当于整体左移了 $x$ 位，再把前面那些大于等于 $2^m$ 的右移 $2^m$ 位，并合并起来。当 $m=10$ 时，这里就可以写成b=(b<<x)|(b>>(1024-x))。
这里更新一个结点的信息是 $O(\frac{2^m}{\omega})$ 的，在线段树上区间修改时，单次复杂度还要乘上 $\log n$。区间修改打标记即可。
最后要得到答案，我们有了一个长度为 $2^m$ 的bitset，可以 $O(2^m)$ 判断并计算每位的贡献。
于是得到了一个时间复杂度 $O(\frac{2^m(n+q)\log n}{\omega}+2^mq)$，空间复杂度 $O(2^mn)$ 的算法。
其中，后面的 $O(2^mq)$ 的查询，可以通过预处理，然后手写bitset并每 $32$ 位一起求答案，这样可以优化到 $O(\frac{2^mq}{\omega})$。而 STL 的bitset没法直接提取多位信息（我不太会的说）。不过由于时间复杂度瓶颈不在这里，所以使用 STL 的效率也是可以接受的。
这样做的话，可能会因为常数问题而过不去。注意到当区间比较小的时候，区间里的数很少，此时使用bitset进行运算是非常不划算的，因此在区间比较小的时候，进行暴力修改和查询。
这样就可以通过了，代码长度为 $1.7\rm KB$ 左右。
Code：
#include<iostream>
#include<bitset>
using namespace std;
typedef bitset<1024>BitSet;
const int N=1e5+6;
BitSet d[N];int tg[N],n,m,q,a[N];
void build(int l,int r,int o){
if(r-l+1<=64){
for(register int i=l;i<=r;++i)cin>>a[i],d[o].flip(a[i]);
}else{
const int mid=l+r>>1;
build(l,mid,o<<1),build(mid+1,r,o<<1|1);
d[o]=d[o<<1]^d[o<<1|1];
}
}
inline void pushdown(int o){
int&x=tg[o];
d[o<<1]=(d[o<<1]<<x)|(d[o<<1]>>(1024-x));
d[o<<1|1]=(d[o<<1|1]<<x)|(d[o<<1|1]>>(1024-x));
(tg[o<<1]+=x)&=1023,(tg[o<<1|1]+=x)&=1023;
x=0;
}
void modify(int l,int r,int o,const int&L,const int&R,const int&x){
if(r-l+1<=64){
const int lx=max(l,L),rx=min(r,R);
for(register int i=lx;i<=rx;++i)d[o].flip((a[i]+tg[o])&1023),d[o].flip((tg[o]+((a[i]+=x)&=1023))&1023);
}else
if(L<=l&&r<=R){
d[o]=(d[o]<<x)|(d[o]>>(1024-x));
(tg[o]+=x)&=1023;
}else{
if(tg[o])pushdown(o);
const int mid=l+r>>1;
if(L<=mid)modify(l,mid,o<<1,L,R,x);
if(mid<R)modify(mid+1,r,o<<1|1,L,R,x);
d[o]=d[o<<1]^d[o<<1|1];
}
}
void query(int l,int r,int o,const int&L,const int&R,BitSet&b){
if(r-l+1<=64){
const int lx=max(l,L),rx=min(r,R);
for(register int i=lx;i<=rx;++i)b.flip((a[i]+tg[o])&1023);
}else
if(L<=l&&r<=R)b^=d[o];else{
if(tg[o])pushdown(o);
const int mid=l+r>>1;
if(L<=mid)query(l,mid,o<<1,L,R,b);
if(mid<R)query(mid+1,r,o<<1|1,L,R,b);
}
}
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>n>>m>>q;
build(1,n,1);
while(q--){
int l,r,op,x;
cin>>op>>l>>r;
if(op==1){
cin>>x;
modify(1,n,1,l,r,x);
}else{
static BitSet b;
b.reset();
query(1,n,1,l,r,b);
int ans=0;
for(register int i=0;i<1024;++i)
ans^=b[i]*i;
ans&=(1<<m)-1;
cout<<ans<<'\n';
}
}
return 0;
}