题目：[USACO 6.1.3] Cow XOR

没找到这题具体网址，这个题就是求最大异或区间（总长度尽量小，右端点尽量大）

嗯很显然一个[l，r]的异或和=s[r]^{s[l-1]，那么现在有了优秀的n}2做法

不难（很难）联想trie树，枚举1到n每次把1...i的异或和加入trie树中，然后跑一遍找最大值（史记上就是trie树维护这个n^2算法，降低了复杂度）

代码：

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <algorithm>

const int N=1e5+5;

using namespace std;

int n,m,tot,ret=-1,lr,rr,a[N],sum;

namespace trietree

{

	struct trie

	{

		int son[2],tag;

	}e[N*22];

	void insert(int x,int id)

	{

		int p=0;

		for(int i=21;i>=0;i--)

		{

			int k=x>>i&1;

			if(!e[p].son[k])

			    e[p].son[k]=++tot;

			p=e[p].son[k];

		}

		e[p].tag=id;

	}

	int query(int x,int &ans)

	{

		int p=0;

		for(int i=21;i>=0;i--)

		{

			int k=x>>i&1;

			if(!e[p].son[k^1])

			    p=e[p].son[k];

			else

			    p=e[p].son[k^1],ans+=1<<i;

		}

		return e[p].tag;

	}

}

using namespace trietree;

int main()

{

	scanf("%d",&n);

	for(int i=1;i<=n;i++)

	{

		int x;

		scanf("%d",&x);

		sum^=x;

		insert(sum,i);

		int ans=0;

		int l=query(sum,ans);

		if(ans>ret)

		{

			ret=ans;

			rr=i,lr=l;

		}

	}

	printf("%d %d %d\n",ret,lr+1,rr);

	return 0;

}

2022春每日一题：Day 33的相关教程结束。