【BZOJ2770】YY的Treap
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
1 2
4 5
Q 1 2
I 3 3
Sample Output
1
HINT
数据保证n<=10^5,m<=3*10^5
其余整数均不超过long的范围
数据保证任意时刻树中key和priority均不相同
题解：上来的第一直觉就是猜结论：Treap中a和b的LCA就是key值在a,b之间的，priority最小的点。一开始还想了想怎么证，后来发现这么显然的结论还用证~
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define lson x<<1
#define rson x<<1|1
using namespace std;
typedef long long ll;
const int maxn=400010;
int n,m,nm,tot;
int s[maxn<<2];
int op[maxn],pa[maxn];
ll pr[maxn],pb[maxn],ref[maxn],v[maxn];
char str[10];
struct node
{
ll val;
int org;
}p[maxn<<1];
inline int MN(int a,int b)
{
return v[a]<v[b]?a:b;
}
bool cmp(const node &a,const node &b)
{
return a.val<b.val;
}
void build(int l,int r,int x)
{
if(l==r)
{
s[x]=l;
return ;
}
int mid=(l+r)>>1;
build(l,mid,lson),build(mid+1,r,rson);
s[x]=MN(s[lson],s[rson]);
}
void updata(int l,int r,int x,int y)
{
if(l==r) return ;
int mid=(l+r)>>1;
if(y<=mid) updata(l,mid,lson,y);
else updata(mid+1,r,rson,y);
s[x]=MN(s[lson],s[rson]);
}
int query(int l,int r,int x,int a,int b)
{
if(a<=l&&r<=b) return s[x];
int mid=(l+r)>>1;
if(b<=mid) return query(l,mid,lson,a,b);
if(a>mid) return query(mid+1,r,rson,a,b);
return MN(query(l,mid,lson,a,b),query(mid+1,r,rson,a,b));
}
inline ll rd()
{
ll ret=0,f=1; char gc=getchar();
while(gc<'0'||gc>'9') {if(gc=='-')f=-f; gc=getchar();}
while(gc>='0'&&gc<='9') ret=ret*10+gc-'0',gc=getchar();
return ret*f;
}
int main()
{
n=rd(),m=rd();
int i;
for(i=1;i<=n;i++) p[++tot].val=rd(),p[tot].org=i;
for(i=1;i<=n;i++) pr[i]=rd();
for(i=1;i<=m;i++)
{
scanf("%s",str);
if(str[0]=='I') op[i]=0,p[++tot].val=rd(),p[tot].org=i+n,pb[i]=rd();
if(str[0]=='D') op[i]=1,p[++tot].val=rd(),p[tot].org=i+n;
if(str[0]=='Q') op[i]=2,p[++tot].val=rd(),p[tot].org=i+n,p[++tot].val=rd(),p[tot].org=i+n;
}
sort(p+1,p+tot+1,cmp);
ref[0]=-1ll<<60;
for(i=1;i<=tot;i++)
{
if(p[i].val>ref[nm]) ref[++nm]=p[i].val,v[nm]=1ll<<60;
if(p[i].org<=n) v[nm]=pr[p[i].org];
else
{
p[i].org-=n;
if(op[p[i].org]==0) pa[p[i].org]=nm;
if(op[p[i].org]==1) pa[p[i].org]=nm;
if(op[p[i].org]==2)
{
if(!pa[p[i].org]) pa[p[i].org]=nm;
else pb[p[i].org]=nm;
}
}
}
build(1,nm,1);
for(i=1;i<=m;i++)
{
if(op[i]==0) v[pa[i]]=pb[i],updata(1,nm,1,pa[i]);
if(op[i]==1) v[pa[i]]=1ll<<60,updata(1,nm,1,pa[i]);
if(op[i]==2) printf("%lld
",ref[query(1,nm,1,pa[i],pb[i])]);
}
return 0;
}