注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

n+e

NewWeb:http://trinkle.is-programmer.com/

 
 
 

日志

 
 

[BZOJ2770]YY的Treap  

2015-06-20 19:35:46|  分类: BZOJ |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

2770: YY的Treap

Time Limit: 10 Sec  Memory Limit: 128 MB
Submit: 132  Solved: 35
[Submit][Status][Discuss]

Description

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

Input

第一行两个整数nm

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

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

接下m行,每行一条命令

I A B,插入一个元素,keyA, priorityB

D A,删除一个元素,keyA

Q A B,询问key分别为ABLCAkey

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均不相同

Solution

离线离散化key,从而不需要写平衡树。
把key从小到大排序,key_l和key_r的lca为key_l<=key_i<=key_r且priority_i最小的i
线段树解决。

Code

/**************************************************************
    Problem: 2770
    User: wjy1998
    Language: C++
    Result: Accepted
    Time:2264 ms
    Memory:25252 kb
****************************************************************/
 
#include<cstdio>
#include<cstring>
#include<algorithm>
char ch,B[1<<15],*S=B,*T=B;
#define getc() (S==T&&(T=(S=B)+fread(B,1,1<<15,stdin),S==T)?0:*S++)
int aa,bb;int F(){
    while(ch=getc(),(ch<'0'||ch>'9')&&ch!='-');ch=='-'?aa=bb=0:(aa=ch-'0',bb=1);
    while(ch=getc(),ch>='0'&&ch<='9')aa=aa*10+ch-'0';return bb?aa:-aa;
}
#define N 400010
int n,m,d,k,x,tot,cnt=1;char op;
int t[1<<20],val[N],y[N];
struct Q{int op,a,b;}q[N];
struct D{int x,n;}a[N<<2];
bool operator<(const D&a,const D&b){return a.x<b.x;}
int main(){
    n=F(),m=F();
    for(int i=1;i<=n;i++)q[i].a=F();
    for(int i=1;i<=n;i++)q[i].b=F();
    for(int i=n+1;i<=n+m;i++){
        while(op=getc(),op<'A'||op>'Z');
        if(op=='Q')q[i].op=2;
        else if(op=='D')q[i].op=1;
        q[i].a=F();if(q[i].op!=1)q[i].b=F();
    }
    for(int i=1;i<=m+n;i++)if(q[i].op==2)a[++tot]=(D){q[i].a,i},a[++tot]=(D){q[i].b,-i};
    else a[++tot]=(D){q[i].a,i};
    std::sort(a+1,a+1+tot);
    for(int i=1;i<=tot;i++){
        if(a[i].n>0)q[a[i].n].a=cnt;
        else q[-a[i].n].b=cnt;
        if(a[i].x!=a[i+1].x)y[cnt++]=a[i].x;
    }
    for(d=1;d<=cnt+1;d<<=1);
    memset(val,127,sizeof(val));
    for(int i=0;i<d;i++)t[i+d]=i;
    for(int i=1;i<=n+m;i++)
    if(q[i].op==0){
        val[q[i].a]=q[i].b;
        for(int o=d+q[i].a;o>>=1;t[o]=t[o<<1|(val[t[o<<1]]>val[t[o<<1|1]])]);
    }else if(q[i].op==1){
        val[q[i].a]=val[0];
        for(int o=d+q[i].a;o>>=1;t[o]=t[o<<1|(val[t[o<<1]]>val[t[o<<1|1]])]);
    }else{
        int l=q[i].a,r=q[i].b,ans=0;
        if(l>r)ans=l,l=r,r=ans,ans=0;
        for(l+=d-1,r+=d+1;l^r^1;l>>=1,r>>=1)
        ~l&1&&val[t[l^1]]<val[ans]?ans=t[l^1]:1,
         r&1&&val[t[r^1]]<val[ans]?ans=t[r^1]:1;
        printf("%d\n",y[ans]);
    }
}
  评论这张
 
阅读(167)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018