面倒なだけで面白くはないなぁ…。
https://codeforces.com/contest/1401/problem/F
問題
長さ2^Nの数列Aが与えられる。
以下のクエリに順次答えよ。
- 指定された1要素の値を更新する
- 区間[i*2^k+1,(i+1)*2^k]の間の要素を反転する
- 区間[(2i)*2^k+1,(2i+1)*2^k]と[(2i+1)*2^k+1,(2i+2)*2^k]の間の要素をswapする
- 区間[L,R]の要素の総和を答える
解法
区間の総和を求めるSegTreeの各ノードについて、下位の要素を参照する際にswap/reverseの有無を管理しておき、それらをもちいて総和を求める。
int R[19]; int S[19]; template<class V,int NV> class SegTree_3 { public: vector<V> val; SegTree_3(){ int i; val.resize(NV*2,0); }; V getval(int x,int y,int l=0,int r=NV,int k=1,int step=18) { if(y<x) return 0; if(r<=x || y<l) return 0; if(x<=l && r-1<=y) return val[k]; assert(step>0); x=max(x,l); y=min(y,r-1); if(step && R[step]) { x^=(1<<step)-1; y^=(1<<step)-1; swap(x,y); } if(S[step-1]) { x^=1<<(step-1); y^=1<<(step-1); } if(x<=y) { return getval(x,y,l,(l+r)/2,k*2,step-1)+getval(x,y,(l+r)/2,r,k*2+1,step-1); } else { return val[k]-getval(y+1,(l+r)/2-1,l,(l+r)/2,k*2,step-1)-getval((l+r)/2,x-1,(l+r)/2,r,k*2+1,step-1); } } void update(int x,V v,int l=0,int r=NV,int k=1,int step=18) { if(step==0) { val[k]=v; } else { if(R[step]) x^=(1<<step)-1; if(S[step-1]) x^=1<<(step-1); if(x<(l+r)/2) update(x,v,l,(l+r)/2,k*2,step-1); else update(x,v,(l+r)/2,r,k*2+1,step-1); val[k]=val[k*2]+val[k*2+1]; } } }; int N,Q; SegTree_3<ll,1<<18> st; void solve() { int i,j,k,l,r,x,y; string s; scanf("%d%d",&N,&Q); FOR(i,1<<N) { scanf("%d",&x); st.update(i,x); } while(Q--) { scanf("%d",&i); if(i==1) { scanf("%d%d",&x,&k); x--; st.update(x,k); } else if(i==2) { scanf("%d",&x); R[x]^=1; } else if(i==3) { scanf("%d",&x); S[x]^=1; } else { scanf("%d%d",&x,&y); cout<<st.getval(x-1,y-1)<<endl; } } }
まとめ
まぁ解法は割と自明だし、本番中に解く人も多いよね。