kmjp's blog

競技プログラミング参加記です

Codeforces #665 Div2 F. Reverse and Swap

面倒なだけで面白くはないなぁ…。
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;
		}
	}
}

まとめ

まぁ解法は割と自明だし、本番中に解く人も多いよね。