单调栈&可持久化0/1trie树

题目链接

题目描述

小w学会了RMQ算法，他现在可以求出一个给定数组某一段子区间的最大值，最小值。
在这之前，他也学会了前缀和，并且他知道前缀和可以扩展到位运算求出区间异或和。
现在你给了他一个长度大小为n的数组，为了考察小w写RMQ以及前缀异或和的正确性，你要求他求出该数组的某一个子区间，记该子区间的异或和为xorsum，记该子区间的最大值为max，记该子区间的最小值为min，你要求使得xorsum⊕max⊕min最大。其中⊕为位运算异或操作。

输入描述:

第一行输入一个正整数n，表示数组的长度。
接下来一行n个非负整数a[i]表示数组中的内容。

输出描述:

仅一行一个非负整数，表示xorsum⊕max⊕min的最大值。

样例输入

3
1 2 3

样例输出

3

题解

根据大佬Treaker的指示，我们知道我们需要枚举最大值和最小值。所以我们先用单调栈来预处理每一个数右面第一个比自己大的数和第一个比自己小的数。时间复杂度为\(O(n)\).

然后我们在处理好之后就可以枚举每一个子序列的左端点，由于在一定的范围内子序列的最大值和最小值是不变的，所以我们可以利用我们处理好的单调栈来更新最小值和最大值。根据yych大佬的指示，在平均情况下（随机数据下）我们需要"跳"（更新）\(log(n)\)次。

那么当我们确定了最大值和最小之后，怎么跟新我们的答案？这时候就要用到可持久化0/1trie树了。设最大值的位置是\(maxx\),最小值的位置是\(minn\)，第一个比\(a_i\)大的位置是\(da[i]\),第一个比\(a_i\)小的位置是\(xiao[i]\),\(yi[i]\)为前缀异或和，则我们需要在\(max(maxx,minn)\)~\(da(xiao)[maxx]-1\)找到一个\(yi[i]\)使其亦或上\(yi[i-1]\) ^ \(a[maxx]\)^\(a[minn]\)最大（想一想，为什么）。我们使用可持久化0/1trie树就能在\(O(log(n))\)内找出最大值了。

这样的时间复杂度是\(O(nlog^2(n))\),但是这里面还是存在一些问题，那就是当数据为单调递增（减）的时候，单调栈更新最大值和最小值的时间复杂度就退化成了\(O(n)\),这样的时间复杂度是\(O(n^2log(n))\).妥妥的\(TLE\)，对于这样数据我们直接判一下，我们发现就是求一段区间的异或和的最大值，直接用trie树就OK了。这样的时间复杂度为\(O(nlog(n))\).但这毕竟只能特判，在不知道的情况下还是会死掉的TAT。

实测最慢的为707 ms，还是比较优秀的（可能是我分析的时间复杂度不太准吧）。代码还是很好打的。

最后献上我丑陋的代码。

#include<iostream>
#include<cstdio>
#define R register
using namespace std;
int n, top, ans, cnt, maxx, minn, f1, f2;
const int N = 100010;
int a[N], zhan[N], da[N], xiao[N], yi[N], rt[N];
int js[N * 50], tr[N * 50][2];
inline int read() 
{
	int res = 0; char ch = getchar(); bool XX = false;
	for (; !isdigit(ch); ch = getchar())(ch == '-') && (XX = true);
	for (; isdigit(ch); ch = getchar())res = (res << 3) + (res << 1) + (ch ^ 48);
	return XX ? -res : res;
}
void Insert(int k, int pre, int t, int x) 
{
	if (t < 0)return;
	R int i = (x >> t) & 1;
	tr[k][!i] = tr[pre][!i];
	tr[k][i] = ++cnt;
	js[tr[k][i]] = js[tr[pre][i]] + 1;
	Insert(tr[k][i], tr[pre][i], t - 1, x);
}
int ask(int l, int r, int t, int x) 
{
	if (t < 0)return 0;
	R int i = (x >> t) & 1;
	if (js[tr[r][!i]] > js[tr[l][!i]])
		return (1 << t) | ask(tr[l][!i], tr[r][!i], t - 1, x);
	else return ask(tr[l][i], tr[r][i], t - 1, x);
}

inline void yych() 
{
	cin >> n; f1 = f2 = 1;
	for (R int i = 1; i <= n; ++i) 
	{
		a[i] = read();
		yi[i] = a[i] ^ yi[i - 1];
		rt[i] = ++cnt;
		Insert(rt[i], rt[i - 1], 29, yi[i]);
	}
	for (R int i = 1; i <= n; ++i)da[i] = xiao[i] = n + 1;
	top = 0;
	for (R int i = 1; i <= n; ++i) 
	{
		while (top && a[zhan[top]] < a[i])da[zhan[top--]] = i;
		zhan[++top] = i;
	}
	top = 0;
	for (R int i = 1; i <= n; ++i) 
	{
		while (top && a[zhan[top]] > a[i])xiao[zhan[top--]] = i;
		zhan[++top] = i;
	}
	for (int i = 2; i <= n; ++i) 
	{
		if (a[i] < a[i - 1])f1 = 0;
		if (a[i] > a[i - 1])f2 = 0;
	}
}
void slove1() 
{
	for (int i = 1; i <= n; ++i)ans = max(ans, a[i]);
	for (int i = 2; i <= n - 1; ++i)
		ans = max(ans, ask(rt[i - 1], rt[n - 1], 29, yi[i - 1]));
}
int main() 
{
	yych();
	if (f1 || f2) 
	{
		slove1();
		cout << ans;
		return 0;
	}
	for (R int i = 1; i <= n; ++i) 
	{
		maxx = minn = i;
		while (maxx <= n && minn <= n) 
		{
			if (da[maxx] <= xiao[minn]) 
			{
				ans = max(ans , ask(rt[max(maxx, minn) - 1] , rt[da[maxx] - 1] , 29 , yi[i - 1] ^ a[maxx] ^ a[minn]));
				maxx = da[maxx];
			} else 
			{
				ans = max(ans , ask(rt[max(maxx, minn) - 1] , rt[xiao[minn] - 1] , 29 , yi[i - 1] ^ a[maxx] ^ a[minn]));
				minn = xiao[minn];
			}
		}
	}
	cout << ans;
	return 0;
}