【bzoj2770】YY的Treap

2015.03.28 10:35 Sat | 3次阅读 | 旧日oi | 固定链接 | 源码

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
其余整数均不超过long的范围
数据保证任意时刻树中key和priority均不相同

题解

到现在为止,这题只有24个人a,但是这题并不是很难……昨天这题是考试题,写了一个裸treap+暴力查询,也得了80分,今天把正解写了
因为priority不是随机分配的,所以treap有可能退化成一条链。
考虑到一个性质,treap的中序遍历恰好是元素按k值从小到大的一个排列,而两个点u,v的lca就应该是位于ku,kv之间w值最小的点(默认ku<kv,比ku小的,一定在u的子树中,比kv大的,一定在u,v的lca的上方,在ku,kv之间的w值不是最小的点,一定属于lca的某一个子树上。
所以这道题就转化为了线段树维护,因为k值很大,离散化之后进行处理,建立一颗维护最小值的线段树,同时要记录真实的k值,写起来还有点麻烦……

我的程序

#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<vector>
#include<bitset>
#include<stack>
#include<ctime>
#include<cmath>
#include<queue>
#include<set>
#include<map>
#define maxn 100010
#define ll long long
#define mod 1000000007
#define inf 0x3f3f3f3f
using namespace std;
ll read()
{
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
ll n,m,x,y;
ll a[maxn],b[maxn];
struct Question{
    char s[5];
    ll k,w;
}q[maxn*3];
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
ll val[maxn*16];
ll real[maxn*16];
ll num[maxn*4],cnt;
void pushup(int rt)
{
    if(val[rt<<1]<val[rt<<1|1]) 
    {
        real[rt]=real[rt<<1];
        val[rt]=val[rt<<1];
    }
    else
    {
        real[rt]=real[rt<<1|1];
        val[rt]=val[rt<<1|1];
    }
}
void insert(int l,int r,int rt,int x,ll c,ll k)
{
    if(l==r)
    {
        val[rt]=c;
        real[rt]=k;
        return;
    }
    int mid=(l+r)>>1;
    if(x<=mid) insert(lson,x,c,k);
    else insert(rson,x,c,k);
    pushup(rt);
}
pair<ll,ll> query(int l,int r,int rt,int x,int y)
{
    if(x<=l&&y>=r) return make_pair(val[rt],real[rt]);
    int mid=l+r>>1;
    if(x>mid) return query(rson,x,y);
    else if(y<=mid) return query(lson,x,y);
    else
    {
        pair<ll,ll> t1=query(rson,mid+1,y);
        pair<ll,ll> t2=query(lson,x,mid);
        if(t1.first>t2.first) return t2;
        else return t1;
    }
}
int main()
{
    n=read();m=read();
    for(int i=1;i<=n;i++) a[i]=read(),num[++cnt]=a[i];
    for(int i=1;i<=n;i++) b[i]=read();
    for(int i=1;i<=m;i++)
    {
        scanf("%s",q[i].s);q[i].k=read();
        if(q[i].s[0]=='I') 
        {
            q[i].w=read();
            num[++cnt]=q[i].k;
        }
        else if(q[i].s[0]=='Q') q[i].w=read();
    }
    sort(num+1,num+cnt+1);
    memset(val,0x3f,sizeof(val));
    for(int i=1;i<=n;i++) 
    {
        ll tmp=a[i];
        a[i]=lower_bound(num+1,num+cnt+1,a[i])-num;
        insert(1,n+m,1,a[i],b[i],tmp);
    }
    for(int i=1;i<=m;i++)
    {
        if(q[i].s[0]=='I') 
        {
            ll tmp=q[i].k;
            q[i].k=lower_bound(num+1,num+cnt+1,q[i].k)-num;
            insert(1,n+m,1,q[i].k,q[i].w,tmp);
        }
        else if(q[i].s[0]=='D')
        {
            ll tmp=q[i].k;
            q[i].k=lower_bound(num+1,num+cnt+1,q[i].k)-num;
            insert(1,n+m,1,q[i].k,0x3f3f3f3f3f3f3f3fll,tmp);
        }
        else
        {
            q[i].k=lower_bound(num+1,num+cnt+1,q[i].k)-num;
            q[i].w=lower_bound(num+1,num+cnt+1,q[i].w)-num;
            if(q[i].k>q[i].w) swap(q[i].k,q[i].w);
            printf("%lld\n",query(1,n+m,1,q[i].k,q[i].w).second);
        }
    }
    return 0;
}```