HackerRank HourRank 28 : C. Xorry Queries

こちらも気がつけばただの実装問題。
https://www.hackerrank.com/contests/hourrank-28/challenges/xorry-queries

問題

数列A[1..N]と整数pに対し、関数P(i)を以下のように定める。

• i+p-1がN以下ならP(i) = A[i] xor A[i+1] xor ... xor A[i+p-1]
• そうでないならP(i)=0

以下のクエリに順次答えよ。

• A[i]の1要素を変更し、入力値xをxor加算する
• L,Rに対しsum(P[L..R])を答えよ

解法

xorに関する問題なので、2進数表記の桁ごとに以下を考える。
桁ごとにP(i)における区間内のたっているビット数をカウントするSegtreeを作ろう。
範囲にxorを適用するのと、区間和を取る機能を持てばよい。

template<class V,int NV> class SegTree_3 {
public:
	vector<V> val, ma;
	SegTree_3(){
		int i;
		val.resize(NV*2,0); ma.resize(NV*2,0);
	};
	
	V getval(int x,int y,int l=0,int r=NV,int k=1) {
		if(x>=y) return 0;
		if(r<=x || y<=l) return 0;
		if(x<=l && r<=y) return ma[k];
		int num=getval(x,y,l,(l+r)/2,k*2)+getval(x,y,(l+r)/2,r,k*2+1);
		if(val[k]) num=(min(y,r)-max(x,l))-num;
		return num;
	}
	
	void update(int x,int y, V v,int l=0,int r=NV,int k=1) {
		if(l>=r) return;
		if(x<=l && r<=y) {
			val[k]^=1;
			ma[k]=(r-l)-ma[k];
		}
		else if(l < y && x < r) {
			update(x,y,v,l,(l+r)/2,k*2);
			update(x,y,v,(l+r)/2,r,k*2+1);
			
			ma[k]=ma[k*2]+ma[k*2+1];
			if(val[k]) ma[k]=(r-l)-ma[k];
		}
	}
};

SegTree_3<int,1<<17> st[18];
int N,M,P;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M>>P;
	FOR(i,N) {
		cin>>x;
		FOR(j,17) if(x&(1<<j)) st[j].update(max(0,i-P+1),i+1,1);
	}
	
	while(M--) {
		cin>>i>>x>>y;
		if(i==1) {
			FOR(j,17) if(y&(1<<j)) st[j].update(max(0,x-P),x,1);
		}
		else {
			ll ret=0;
			FOR(j,17) ret+=1LL*st[j].getval(x-1,min(N-P+1,y))<<j;
			cout<<ret<<endl;
		}
	}
	
	
}

まとめ

なんか無理やり作った感のある問題セットだ。