「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
Sample Output
1
HINT
数据保证n<=10^5,m<=3*10^5
其余整数均不超过long的范围
数据保证任意时刻树中key和priority均不相同
题解
首先询问的两个点的key是一个区间
则lca的key是在这个区间内pri最小的
那么就变成了维护一个集合
支持查询区间最值，加入删除元素
线段树/平衡树
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 |
#include<set> #include<map> #include<ctime> #include<queue> #include<cmath> #include<cstdio> #include<vector> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define inf 2147483647 using namespace std; int read() { int 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; } int n,m,tot; int v[400005],p[400005],a[400005],b[400005]; map<int,int>pid,kid; char ch[300005][2]; vector<pair<int,int> >q; struct seg{ int l,r,mn; }t[1600005]; void build(int k,int l,int r) { t[k].l=l;t[k].r=r; if(l==r){t[k].mn=inf;return;} int mid=(l+r)>>1; build(k<<1,l,mid); build(k<<1|1,mid+1,r); t[k].mn=min(t[k<<1].mn,t[k<<1|1].mn); } int query(int k,int x,int y) { int l=t[k].l,r=t[k].r,mid=(l+r)>>1; if(x==l&&y==r)return t[k].mn; if(y<=mid)return query(k<<1,x,y); else if(x>mid)return query(k<<1|1,x,y); else return min(query(k<<1,x,mid),query(k<<1|1,mid+1,y)); } void insert(int k,int x,int val) { int l=t[k].l,r=t[k].r,mid=(l+r)>>1; if(l==r){t[k].mn=val;return;} if(x<=mid)insert(k<<1,x,val); else insert(k<<1|1,x,val); t[k].mn=min(t[k<<1].mn,t[k<<1|1].mn); } int main() { n=read();m=read();tot=n; for(int i=1;i<=n;i++)v[i]=read(); for(int i=1;i<=n;i++)p[i]=read(); for(int i=1;i<=n;i++) q.push_back(make_pair(v[i],p[i])); for(int i=1;i<=m;i++) { scanf("%s",ch[i]+1); a[i]=read(); if(ch[i][1]!='D')b[i]=read(); if(ch[i][1]=='I') { v[++tot]=a[i],p[tot]=b[i]; q.push_back(make_pair(a[i],b[i])); } } sort(q.begin(),q.end()); build(1,1,tot); for(int i=1;i<=n;i++) { kid[v[i]]=pid[p[i]]=lower_bound(q.begin(),q.end(),make_pair(v[i],p[i]))-q.begin()+1; insert(1,kid[v[i]],p[i]); } for(int i=1;i<=m;i++) { if(ch[i][1]=='I') { kid[a[i]]=pid[b[i]]=lower_bound(q.begin(),q.end(),make_pair(a[i],b[i]))-q.begin()+1; insert(1,kid[a[i]],b[i]); } else if(ch[i][1]=='D')insert(1,kid[a[i]],inf); else { int t1=kid[a[i]],t2=kid[b[i]]; if(t1>t2)swap(t1,t2); int p=query(1,t1,t2); printf("%d\n",q[pid[p]-1].first); } } return 0; } |
Subscribe
计数器 9303046
OI 课件=>
OI 课件=>