codeforces 1457 D. XOR-gun (构造)

题目链接：https://codeforces.com/contest/1457/problem/D

错误做法：以为只有连续异或一段数的情况，直接上(trie), wa 在 (51) 个点上
后来发现还有一种情况: 左边连续一段异或起来大于右边连续一段异或起来

正确做法：构造，序列中如果连续三个数最高位 (1) 位置相同，则可以通过异或后两个数一次满足条件
所以如果数列中超过了 (60) 个数，答案必定为 (1), 如果小于 (60) 个数，暴力即可

trie: (调了好久才调出来发现是错误做法。。)

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;
typedef long long ll;

const int maxn = 100010;

int n;
ll a[maxn];

int rt = 0, tot = 0;

struct Trie{
	int son[2];
	int pos;
}trie[maxn * 32];

void insert(int x, int l){
	int p = rt;
	for(int i = 31 ; i >= 0 ; --i){
		int c = (x >> i) & 1;
		
		if(!trie[p].son[c]){
			trie[p].son[c] = ++tot;
		}
		
		p = trie[p].son[c];
		trie[p].pos = l;
	}
}

int query_l(int x, int y){
	int p = rt;
	int res = -1;
	for(int i = 31; i >= 0 ; --i){
		int c = (x >> i) & 1;
		int g = (y >> i) & 1;
//		printf("%d %d %d
", i, c, g);
		if(c == 1){
			if(g == 0){ // 两边都可以走 
				if(trie[p].son[0]){ // 异或值满足条件，记录一下答案, 向反方向探索 
					res = max(res, trie[trie[p].son[0]].pos); 
					if(trie[p].son[1]) p = trie[p].son[1];
					else return res;
//					printf("pos: %d
", trie[trie[p].son[0]].pos); 
				} else{ // 目前异或值相等，继续向下寻找 
					if(trie[p].son[1]) p = trie[p].son[1];
					else return res;
				}	
			} else{ // 只能异或值为 1 才能相等，否则不满足条件 
				if(trie[p].son[0]){
					p = trie[p].son[0];
				} else{
					return res;
				} 
			}
		} else{
			if(g == 0){ // 两边都可以走 
				if(trie[p].son[1]){ // 异或值满足条件，记录一下答案, 无需向下探索 
					res = max(res, trie[trie[p].son[1]].pos); 
					if(trie[p].son[0]) p = trie[p].son[0];
					else return res;
//					printf("pos: %d
", trie[trie[p].son[0]].pos); 
				} else{ // 目前异或值相等，继续向下寻找 
					if(trie[p].son[0]) p = trie[p].son[0];
					else return res;
				}	
			} else{ // 只能异或值为 1 才能相等，否则不满足条件 
				if(trie[p].son[1]){
					p = trie[p].son[1];
				} else{ // 否则不满足条件，直接返回不可能 
					return res;
				} 
			}
		}
//		printf("%d ", p);
	}
//	printf("
");
	return res; 
}

int query_r(int x, int y){
//	printf("x:%d y:%d
", x, y);
	int p = rt;
	int res = 1000000007;
	for(int i = 31; i >= 0 ; --i){
		int c = (x >> i) & 1;
		int g = (y >> i) & 1;
//		printf("%d %d %d
", i, c, g);
		if(c == 1){
			if(g == 1){ // 两边都可以走 
				if(trie[p].son[1]){ // 异或值满足条件，记录一下答案, 无需向下探索 
					res = min(res, trie[trie[p].son[1]].pos); 
					if(trie[p].son[0]) p = trie[p].son[0];
					else return res;
//					printf("pos: %d %d
", i, trie[trie[p].son[0]].pos); 
				} else{ // 目前异或值相等，继续向下寻找 
					if(trie[p].son[0]) p = trie[p].son[0];
					else return res;
				}	
			} else{ // 只能异或值为 0 才能相等，否则不满足条件 
//				printf("zhixing %d
", trie[p].son[1]);
				if(trie[p].son[1]){
					p = trie[p].son[1];
				} else{
					return res;
				} 
			}
		} else{
			if(g == 1){ // 两边都可以走 
				if(trie[p].son[0]){ // 异或值满足条件，记录一下答案, 无需向下探索 
					res = min(res, trie[trie[p].son[0]].pos);
					if(trie[p].son[1]) p = trie[p].son[1];
					else return res;
//					printf("pos: %d %d
", i, trie[trie[p].son[0]].pos); 
				} else{ // 目前异或值相等，继续向下寻找 
					if(trie[p].son[1]) p = trie[p].son[1];
					else return res;
				}	
			} else{ // 只能异或值为 0 才能相等，否则不满足条件 
				if(trie[p].son[0]){
					p = trie[p].son[0];
				} else{ // 否则不满足条件，直接返回不可能 
					return res;
				} 
			}
		}
//		printf("p : %d 
", p);
	}
	return res; 
} 

ll read(){ ll s = 0, f = 1; char ch = getchar(); while(ch < '0' || ch > '9'){ if(ch == '-') f = -1; ch = getchar(); } while(ch >= '0' && ch <= '9'){ s = s * 10 + ch - '0'; ch = getchar(); } return s * f; }

int main(){
	n = read();
	for(int i = 1 ; i <= n ; ++i) a[i] = read();
	
	int ans = 10000000;
	insert(0, 0);
	int sum = a[1];
	insert(a[1], 1);
	for(int i = 2 ; i <= n - 1; ++i){
		sum ^= a[i];
		int res = query_l(sum, a[i + 1]);
		if(res != -1) ans = min(ans, i - res - 1);
		insert(sum, i);
	}
//	printf("%d
", ans);

	tot = 0;
	memset(trie, 0, sizeof(trie));
	
	insert(0, n + 1);
	sum = a[n];
	insert(a[n], n);
	
//	printf("%d
", sum);
	for(int i = n - 1 ; i >= 2 ; --i){
		sum ^= a[i];
//		printf("%d: %d %d
", i, sum, a[i - 1]);
		int res = query_r(sum, a[i - 1]);
		if(res != 1000000007) {
			ans = min(ans, res - i - 1);
//			printf("%d %d %d %d
", i, res, ans, sum);
		}
		insert(sum, i);
	}
	
	printf("%d
", ans == 10000000? -1: ans);
	
	return 0;
}