Mail.Ru Cup 2018 Round 1 : D. Changing Array

いまいち自信なかったけど通った。
http://codeforces.com/contest/1054/problem/D

問題

2進数でK桁以下の整数からなるN要素の整数列A[i]が与えられる。
一部の要素を、K桁全要素01反転することができるとする。
この時、Aの連続部分列のうち、xorを取ったものが非0になる数を最大化せよ。

解法

01反転が無い場合、良くある累積和のmapを使い同じ累積和になる場所の数を求めれば0になる数を高速に求められる。
この要領を少し変更し、要素を順に見ていって、01反転した場合としない場合どちらの方がその要素を終端とする部分列のうち条件を満たす数が多いか試して、多い方を取ればよい。

int N,K,NK;
int A[202020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K;
	NK=(1<<K)-1;
	
	ll tot=0;
	int cur=0;
	map<int,ll> M;
	M[0]=1;
	FOR(i,N) {
		cin>>x;
		if(M[cur^x]<M[cur^x^NK]) {
			cur^=x;
		}
		else {
			cur^=x^NK;
		}
		tot+=(i+1)-M[cur];
		M[cur]++;
	}
	cout<<tot<<endl;
}

まとめ

本番このアプローチで正しさを検証することなく通してしまった。