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
1
HINT
数据保证(n<=10^5,m<=3*10^5).
其余整数均不超过(int)的范围.
数据保证任意时刻树中(key)和(priority)均不相同.
Solution
- 此题就是对(treap)基本性质的一个考察.
- (C)是(A,B)的(LCA)(假设(key_a<key_b)).需要满足(key_cin [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
",kc[anspos]);
}
}
return 0;
}