P13895 题解

看到“选择两个不相交的子段”，想到经典 trick：两边分开做，最后统计答案。

假设我们知道了对于任意一个

i

，

1\sim i

（称其为左边）和

i+1\sim n

（称其为右边）的子段分别的最大异或和、最小异或和，我们直接枚举

i

，然后答案就是左边的最大值减右边最小值，右边的最大值减左边最小值中的 max。

CPP

rep(i, 1, n - 1)
{
	int s1 = maxl[i] - minr[i + 1];
	int s2 = maxr[i + 1] - minl[i];
	//minl, maxl, minr, maxr 分别表示两边的最小最大异或和
	ans = max(ans, max(s1, s2));
}

考虑如何求这四个数组。

我们先求左边的情况，右边的情况可以类比。

设

s

为

a

的前缀异或和数组，我们注意到

\oplus_{i = l}^{r} a_i=s_r\oplus s_{l - 1}

于是我们就把一段区间的异或和转化为了两个数的异或的值。

我们枚举右端点

r

，然后找一个

l

使得

s_r\oplus s_{l - 1}

最大（或者最小），可以用 01-trie 解决。

注意这样可以计算到所有区间，右边的情况类比就行了。

CPP

cin >> n;
r(n) cin >> a[i], la[i] = la[i - 1] ^ a[i]; 
reb(i, n, 1) ra[i] = ra[i + 1] ^ a[i];
maxl[0] = maxr[n + 1] = 0;
minl[0] = minr[n + 1] = INT_MAX;
tl.insert(0), tr.insert(0);
r(n) // 枚举右端点 i
{
	int k1 = tl.findmx(la[i]);
	int k2 = tl.findmn(la[i]);
	tl.insert(la[i]);
	maxl[i] = max(maxl[i - 1], k1);
	minl[i] = min(minl[i - 1], k2);
}
reb(i, n, 1)
{
	int k1 = tr.findmx(ra[i]);
	int k2 = tr.findmn(ra[i]);
	tr.insert(ra[i]);
	maxr[i] = max(maxr[i + 1], k1);
	minr[i] = min(minr[i + 1], k2);
}

01-trie 封装代码

CPP

struct Trie
{
	int tr[N << 3][2], cnt = 0;
	void insert(int x)
	{
		int p = 0;
		reb(i, 20, 0)
		{
			bool vl = x & (1 << i);
			if (!tr[p][vl])
				tr[p][vl] = ++cnt;
			p = tr[p][vl];
		}
	}
	int findmx(int x)
	{
		int p = 0, res = 0;
		reb(i, 20, 0)
		{
			bool vl = x & (1 << i);
			if (tr[p][vl ^ 1])
				p = tr[p][vl ^ 1], res |= (1 << i);
			else p = tr[p][vl];
		}
		return res;
	}
	int findmn(int x)
	{
		int p = 0, res = 0;
		reb(i, 20, 0)
		{
			bool vl = x & (1 << i);
			if (tr[p][vl])
				p = tr[p][vl];
			else p = tr[p][vl ^ 1], res |= (1 << i);
		}
		return res;
	}
} tl, tr;

完整 AC 代码

CPP

#include<bits/stdc++.h>
// #define int long long
#define r(x) for (int i = 1; i <= x; i++)
#define rep(i, a, b) for (int i = a; i <= b; i++)
#define reb(i, a, b) for (int i = a; i >= b; i--)
using namespace std;

const int N = 2e6 + 50;
int n, q, x, a[N], ans, maxl[N], maxr[N];
int la[N], ra[N], k, minl[N], minr[N];

struct Trie
{
	int tr[N << 3][2], cnt = 0;
	void insert(int x)
	{
		int p = 0;
		reb(i, 20, 0)
		{
			bool vl = x & (1 << i);
			if (!tr[p][vl])
				tr[p][vl] = ++cnt;
			p = tr[p][vl];
		}
	}
	int findmx(int x)
	{
		int p = 0, res = 0;
		reb(i, 20, 0)
		{
			bool vl = x & (1 << i);
			if (tr[p][vl ^ 1])
				p = tr[p][vl ^ 1], res |= (1 << i);
			else p = tr[p][vl];
		}
		return res;
	}
	int findmn(int x)
	{
		int p = 0, res = 0;
		reb(i, 20, 0)
		{
			bool vl = x & (1 << i);
			if (tr[p][vl])
				p = tr[p][vl];
			else p = tr[p][vl ^ 1], res |= (1 << i);
		}
		return res;
	}
} tl, tr;

signed main()
{
	cin.tie(0)->sync_with_stdio(0);
	cin >> n;
	r(n) cin >> a[i], la[i] = la[i - 1] ^ a[i]; 
	reb(i, n, 1) ra[i] = ra[i + 1] ^ a[i];
	maxl[0] = maxr[n + 1] = 0;
	minl[0] = minr[n + 1] = INT_MAX;
	tl.insert(0), tr.insert(0);
	r(n)
	{
		int k1 = tl.findmx(la[i]);
		int k2 = tl.findmn(la[i]);
		tl.insert(la[i]);
		maxl[i] = max(maxl[i - 1], k1);
		minl[i] = min(minl[i - 1], k2);
	}
	reb(i, n, 1)
	{
		int k1 = tr.findmx(ra[i]);
		int k2 = tr.findmn(ra[i]);
		tr.insert(ra[i]);
		maxr[i] = max(maxr[i + 1], k1);
		minr[i] = min(minr[i + 1], k2);
	}
	rep(i, 1, n - 1)
	{
		int s1 = maxl[i] - minr[i + 1];
		int s2 = maxr[i + 1] - minl[i];
		ans = max(ans, max(s1, s2));
	}
	cout << ans << "\n";
	return 0;
}

文章操作

相关推荐

评论

P13895 题解