2020-2021:teams:legal_string:jxm2001:contest:cf_665_div._2
| 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:legal_string:jxm2001:contest:cf_665_div._2 [2020/08/22 10:36] jxm2001 创建 |
2020-2021:teams:legal_string:jxm2001:contest:cf_665_div._2 [2020/08/23 11:58] (当前版本) jxm2001 |
||
|---|---|---|---|
| 行 75: | 行 75: | ||
| </hidden> | </hidden> | ||
| + | ===== F. Reverse and Swap ===== | ||
| + | ==== 题意 ==== | ||
| + | |||
| + | 给定一个长度为 $2^n$ 的序列 $\{a\}$，接下来 $q$ 次操作： | ||
| + | |||
| + | - 将 $a_x$ 的值修改为 $k$ | ||
| + | - 将所有 $[(i-1)2^k+1,i2^k]$ 区间翻转 | ||
| + | - 将所有 $[(2i-2)2^k+1,(2i-1)2^k]$ 区间与 $[(2i-1)2^k+1,(2i)2^k]$ 区间交换 | ||
| + | - 询问 $[l,r]$ 区间的和 | ||
| + | |||
| + | ==== 题解 ==== | ||
| + | |||
| + | 将 $\{a\}$ 下标改为从零开始。不难发现操作 $2$ 相当于将 $a_x$ 变为 $a_{x\oplus (2^k-1)}$，操作 $3$ 相当于将 $a_x$ 变为 $a_{x\oplus 2^k}$。 | ||
| + | |||
| + | 于是对于操作 $2$ 和操作 $3$，只需要维护最终下标的异或值 $\text{val}$ 即可，对于操作 $1$，只需要修改 $a_{x\oplus \text{val}}$ 即可。 | ||
| + | |||
| + | 对于操作 $4$，不妨先将查询区间分割为若干段形如 $[M2^k,M2^k+2^k-1]$ 的区间。 | ||
| + | |||
| + | 不难发现 $[0,2^k-1]$ 区间异或 $\text{val}\And (2^k-1)$ 后仍然遍历 $[0,2^k-1]$。 | ||
| + | |||
| + | 于是 $[M2^k,M2^k+2^k-1]$ 异或 $\text{val}$ 后变为 $[M2^k\oplus (\text{val} \And\text{~} (2^k-1)),M2^k\oplus (\text{val} \And\text{~} (2^k-1))+2^k-1]$，考虑线段树查询即可。 | ||
| + | |||
| + | 总时间复杂度 $O(2^n+nq)$。 | ||
| + | |||
| + | <hidden 查看代码> | ||
| + | <code cpp> | ||
| + | const int MAXN=1<<18; | ||
| + | int a[MAXN],val; | ||
| + | LL s[MAXN<<2]; | ||
| + | void build(int k,int L,int R){ | ||
| + | int M=L+R>>1; | ||
| + | if(L==R)return s[k]=a[M],void(); | ||
| + | build(k<<1,L,M);build(k<<1|1,M+1,R); | ||
| + | s[k]=s[k<<1]+s[k<<1|1]; | ||
| + | } | ||
| + | void update(int k,int L,int R,int pos,int v){ | ||
| + | if(L==R)return s[k]=v,void(); | ||
| + | int M=L+R>>1; | ||
| + | if(M>=pos)update(k<<1,L,M,pos,v); | ||
| + | else update(k<<1|1,M+1,R,pos,v); | ||
| + | s[k]=s[k<<1]+s[k<<1|1]; | ||
| + | } | ||
| + | LL query(int k,int L,int R,int ql,int qr,int pos){ | ||
| + | if(ql<=L&&R<=qr)return s[k]; | ||
| + | int M=L+R>>1,dir=(val>>pos)&1; | ||
| + | if(M>=qr)return query((k<<1)^dir,L,M,ql,qr,pos-1); | ||
| + | else if(M<ql)return query((k<<1|1)^dir,M+1,R,ql,qr,pos-1); | ||
| + | else return query((k<<1)^dir,L,M,ql,qr,pos-1)+query((k<<1|1)^dir,M+1,R,ql,qr,pos-1); | ||
| + | } | ||
| + | int main() | ||
| + | { | ||
| + | int n=read_int(),q=read_int(),m=1<<n; | ||
| + | _for(i,0,m)a[i]=read_int(); | ||
| + | build(1,0,m-1); | ||
| + | while(q--){ | ||
| + | int opt=read_int(),x=read_int(); | ||
| + | if(opt==1) | ||
| + | update(1,0,m-1,(x-1)^val,read_int()); | ||
| + | else if(opt==2) | ||
| + | val^=(1<<x)-1; | ||
| + | else if(opt==3) | ||
| + | val^=1<<x; | ||
| + | else | ||
| + | enter(query(1,0,m-1,x-1,read_int()-1,n-1)); | ||
| + | } | ||
| + | return 0; | ||
| + | } | ||
| + | </code> | ||
| + | </hidden> | ||
2020-2021/teams/legal_string/jxm2001/contest/cf_665_div._2.1598063818.txt.gz · 最后更改: 2020/08/22 10:36 由 jxm2001
