[bzoj 3166] [Heoi2013]Alo

长度为n的序列a, 一个区间的价值等于这段区间的次大值与区间内其他任意一个数异或的最大值, 求最大价值. (1≤n≤50000, 0≤ai≤10^9, ai两两不同) 枚举次大值, 求该次大值对应的区间, 则问题转化为一个简单的模型.

最大值对应的区间我们会求. 单调栈左右各跑一遍, 求出左边大于它的最大位置l, 和右边大于它的最小位置r.

方便起见, 令a[0]=a[n+1]=inf. 次大值a[i]对应的区间, 首先也求出这两个量. 若l!=0, 则a[l]是区间的最大值, a[r]同理, 并且a[l], a[r]不能同在一个区间. 继续向右延伸, 求出r的右边大于a[i]的最小位置y, 同样地, 向左延伸, 求出x. 若l!=0, 则(x, r)是a[i]作次大值, a[l]作最大值的最长区间. 若r!=n+1, 则(l, y)是a[i]作次大值, a[r]作最大值的最长区间. 查询最大异或时, 可以把这两个区间合并.

现在问题是求[1, p]范围内值大于x的最大位置, [p, n]范围内值大于x的最小位置. 值域范围是前提, 在此基础上最大化或最小化位置. 把位置和值当成二元组排序显然是错误的, 但我怎么就......可持久化线段树可以完成, 而且这个问题显然是二维的, 但是不想写, 来了个自认为正确事实上单次操作的线段树.

所以最后还是来了个可持久化线段树......每个结点两个附加域, 表示这棵子树中存在的最大值和最小值. 离散化之后, 按照值从大到小, 将下标排序, 依次插入. 我曾经想, 区间K大等应用中是每个位置一棵权值线段树, 那么每个权值一棵线段树存位置有什么应用吗? 现在明白, 可以查询某一范围的值在序列中出现位置的信息.

然后看了看题解......以上在造轮子......既然值域范围是前提, 查询的是大于x的位置, 为什么不按照值从大到小, 将下标插进一棵平衡树, 找找前驱后继呢? 一个set就搞定了.

对于前缀, 后缀的信息, 有时控制结点插入顺序可以完成可持久化的工作. 这个顺序有可能是位置上的, 也可能是值上的.

set

#include <bits/stdc++.h>
#define Rep(i, a, b) for (int i = (a), i##_ = (b); i < i##_; ++i)
#define For(i, a, b) for (int i = (a), i##_ = (b); i <= i##_; ++i)
#define Down(i, a, b) for (int i = (a), i##_ = (b); i >= i##_; --i)
#define bin(x, k) ((x)>>(k)&1)
#define iter iterator
using namespace std;
const int D = 30, MAX_N = 5e4;
typedef set<int> Set;

namespace Trie {
	struct Node {
		Node* ch[2];
		int v;
	} nodes[(D+1)*MAX_N+1], * nil = nodes, * root[MAX_N+1] = {nil};

	inline Node* new_node(const Node& x)
	{
		static Node* cur = nodes + 1;
		*cur = x;
		return cur++;
	}

	void insert(Node* &o, Node* p, int x, int k)
	{
		o = new_node(*p);
		++o->v;
		if (k < 0) return;
		int b = bin(x, k);
		insert(o->ch[b], p->ch[b], x, k-1);
	}

	inline void insert(int i, int x)
	{
		insert(root[i], root[i-1], x, D-1);
	}
	
	int query(Node* o, Node* p, int x, int k)
	{
		if (k < 0) return 0;
		int b = bin(x, k)^1;
		return o->ch[b] - p->ch[b] ? 1<<k | query(o->ch[b], p->ch[b], x, k-1)
			: query(o->ch[b^1], p->ch[b^1], x, k-1);
	}

	inline int query(int x, int y, int v)
	{
		return query(root[y], root[x-1], v, D-1);
	}
	
	inline void init()
	{
		*nil = (Node){nil, nil, 0};
	}
};

int n, a[MAX_N+1], h[MAX_N], top;
Set S;

inline bool cmp(int i, int j)
{
	return a[i] < a[j];
}

int main()
{	
	int ans = 0;
	scanf("%d", &n);
	Trie::init();

	For (i, 1, n) {
		scanf("%d", &a[i]);
		Trie::insert(i, a[i]);
		h[top++] = i;
	}

	sort(h, h+top, cmp);

	S.insert(0);
	S.insert(n+1);
	
	Down (i, n-1, 0) {
		Set::iter l, r;
		S.insert(h[i]);
		l = r = S.find(h[i]);
		if (*--l > 0) --l;
		if (*++r <= n) ++r;
		ans = max(ans, Trie::query(*l+1, *r-1, a[h[i]]));
	}

	printf("%d\n", ans);
	
	return 0;
}

可持久化线段树

#include <bits/stdc++.h>
#define Rep(i, a, b) for (int i = (a), i##_ = (b); i < i##_; ++i)
#define For(i, a, b) for (int i = (a), i##_ = (b); i <= i##_; ++i)
#define Down(i, a, b) for (int i = (a), i##_ = (b); i >= i##_; --i)
#define bin(x, k) ((x)>>(k)&1)

using namespace std;
const int D = 30, inf = 1e9 + 1, MAX_N = 5e4, LG_N = 16;

namespace Trie {
	struct Node {
		Node* ch[2];
		int v;
	} nodes[(D+1)*MAX_N+1], * nil = nodes, * root[MAX_N+1] = {nil};

	inline Node* new_node(const Node& x)
	{
		static Node* cur = nodes + 1;
		*cur = x;
		return cur++;
	}

	void insert(Node* &o, Node* p, int x, int k)
	{
		o = new_node(*p);
		++o->v;
		if (k < 0) return;
		int b = bin(x, k);
		insert(o->ch[b], p->ch[b], x, k-1);
	}

	inline void insert(int i, int x)
	{
		insert(root[i], root[i-1], x, D-1);
	}
	
	int query(Node* o, Node* p, int x, int k)
	{
		if (k < 0) return 0;
		int b = bin(x, k)^1;
		return o->ch[b] - p->ch[b] ? 1<<k | query(o->ch[b], p->ch[b], x, k-1)
			: query(o->ch[b^1], p->ch[b^1], x, k-1);
	}

	inline int query(int x, int y, int v)
	{
		return query(root[y], root[x-1], v, D-1);
	}
	
	inline void init()
	{
		*nil = (Node){nil, nil, 0};
	}
};

int n;

namespace Seg {
	struct Node {
		Node* lc, * rc;
		int mn, mx;
		void up()
		{
			mn = min(lc->mn, rc->mn);
			mx = max(lc->mx, rc->mx);
		}
	} nodes[(MAX_N+2)*(LG_N+1) + 1], * nil = nodes, * root[MAX_N+3];

	inline void init()
	{
		* nil = (Node){nil, nil, inf, -1};
		root[n+2] = nil;
	}
	
	inline Node* new_node(const Node& x)
	{
		static Node* cur = nodes + 1;
		*cur = x;
		return cur++;
	}
	
	void insert(Node* &o, Node* p, int x, int l, int r)
	{
		o = new_node(*p);
		if (l == r) {
			o->mn = o->mx = x;
			return;
		}
		int m = (l+r)/2;
		if (x <= m) insert(o->lc, p->lc, x, l, m);
		else insert(o->rc, p->rc, x, m+1, r);
		o->up();
	}

	inline void insert(int i, int x)
	{
		insert(root[i], root[i+1], x, 0, n+1);
	}
	
	// 大于等于x的最小元素
	int qmin(Node* o, int x, int l, int r)
	{
		if (l == r) return l;
		int m = (l+r)/2;
		if (x > m || o->lc->mx < x)
			return qmin(o->rc, x, m+1, r);
		return qmin(o->lc, x, l, m);
	}

	// 小于等于x的最大元素
	int qmax(Node* o, int x, int l, int r)
	{
		if (l == r) return l;
		int m = (l+r)/2;
		if (x <= m || o->rc->mn > x)
			return qmax(o->lc, x, l, m);
		return qmax(o->rc, x, m+1, r);
	}

	inline int qmin(int i, int x)
	{
		return qmin(root[i], x, 0, n+1);
	}

	inline int qmax(int i, int x)
	{
		return qmax(root[i], x, 0, n+1);
	}
};

int a[MAX_N+2], h[MAX_N+2], top;

inline bool cmp(int i, int j)
{
	return a[i] < a[j];
}

int main()
{	
	int ans = 0;
	scanf("%d", &n);
	Trie::init();
	Seg::init();
	For (i, 1, n) {
		scanf("%d", &a[i]);
		Trie::insert(i, a[i]);
		h[top++] = i;
	}

	a[0] = a[n+1] = inf;
	h[top++] = 0;
	h[top++] = n+1;

	sort(h, h+top, cmp);

	Down (i, top-1, 0)
		Seg::insert(i, h[i]);
	
	For (i, 1, n) {
		int j = upper_bound(h, h+top, i, cmp) - h, r = Seg::qmin(j, i+1), l = Seg::qmax(j, i-1);
		if (r <= n) {
			int p = Seg::qmin(j, r+1); // [l+1, p-1]
			ans = max(ans, Trie::query(l+1, p-1, a[i]));
		}
		if (l > 0) {
			int p = Seg::qmax(j, l-1); // [p+1, r-1]
			ans = max(ans, Trie::query(p+1, r-1, a[i]));
		}
	}

	printf("%d\n", ans);
	
	return 0;
}