奶牛异或

NC22998. 奶牛异或

描述

农民约翰在喂奶牛的时候被另一个问题卡住了。他的所有N(1 <= N <= 100,000)个奶牛在他面前排成一行(按序号1..N的顺序)，按照它们的社会等级排序。奶牛#1有最高的社会等级，奶牛#N最低。每个奶牛同时被指定了一个不唯一的附加值，这个数在 [0, 2²¹ - 1] 的范围内。

帮助农民约翰找出应该从哪一头奶牛开始喂，使得从这头奶牛开始的一个连续的子序列上，奶牛的附加值的异或最大。

如果有多个这样的子序列，选择结尾的奶牛社会等级最高的。如果还不唯一，选择最短的。

输入描述

第1行:一个单独的整数N。

第2到N + 1行:N个 [0, 2²¹ - 1] 之间的整数，代表每头奶牛的被赋予的数。第j行描述了社会等级j - 1的奶牛。

输出描述

第 1 行: 3个空格隔开的整数，分别为：最大的异或值，序列的起始位置、终止位置。

示例1

输入:

输出:

6 4 5

说明:

最大异或值为6，从第4个开始喂，到第5个结束。

4 异或 2 = 6

(100) 异或 (010) = (110)

上次编辑到这里，代码来自缓存点击恢复默认模板

C++(clang++ 11.0.1) 解法, 执行用时: 89ms, 内存消耗: 7260K, 提交时间: 2022-09-06 00:14:39

#include<bits/stdc++.h>
using namespace std;
int t[100010*32][2],idx,cnt[100010*32],id;
void insert(int x){
	int now=0;
	for(int i=31;i>=0;i--){
		if(!t[now][x>>i&1])t[now][x>>i&1]=++idx;
		now=t[now][x>>i&1];
	}
	cnt[now]=++id;
}
pair<int,int>ch(int x){
	int ans=0,now=0;
	for(int i=31;i>=0;i--){
		int num=x>>i&1;
		if(t[now][!num])now=t[now][!num],ans+=1<<i;
		else now=t[now][num];
	}
	return {ans,cnt[now]};
}
int a[100100];
int main(){
	int n,ans=-1,l,r;
	cin>>n;
	insert(0);
	for(int i=1;i<=n;i++){
		cin>>a[i];
		a[i]^=a[i-1];
		auto [x,y]=ch(a[i]);
		if(x>ans){
			ans=x;
			l=y,r=i;
		}
		insert(a[i]);
	}
	
	cout<<ans<<" "<<l<<" "<<r<<endl;
	return 0;
}