Codeforces #956 : Div2 F. array-value

こちらは本番中に解き切れず。
https://codeforces.com/contest/1983/problem/F

問題

整数列Aに対し、長さ2以上の部分列のスコアを、2要素のxorの最小値とする。
全部分列のスコアのうち、K番目に小さいものを求めよ。

解法

二分探索で解く。
今v以下のスコアがK通り以上あるか数え上げよう。
BinaryTrieを使い、整数値を入力すると、xorが所定の値以下になる最大のindexを答えるようなものを準備しよう。
f(i) := A[f(i)]～A[i]から2値取ると、xorをv以下にできるような最大のf(i)
とすると、f(i)=min(f(i-1), j) 、ただしjはA[i] xor A[j]がv以下となる最大のj、とできる。
jはBinaryTrieで求められる。

int T,N;
ll K;
ll A[101010];
int po;

struct BinarySumTrie {
	static BinarySumTrie nodes[8<<20];
	int nex[2];
	int v;
	BinarySumTrie() {
		nex[0]=nex[1]=-1;
		v=-1;
	}
	void add(int s,int val,int pos=29) {
		v=max(v,val);
		if(pos>=0) {
			int c=(s>>pos)&1;
			if(nex[c]==-1) nex[c]=po++;
			nodes[nex[c]].add(s,val,pos-1);
		}
	}
	int pick(int val,int t,int pos=29) { // sum [0,s-1]
		if(pos<0) return v;
		int ret=-1;
		int p=1<<pos;
		if((val&p)&&(t&p)) {
			if(nex[1]>=0) ret=max(ret,nodes[nex[1]].v);
			if(nex[0]>=0) ret=max(ret,nodes[nex[0]].pick(val^p,t,pos-1));
		}
		else if((val&p)) {
			if(nex[1]>=0) ret=max(ret,nodes[nex[1]].pick(val^p,t,pos-1));
		}
		else if(t&p) {
			if(nex[0]>=0) ret=max(ret,nodes[nex[0]].v);
			if(nex[1]>=0) ret=max(ret,nodes[nex[1]].pick(val^p,t,pos-1));
		}
		else {
			if(nex[0]>=0) ret=max(ret,nodes[nex[0]].pick(val^p,t,pos-1));
		}
		return ret;
	}
};
BinarySumTrie BinarySumTrie::nodes[8<<20];
int bst;
int R[101010];

ll num(int v) {
	ll sum=0;
	int i,j;
	int bst=po++;
	int lef=-1;
	FOR(i,N) {
		lef=max(lef,BinarySumTrie::nodes[bst].pick(A[i],v));
		sum+=lef+1;
		BinarySumTrie::nodes[bst].add(A[i],i);
	}
	return sum;
	
}


void solve() {
	int i,j,k,l,r,x,y; string s;

	cin>>T;
	while(T--) {
		cin>>N>>K;
		FOR(i,N) cin>>A[i];
		
		
		int ret=(1<<30)-1;
		for(i=29;i>=0;i--) {
			po=0;
			if(num(ret-(1<<i))>=K) ret-=(1<<i);
			FOR(j,po+1) {
				BinarySumTrie::nodes[j].nex[0]=BinarySumTrie::nodes[j].nex[1]=-1;
				BinarySumTrie::nodes[j].v=-1;
			}
		}
		cout<<ret<<endl;
	}
}

まとめ

これは思いつくべきだったな…。