【bzoj2770】YY的Treap 权值线段树

题目描述

志向远大的YY小朋友在学完快速排序之后决定学习平衡树，左思右想再加上SY的教唆，YY决定学习Treap。友爱教教父SY如砍瓜切菜般教会了YY小朋友Treap（一种平衡树，通过对每个节点随机分配一个priority，同时保证这棵平衡树关于priority是一个小根堆以保证效率）。这时候不怎么友爱的510跑了出来，他问了YY小朋友一个极不和谐的问题：怎么求Treap中两个点之间的路径长度。YY秒了之后决定把这个问题交给你来做，但只要求出树中两点的LCA。

输入

第一行两个整数n，m

第二行n个整数表示每个元素的key

第三行n个整数表示每个元素的priority

接下m行，每行一条命令

I A B，插入一个元素，key为A, priority为B

D A，删除一个元素，key为A

Q A B，询问key分别为A和B的LCA的key

输出

对于每个Q输出一个整数。

样例输入

2 1
1 2
4 5
Q 1 2

样例输出

题解

权值线段树

一个小结论：不妨设$a\le b$，则Treap中权值为$a$、$b$两点的LCA为权值在$[a,b]$之间，优先级最小的点。

证明：

1.LCA的权值在$[a,b]$之间：考虑从$a$、$b$找到LCA的最后一步：一定是$a$在LCA的非右子树，$b$在LCA的非左子树。否则$a$、$b$在同子树内则LCA可以为更优的该儿子节点。

2.权值在$[a,b]$之间的节点一定都在LCA的子树内：如果不在LCA的子树内，那么节点如果在LCA右侧则一定大于$b$，或在LCA左侧则一定小于$a$。

3.LCA的子树中所有节点的优先级都小于等于LCA：证明显然。

4.LCA一定在LCA的子树内：证明显然。

因此由1、2、3、4得证。

于是只需要对每个数的key维护权值线段树，维护权值在某区间内的数的优先级最小值及其位置。查询时直接区间查询即可。

为了避免一些细节问题（比如两个int加起来爆int之类的），代码中使用了离线离散化。

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

#include <cstdio>

#include <utility>

#include <algorithm>

#define N 100010

#define lson l , mid , x << 1

#define rson mid + 1 , r , x << 1 | 1

#define id(x) lower_bound(v + 1 , v + tot + 1 , x) - v

#define inf 0x7fffffff

using namespace std;

typedef pair<int , int> pr;

int key[N] , pri[N] , opt[N * 3] , qx[N * 3] , qy[N * 3] , v[N << 2] , tot;

pr mn[N << 4];

char str[5];

void build(int l , int r , int x)

{

	mn[x] = pr(inf , inf);

	if(l == r) return;

	int mid = (l + r) >> 1;

	build(lson) , build(rson);

}

void insert(int p , int v , int l , int r , int x)

{

	if(l == r)

	{

		mn[x] = pr(v , p);

		return;

	}

	int mid = (l + r) >> 1;

	if(p <= mid) insert(p , v , lson);

	else insert(p , v , rson);

	mn[x] = min(mn[x << 1] , mn[x << 1 | 1]);

}

void erase(int p , int l , int r , int x)

{

	if(l == r)

	{

		mn[x] = pr(inf , inf);

		return;

	}

	int mid = (l + r) >> 1;

	if(p <= mid) erase(p , lson);

	else erase(p , rson);

	mn[x] = min(mn[x << 1] , mn[x << 1 | 1]);

}

pr query(int b , int e , int l , int r , int x)

{

	if(b <= l && r <= e) return mn[x];

	int mid = (l + r) >> 1;

	pr ans(inf , inf);

	if(b <= mid) ans = min(ans , query(b , e , lson));

	if(e > mid) ans = min(ans , query(b , e , rson));

	return ans;

}

int main()

{

	int n , m , i;

	scanf("%d%d" , &n , &m);

	for(i = 1 ; i <= n ; i ++ ) scanf("%d" , &key[i]) , v[++tot] = key[i];

	for(i = 1 ; i <= n ; i ++ ) scanf("%d" , &pri[i]);

	for(i = 1 ; i <= m ; i ++ )

	{

		scanf("%s%d" , str , &qx[i]);

		if(str[0] == 'I') opt[i] = 1 , scanf("%d" , &qy[i]) , v[++tot] = qx[i];

		else if(str[0] == 'D') opt[i] = 2;

		else opt[i] = 3 , scanf("%d" , &qy[i]);

	}

	sort(v + 1 , v + tot + 1);

	build(1 , tot , 1);

	for(i = 1 ; i <= n ; i ++ ) insert(id(key[i]) , pri[i] , 1 , tot , 1);

	for(i = 1 ; i <= m ; i ++ )

	{

		if(opt[i] == 1) insert(id(qx[i]) , qy[i] , 1 , tot , 1);

		else if(opt[i] == 2) erase(id(qx[i]) , 1 , tot , 1);

		else if(qx[i] < qy[i]) printf("%d\n" , v[query(id(qx[i]) , id(qy[i]) , 1 , tot , 1).second]);

		else printf("%d\n" , v[query(id(qy[i]) , id(qx[i]) , 1 , tot , 1).second]);

	}

	return 0;

}

巴特西

【bzoj2770】YY的Treap 权值线段树

最新文章

热门文章