题目链接：https://www.nowcoder.com/acm/contest/211/E
题目描述
请实现一个数据结构支持以下操作：区间循环左右移，区间与，区间或，区间求和。
输入描述:
第一行n,q表示数列长度及操作次数。
第二行n个数表示初始序列。
接下来q行表示操作。
操作格式如下：
一行表示一个操作。所有操作形如 opt l r v。
opt=1 表示将区间[l,r]循环右移v位。
opt=2 表示将区间[l,r]循环左移v位。
opt=3 表示将区间[l,r]按位或上v。
opt=4 表示将区间[l,r]按位与上v。
opt=5 询问区间[l,r]的和。
保证opt=1或2时 1 ≤ v ≤ 20
注意：为了优化你的做题体验，操作5也会输入一个v，但是是没有意义的。
注意：循环左右移在20个二进制位的意义下进行
输出描述:
对于每个opt=5的操作，输出一个数表示答案。
输入
10 10
10112 23536 1305 7072 12730 29518 12315 3459 12435 29055
4 5 10 12373
2 1 6 7
5 4 10 24895
1 1 4 8
5 3 7 7767
5 7 9 6127
4 2 8 30971
5 4 10 2663
1 7 10 1
1 2 9 5
输出
2001530
1600111
24611
49482
备注:
1 ≤ N,Q ≤ 2*10^5 且 0 ≤ ai < 2^20
一些说明：
1. 对于00000000000000000101，右移一位后会变成10000000000000000010
2. 不是区间位移，是区间中的每一个数的二进制位的位移
题解：
（说实话这道题其实不难的，会线段树就应该想到怎么做的，可能是我脑子太笨了吧，比赛的时候想不到怎么做。）
考虑到只有二进制下只有 $20$ 位，而且修改操作都是按位与或者按位或，所以可以将 $20$ 位拆开来看。
然后就简单了呀：
对 $01$ 序列中某一个区间，全部与上 $x(x=0,1)$，那么 $x = 1$ 时不变， $x = 0$ 时全 $0$。
对 $01$ 序列中某一个区间，全部或上 $x(x=0,1)$，那么 $x = 0$ 时不变， $x = 1$ 时全 $1$。（这两种操作可以归结为直接把一个常见的线段树区间覆盖操作）
循环平移就是在 $20$ 棵平衡树进行数据的循环平移，向左向右循环平移都可以全部归结为向右平移，范围为 $(0,19)$，这个就是把每个线段树节点里的二十位的01序列重新排一下即可。
求和，我们线段树每个节点都有一个 $val[20]$ 用以为维护某一位上，当前区间内所有数字在这一位上合起来总共出现了多少个 $1$，也就是说这个 $val[20]$ 相当于一个算加法但还没来得及进位的二进制数，这样的二进制数转成十进制和普通二进制数转十进制是一样的。
AC代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=2e5+; int n,q,a[maxn]; /********************************* Segment Tree - st *********************************/
int tmp[];
struct Node{
int l,r;
int val[];
int lazy[],shft;
void upd_shft(int x)
{
x=(x+)%;
shft=(shft+x)%;
for(int i=;i<x;i++) tmp[i]=lazy[i];
for(int i=;i<-x;i++) lazy[i]=lazy[i+x];
for(int i=;i<x;i++) lazy[i+-x]=tmp[i]; for(int i=;i<x;i++) tmp[i]=val[i];
for(int i=;i<-x;i++) val[i]=val[i+x];
for(int i=;i<x;i++) val[i+-x]=tmp[i];
}
void upd_lazy(int i,int x)
{
val[i]=(r-l+)*x;
lazy[i]=x;
}
}node[*maxn];
void pushdown(int root)
{
if(node[root].shft)
{
node[root*].upd_shft(node[root].shft);
node[root*+].upd_shft(node[root].shft);
node[root].shft=;
}
for(int i=;i<;i++)
{
if(node[root].lazy[i]!=-)
{
node[root*].upd_lazy(i,node[root].lazy[i]);
node[root*+].upd_lazy(i,node[root].lazy[i]);
node[root].lazy[i]=-;
}
}
}
void pushup(int root)
{
for(int i=;i<;i++)
node[root].val[i]=node[root*].val[i]+node[root*+].val[i];
}
void build(int root,int l,int r)
{
if(l>r) return;
node[root].l=l, node[root].r=r;
node[root].shft=;
for(int i=;i<;i++) node[root].lazy[i]=-;
if(l==r)
{
for(int i=;i<;i++)
node[root].val[i]=(a[l]>>i)%;
}
else
{
int mid=(l+r)/;
build(root*,l,mid);
build(root*+,mid+,r);
pushup(root);
}
}
void update(int type,int root,int st,int ed,int x)
{
if(st<=node[root].l && node[root].r<=ed)
{
if(type==)
{
node[root].upd_shft(x);
}
if(type==)
{
for(int i=,k;i<;i++)
{
k=(x>>i)%;
if(!k) node[root].upd_lazy(i,);
}
}
if(type==)
{
for(int i=,k;i<;i++)
{
k=(x>>i)%;
if(k) node[root].upd_lazy(i,);
}
}
}
else
{
int mid=(node[root].l+node[root].r)/;
pushdown(root);
if(st<=mid) update(type,root*,st,ed,x);
if(ed>mid) update(type,root*+,st,ed,x);
pushup(root);
}
}
ll query(int root,int st,int ed)
{
if(st<=node[root].l && node[root].r<=ed)
{
ll res=;
for(int i=;i<;i++) res+=(ll)node[root].val[i]*(<<i);
return res;
}
pushdown(root);
int mid=(node[root].l+node[root].r)/;
ll res=;
if(st<=mid) res+=query(root*,st,ed);
if(ed>mid) res+=query(root*+,st,ed);
return res;
}
/********************************* Segment Tree - ed *********************************/ int main()
{
scanf("%d%d",&n,&q);
for(int i=;i<=n;i++) scanf("%d",&a[i]);
build(,,n);
while(q--)
{
int op,l,r,v;
scanf("%d%d%d%d",&op,&l,&r,&v);
if(op==) update(,,l,r,v);
if(op==) update(,,l,r,-v);
if(op==) update(,,l,r,v);
if(op==) update(,,l,r,v);
if(op==) printf("%lld\n",query(,l,r));
}
}