解题思路
巧妙的数据结构题,非常巧妙的利用的线段树的奇妙性质。
操作逐条维护:
Replace
: 直接线段树上单点修改;Sum
:线段树查询区间和;Reverse
:考虑线段树的形态。线段树第 \(i\) 层(除最后一层)有 \(2^{i-1}\) 个节点,那么将所有 \(i\ge 1\) 的区间 \([(i-1)\times 2^k,i\times 2^k]\) 翻转,可以看作将线段树每一层均翻转一次。考虑用一个标记来表示每一层是否被翻转,因为翻转两次后相当于没有翻转,那么直接使用异或来维护即可,即每一次翻转操作让每一层的标记异或 \(1\);Swap
:观察两个被交换的区间,肉眼可见在除以 \(2\) 之后就变成了一个 \([(i-1)\times 2^k,i\times 2^k]\) 的区间,而两个区间刚好各占一半。由于题目中唯一的查询操作是查询区间和,那么交换操作和翻转操作是等价的,那么直接修改第 \(k+1\) 层的标记即可。
需要注意的是,在这种维护层的顺序下,区间 \([1,2^n]\) 实际上是位于第 \(n\) 层的,然后不要忘了开 long long。
AC 代码
#include<stdio.h>
#include<stdlib.h>
#define int long long
#define N (1<<18)+5
int n,q,a[N],Mark[N];
int tree[N<<1];
#define l(x) (x<<1)
#define r(x) ((x<<1)|1)
#define mid ((l+r)>>1)
inline void Push_Up(int now){
tree[now]=
tree[l(now)]+
tree[r(now)];
}
inline void Update(int now,int l,int r,int p,int v,int depth){
if(p>r||p<l) return;
if(l==r){
tree[now]=v;
return;
}
if(Mark[depth]){
Update(l(now),mid+1,r,p,v,depth-1);
Update(r(now),l,mid,p,v,depth-1);
}else{
Update(l(now),l,mid,p,v,depth-1);
Update(r(now),mid+1,r,p,v,depth-1);
}Push_Up(now);
}
inline int Query(int now,int l,int r,int L,int R,int depth){
if(L>r||R<l) return 0;
if(L<=l&&r<=R)
return tree[now];
int Lans,Rans;
if(Mark[depth]){
Lans=Query(l(now),mid+1,r,L,R,depth-1);
Rans=Query(r(now),l,mid,L,R,depth-1);
}else{
Lans=Query(l(now),l,mid,L,R,depth-1);
Rans=Query(r(now),mid+1,r,L,R,depth-1);
}return Lans+Rans;
}
signed main(){
scanf("%lld%lld",&n,&q);
for(register int i=1;i<=1<<n;++i)
scanf("%lld",&a[i]);
for(register int i=1;i<=1<<n;++i)
Update(1,1,1<<n,i,a[i],n);
int opt,x,k;while(q--){
scanf("%lld",&opt);
switch (opt){
case 1:{
scanf("%lld",&x);
scanf("%lld",&k);
Update(1,1,1<<n,x,k,n);
break;
}
case 2:{
scanf("%lld",&k);
for(register int i=0;i<=k;++i)
Mark[i]^=1;break;
}
case 3:{
scanf("%lld",&k);
Mark[k+1]^=1;
break;
}
default:{
scanf("%lld",&x); scanf("%lld",&k);
printf("%lld\n",Query(1,1,1<<n,x,k,n));
break;
}
}
}
}
标签:CF1401F,Reverse,int,题解,线段,long,times,now,翻转
From: https://www.cnblogs.com/UncleSamDied6/p/18010660