描述 请你维护一个线段树【线段树|[线段树]区间and or xor】样例输入
支持一下操作
A x l r 区间 and x
O x l r区间 Or x
X x l r 区间 Xor x
S l r 区间求和
输入 一个数 T表示数据组数 一个数n表示初始序列长 m表示查询 随后n个整数 接下来m次询问 如上
输出 S次询问的答案
1
4 1
1 2 4 7
S 0 2
样例输出
7
提示
为防止min-max剪枝 n=1e6 m=1e5 Ai<15 T<=3
分析：
因为Ai<15 所以可以把数拆成4个二进制位来做，然后就是简单的区间覆盖和区间翻转了
注意区间翻转时要一并把覆盖标记翻转，本人在此WA无数
代码：
#include
#define N 1000005
#define lc (p<<1)
#define rc (p<<1|1)
#define mid (tr[p][wei].l+tr[p][wei].r>>1)
using namespace std;
inline int read(){
int ans=0;
char ch=getchar();
while(!isdigit(ch))ch=getchar();
while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
return ans;
}
int tr_tr,n,m,a[N];
struct Node{int l,r,sum,tag;
}tr[N<<2][4];
inline void pushup(int p,int wei){tr[p][wei].sum=tr[lc][wei].sum+tr[rc][wei].sum;
}
inline void pushnow(int p,int wei,int k){
if(k<2)tr[p][wei].tag=k,tr[p][wei].sum=(tr[p][wei].r-tr[p][wei].l+1)*k;
else{
if(tr[p][wei].tag<2)tr[p][wei].tag^=1,tr[p][wei].sum=(tr[p][wei].r-tr[p][wei].l+1)*tr[p][wei].tag;
else if(tr[p][wei].tag==2)tr[p][wei].tag=3,tr[p][wei].sum=tr[p][wei].r-tr[p][wei].l+1-tr[p][wei].sum;
else tr[p][wei].tag=2,tr[p][wei].sum=tr[p][wei].r-tr[p][wei].l+1-tr[p][wei].sum;
}
}
inline void pushdown(int p,int wei){if(tr[p][wei].tag!=3)pushnow(lc,wei,tr[p][wei].tag),pushnow(rc,wei,tr[p][wei].tag),tr[p][wei].tag=3;
}
inline void build(int p,int l,int r,int wei){
tr[p][wei].l=l,tr[p][wei].r=r,tr[p][wei].tag=3;
if(l==r){tr[p][wei].sum=(a[l]&(1<>wei;
return;
}
build(lc,l,mid,wei),build(rc,mid+1,r,wei),pushup(p,wei);
}
inline void update(int p,int ql,int qr,int wei,int k){
if(ql>tr[p][wei].r||qrmid)update(rc,ql,qr,wei,k);
else update(lc,ql,mid,wei,k),update(rc,mid+1,qr,wei,k);
pushup(p,wei);
}
inline int query(int p,int ql,int qr,int wei){
if(ql>tr[p][wei].r||qrmid)return query(rc,ql,qr,wei);
return query(lc,ql,mid,wei)+query(rc,mid+1,qr,wei);
}
int main(){
tr_tr=read();
while(tr_tr--){
n=read(),m=read();
for(int i=1;
i<=n;
++i)a[i]=read();
for(int i=0;
i<4;
++i)build(1,1,n,i);
while(m--){
char s[4];
scanf("%s",s);
if(s[0]=='S'){
int l=read()+1,r=read()+1;
int ans=0;
for(int i=0;
i<4;
++i)ans+=query(1,l,r,i)< 推荐阅读
- 线段树|[类欧几里得算法 线段树] BZOJ 1938 [CROATIAN2010] ALADIN
- 牛客 C. 子段乘积（线段树）
- 牛客挑战赛39 C 牛牛的等差数列（线段树）（*）
- 牛客 数据结构（区间修改+求区间元素平方和）
- 校门外的树 线段树版
- 树链剖分|牛客练习赛51 F-ABCBA（树链剖分，线段树，状态转移）
- 数论|bzoj 1938 - 类欧几里得+线段树
- 线段树|FZU - 2277(树链剖分或dfs序+线段树)
- 并查集|[CF938G] Shortest Path Queries
- 牛客网 练习赛25 B最长区间