bzoj 2770 YY的Treap

Written with StackEdit.

Description

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

Input

第一行两个整数\(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.\)

Output

对于每个\(Q\)输出一个整数。

Sample Input

2 2

1 2

4 5

Q 1 2

I 3 3

Sample Output

HINT

数据保证\(n<=10^5,m<=3*10^5\).

其余整数均不超过\(int\)的范围.

数据保证任意时刻树中\(key\)和\(priority\)均不相同.

Solution

此题就是对\(treap\)基本性质的一个考察.
\(C\)是\(A,B\)的\(LCA\)(假设\(key_a<key_b\)).需要满足\(key_c\in [key_a,key_b]\),这样能保证\(A,B\)到根的路径上都经过\(C\).
而要求最近的公共祖先,根据\(priority\)满足小根堆的性质,只需找出其中\(priority\)最小的点即为\(LCA\).
可以建一颗权值线段树,问题转化为修改,删除,以及区间上查询最值.

#include<bits/stdc++.h>

#define inf 0x7fffffff

#define root Tree[o]

#define lson Tree[o<<1]

#define rson Tree[o<<1|1]

using namespace std;

typedef long long LoveLive;

typedef pair<int,int> pii;

inline int read()

{

	int out=0,fh=1;

	char jp=getchar();

	while ((jp>'9'||jp<'0')&&jp!='-')

		jp=getchar();

	if (jp=='-')

		{

			fh=-1;

			jp=getchar();

		}

	while (jp>='0'&&jp<='9')

		{

			out=out*10+jp-'0';

			jp=getchar();

		}

	return out*fh;

}

const int MAXN=4e5+10;

int n,m;

struct Query{

	int op;

	int a,b;//key,pro

	int ans,id;

}q[MAXN];

int kc[MAXN];

struct node{

	int l,r,mi,pos,sum,val;

}Tree[MAXN<<3];

void phup(int o)

{

	if(lson.mi<rson.mi)

		root.mi=lson.mi,root.pos=lson.pos;

	else

		root.mi=rson.mi,root.pos=rson.pos;

	root.sum=lson.sum+rson.sum;

}

void bd(int l,int r,int o)

{

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

	root.l=l,root.r=r;

	root.mi=inf;

	root.sum=0;

	if(l==r)

		return;

	bd(l,mid,o<<1);

	bd(mid+1,r,o<<1|1);

}

void add(int o,int x,int pos)

{

	int l=root.l,r=root.r;

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

	if(l==r)

		{

			root.val=x;

			root.mi=x;

			root.pos=l;

			++root.sum;

			return;

		}

	if(pos<=mid)

		add(o<<1,x,pos);

	else

		add(o<<1|1,x,pos);

	phup(o);

}

void del(int o,int pos)

{

	int l=root.l,r=root.r;

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

	if(l==r)

		{

			root.mi=inf;

			--root.sum;

			return;

		}

	if(pos<=mid)

		del(o<<1,pos);

	else

		del(o<<1|1,pos);

	phup(o);

}

void ins(int x,int pos)

{

	add(1,x,pos);

}

void rem(int pos)

{

	del(1,pos);

}

int ansmi,anspos;

void qy(int o,int L,int R)

{

	int l=root.l,r=root.r;

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

	if(r<L || l>R)

		return;

	if(L<=l && r<=R)

		{

			if(root.mi<ansmi)

				ansmi=root.mi,anspos=root.pos;

			return;

		}

	if(L<=mid)

		qy(o<<1,L,R);

	if(R>mid)

		qy(o<<1|1,L,R);

}

int main()

{

	n=read(),m=read();

	int cnt=0;

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

		{

			q[i].op=1;

			q[i].a=read();

			kc[++cnt]=q[i].a;

			q[i].id=i;

		}

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

		q[i].b=read();

	int idx=n;

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

		{

			++idx;

			q[idx].id=idx;

			char buf[2];

			scanf("%s",buf);

			if(buf[0]=='I')

				{

					q[idx].op=1;

					q[idx].a=read();

					kc[++cnt]=q[idx].a;

					q[idx].b=read();

				}

			else if(buf[0]=='D')

				{

					q[idx].op=2;

					q[idx].a=read();

					kc[++cnt]=q[idx].a;

				}

			else

				{

					q[idx].op=3;

					q[idx].a=read();

					kc[++cnt]=q[idx].a;

					q[idx].b=read();

					kc[++cnt]=q[idx].b;

				}

		}

	bd(1,2*n,1);

	sort(kc+1,kc+1+cnt);

	cnt=unique(kc+1,kc+1+cnt)-(kc+1);

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

		{

			if(q[i].op==1)

				{

					q[i].a=lower_bound(kc+1,kc+1+cnt,q[i].a)-kc;

					ins(q[i].b,q[i].a);

				}

			else if(q[i].op==2)

				{

					q[i].a=lower_bound(kc+1,kc+1+cnt,q[i].a)-kc;

					rem(q[i].a);

				}

			else if(q[i].op==3)

				{

					 q[i].a=lower_bound(kc+1,kc+1+cnt,q[i].a)-kc;

					 q[i].b=lower_bound(kc+1,kc+1+cnt,q[i].b)-kc;

					 ansmi=inf;

					 qy(1,min(q[i].a,q[i].b),max(q[i].a,q[i].b));

					 printf("%d\n",kc[anspos]);

				}

		}

	return 0;

}

巴特西