【BZOJ 3166】【HEOI 2013】Alo

http://www.lydsy.com/JudgeOnline/problem.php?id=3166

这道题难点在于求能对一个次大值有贡献的区间。

设这个次大值为\(a_i\)，\(a_i\)左边第一个和第二个比它大的设为\(l_1\)，\(l_2\)，右边第一个和第二个比它大的设为\(r_1\)，\(r_2\)。

\(a_i\)是次大值的区间就是\((l_1,r_2)\)和\((l_2,r_1)\)（直接排序后用set就可以了）。

找这两个区间里和\(a_i\)的异或最大值（实际上可以求两个区间的并），直接用主席树就可以了（为什么叫它可持久化Trie？什么是可持久化Trie？）

空间开小了导致WA，以后主席树不能再卡着空间开了qwq

时间复杂度\(O(n\log n)\)。

#include<set>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int N = 50003;

int l1[N], l2[N], r1[N], r2[N], a[N], id[N], n;

set <int> s;

set <int> :: iterator it, itl, itr;

bool cmp(int x, int y) {return a[x] < a[y];}

struct node {

	int l, r, s;

} T[N * 31];

int root[N], cnt = 0;

int cc;

void update(int &pos, int tmp, int num) {

	T[++cnt] = T[pos]; pos = cnt; ++T[pos].s;

	if (tmp == -1) return;

	if ((1 << tmp) & num) update(T[pos].r, tmp - 1, num);

	else update(T[pos].l, tmp - 1, num);

}

int ask(int Tl, int Tr, int tmp, int num) {

	if (tmp == -1) return 0;

	if ((1 << tmp) & num) {

		if (T[T[Tr].l].s - T[T[Tl].l].s == 0) return ask(T[Tl].r, T[Tr].r, tmp - 1, num);

		else return (1 << tmp) | ask(T[Tl].l, T[Tr].l, tmp - 1, num);

	} else {

		if (T[T[Tr].r].s - T[T[Tl].r].s == 0) return ask(T[Tl].l, T[Tr].l, tmp - 1, num);

		else return (1 << tmp) | ask(T[Tl].r, T[Tr].r, tmp - 1, num);

	}

}

int main() {

	scanf("%d", &n);

	for (int i = 1; i <= n; ++i) scanf("%d", a + i), id[i] = i;

	stable_sort(id + 1, id + n + 1, cmp);

	for (int i = n; i >= 1; --i) {

		s.insert(id[i]);

		it = s.lower_bound(id[i]);

		itl = itr = it;

		if (itl != s.begin())

			--itl, l1[id[i]] = *itl;

		if (itl != s.begin())

			--itl, l2[id[i]] = *itl;

		if (itr != --s.end())

			++itr, r1[id[i]] = *itr;

		else r1[id[i]] = n + 1;

		if (itr != --s.end())

			++itr, r2[id[i]] = *itr;

		else r2[id[i]] = n + 1;

	}

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

		root[i] = root[i - 1];

		update(root[i], 29, a[i]);

	}

	int ans = 0;

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

		if (l1[i] != 0 || r1[i] != n + 1)

			ans = max(ans, ask(root[l2[i]], root[r2[i] - 1], 29, a[i]));

	printf("%d\n", ans);

	return 0;

}