Xor

xor.cpp

// Ivan Carvalho
// Xor - Seletiva IOI - OBI 2016
// O(n*log(MAXV))
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 3*1e5 + 10;
const int MAXL = 30;

typedef pair<int,int> ii;
typedef tuple<int,int,int> trinca;

vector<trinca> sweep;
vector<ii> val;
vector<int> esq,dir;
int L[MAXN],R[MAXN],V[MAXN],raiz[MAXN],N,K,segPtr;

struct Trie{
	
	Trie* filho[2];
	int maximo,minimo;
	
	Trie(){
		filho[0] = NULL;
		filho[1] = NULL;
		maximo = 0;
		minimo = MAXN;	
	}
	
};

int get_min(Trie* t){
	return t ? t->minimo : MAXN;
}

int get_max(Trie* t){
	return t ? t->maximo : 0;
}

void add(Trie* t,int numero,int posicao){
	
	for(int i = MAXL;i>=0;i--){
		
		int digito = 0;
		if((1 << i) & numero) digito = 1;
		
		if(t->filho[digito]){
			t = t->filho[digito];	
		}
		else{
			t->filho[digito] = new Trie();
			t = t->filho[digito];
		}
		
		t->maximo = max(t->maximo,posicao);
		t->minimo = min(t->minimo,posicao);
		
	}
	
}

int query_max(Trie* t,int numero){
	
	int ans = 0;
	
	for(int i = MAXL;i>=0;i--){
		
		int digito = 0,digitok = 0;
		if((1 << i) & numero) digito = 1;
		if((1 << i) & K) digitok = 1;
		
		if(digitok == 1){
			
			ans = max(ans,get_max(t->filho[digito]));
			if(t->filho[digito ^ 1]) t = t->filho[digito ^ 1];
			else break;
			
		}
		else{
			
			if(t->filho[digito]) t = t->filho[digito];
			else break;
			
		}
		
	}
	
	return ans;
	
}

int query_min(Trie* t,int numero){
	
	int ans = MAXN;
	
	for(int i = MAXL;i>=0;i--){
		
		int digito = 0,digitok = 0;
		if((1 << i) & numero) digito = 1;
		if((1 << i) & K) digitok = 1;
		
		if(digitok == 1){
			
			ans = min(ans,get_min(t->filho[digito]));
			if(t->filho[digito ^ 1]) t = t->filho[digito ^ 1];
			else break;
			
		}
		else{
			
			if(t->filho[digito]) t = t->filho[digito];
			else break;
			
		}
		
	}
	
	return ans;
	
}

void utilidade(){
	val.push_back(ii(0,0));
	esq.push_back(0);
	dir.push_back(0);
}

void update(int novo,int velho,int left,int right,int x,ii davez){
	
	val[novo] = max(val[velho],davez);
	esq[novo] = esq[velho];
	dir[novo] = dir[velho];
	
	if(left == right) return;
	
	int mid = (left+right)/2;
	
	if(x <= mid){
		utilidade();
		esq[novo] = ++segPtr;
		update(esq[novo],esq[velho],left,mid,x,davez);
	}
	else{
		utilidade();
		dir[novo] = ++segPtr;
		update(dir[novo],dir[velho],mid+1,right,x,davez);
	}
	
}

ii query(int pos,int left,int right,int i,int j){
	
	if(left >= i && right <= j) return val[pos];
	
	int mid = (left+right)/2;
	if(j <= mid) return query(esq[pos],left,mid,i,j);
	else if(i >= mid + 1) return query(dir[pos],mid+1,right,i,j);
	else return max(query(esq[pos],left,mid,i,j),query(dir[pos],mid+1,right,i,j));
	
}

int solve(int s,int e){
	
	if(s > e) return 0;
	
	ii davez = query(raiz[s-1],1,N,s,e);
	if(davez.first <= e) return e - s + 1;
	
	int m = davez.second;
	return max(solve(s,m-1),solve(m+1,e));

}

int main(){
	
	utilidade();
	scanf("%d %d",&N,&K);
	for(int i = 1;i<=N;i++){
		scanf("%d",&V[i]);
	}
	
	Trie* raiz1 = new Trie();
	Trie* raiz2 = new Trie();
	
	for(int i = 1;i<=N;i++){
		L[i] = query_max(raiz1,V[i]);
		add(raiz1,V[i],i);
	}
	for(int i = N;i>=1;i--){
		R[i] = query_min(raiz2,V[i]);
		add(raiz2,V[i],i);
	}
	
	for(int i = 1;i<=N;i++){
 		sweep.push_back(make_tuple(L[i],i,R[i]));
	}
	sort(sweep.begin(),sweep.end());
	
	int ptr = 0;
	for(int i = 0;i<=N;i++){
		
		if(i > 0) raiz[i] = raiz[i-1];
		
		while(ptr < N && get<0>(sweep[ptr]) == i){
			int x1 = get<0>(sweep[ptr]),x2 = get<1>(sweep[ptr]),x3 = get<2>(sweep[ptr]);
			utilidade();
			segPtr++;
			int novo = segPtr;
			update(novo,raiz[i],1,N,x2,ii(x3,x2));
			raiz[i] = novo;
			ptr++;
		}
		
	}
	
	printf("%d\n", solve(1,N) );
	
	return 0;
}