Codeforces #845 : Div2 F. Comfortably Numb

問題文が短い。
https://codeforces.com/contest/1777/problem/F

問題

N要素の整数列Aが与えられる。
Aの部分列A[L,R]の評価値は、max(A[L,R]) xor A[L] xor A[L+1] xor ... xor A[R]とする。
全部分列の取り方に対し、評価値の最大値を求めよ。

解法

部分列の最大値を小さい順に見ていく。
今L≦M≦Rに対し、A[L-1]＞A[M]かつA[M]＜A[R+1]かつA[M]=max(A[L..R])とする。
この時、L,M,Rの大小関係に基づき、M-L＜R-Mなら左端、逆なら右端を総当たりしよう。
その際、反対側の端はBinaryTrieを使い、最大値を求めて行く。

区間内のprefix xorの値を格納したBinaryTrieはマージテクの要領でマージしていこう。

int T,N,A[202020];
int S[202020];
ll ret=0;

struct BinarySumTrie {
	BinarySumTrie *nex[2];
	BinarySumTrie() {
		nex[0]=nex[1]=NULL;
	}
	void add(ll s,int pos=29) {
		if(pos>=0) {
			int c=(s>>pos)&1;
			if(!nex[c]) nex[c]=new BinarySumTrie();
			nex[c]->add(s,pos-1);
		}
	}
	ll pick(ll val,int pos=29) { // sum [0,s-1]
		if(pos<0) return 0;
		
		int tar=0;
		if(!(val&(1LL<<pos))) {
			if(nex[1]) tar=1;
			else tar=0;
		}
		else {
			if(nex[0]) tar=0;
			else tar=1;
		}
		return (tar<<pos)+nex[tar]->pick(val,pos-1);
	}
	void del() {
		if(nex[0]) {
			nex[0]->del();
			delete nex[0];
		}
		if(nex[1]) {
			nex[1]->del();
			delete nex[1];
		}
	}
};

BinarySumTrie* bst[202020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N;
		vector<pair<int,int>> V;
		set<pair<int,int>> D;
		FOR(i,N+2) {
			if(bst[i]) {
				bst[i]->del();
				delete bst[i];
				bst[i]=NULL;
			}
		}
			
		FOR(i,N) {
			cin>>A[i+1];
			S[i+1]=S[i]^A[i+1];
			V.push_back({A[i+1],i+1});
		}
		D.insert({0,0});
		D.insert({N+1,N+1});
		
		bst[0]=new BinarySumTrie();
		bst[N+1]=new BinarySumTrie();
		bst[0]->add(0);
		bst[N+1]->add(S[N]);
		
		ll ma=0;
		sort(ALL(V));
		FORR2(v,i,V) {
			pair<int,int> L={-1,-1},R={-1,-1};
			auto it=D.lower_bound({i+1,i+1});
			if(it->first==i+1) {
				R=*it;
			}
			it--;
			if(it->second==i-1) {
				L=*it;
			}
			if(L.first==-1&&R.first==-1) {
				bst[i]=new BinarySumTrie();
				bst[i]->add(S[i]);
				bst[i]->add(S[i-1]);
				D.insert({i,i});
			}
			else if(L.first==-1) {
				D.erase(R);
				D.insert({i,R.second});
				ma=max(ma,S[i-1]^A[i]^bst[R.first]->pick(S[i-1]^A[i]));
				swap(bst[i],bst[i+1]);
				bst[i]->add(S[i-1]);
			}
			else if(R.first==-1) {
				D.erase(L);
				D.insert({L.first,i});
				ma=max(ma,S[i]^A[i]^bst[L.first]->pick(S[i]^A[i]));
				bst[L.first]->add(S[i]);
			}
			else {
				D.erase(L);
				D.erase(R);
				D.insert({L.first,R.second});
				if(i-L.first<R.second-i) {
					for(j=max(0,L.first-1);j<i;j++) ma=max(ma,S[j]^A[i]^bst[R.first]->pick(S[j]^A[i]));
					for(j=max(0,L.first-1);j<i;j++) bst[R.first]->add(S[j]);
					swap(bst[L.first],bst[R.first]);
				}
				else {
					for(j=i;j<=min(N,R.second);j++) ma=max(ma,S[j]^A[i]^bst[L.first]->pick(S[j]^A[i]));
					for(j=i;j<=min(N,R.second);j++) bst[L.first]->add(S[j]);
				}
				bst[R.first]->del();
				delete bst[R.first];
				bst[R.first]=NULL;
			}
		}
		cout<<ma<<endl;
		
	}
}

まとめ

考え方はそこまで難しくないものの、ちょっと面倒くさい。