[Treap模拟线段树] Codechef COT5 Count on a Treap

2019-11-06 08:35:12

字体：大中小

来源：转载

供稿：网友

传送门

Description

在计算机科学中，Treap根据键值是一棵二叉搜索树，根据权值是一个堆（本题中为大根堆）。你的任务是维护一棵Treap，支持以下操作

0 k w 插入一个新节点，键值为k，权值为w。1 k 删除键值为k的节点。2 ku kv 输出键值为ku和kv的两个点之间的路径长度。

保证没有两个点键值相同或权值相同，并且删除一个点时该点存在。

Analysis

考虑如何是如何建Treap的将所有点按键值从小到大排序每次找出权值最大的点作为根左右递归建子树所有点离线按键值排序树上两点的lca就是在序列上两点之间的权值最大的点只需求一个点到根的距离就行了从一个点分别向左右每次找第一个比当前点键值大的点就是该点的祖先向左向右是独立的就是求向左的上升序列和向右的上升序列长度这个东西怎么维护 @BZOJ2957

#include<cstdio>#include<cstdlib>#include<algorithm>#include<map>using namespace std;typedef unsigned int uint;typedef pair<uint,int> abcd;inline char nc(){ static char buf[100000],*p1=buf,*p2=buf; return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;}inline void read(int &x){ char c=nc(),b=1; for (;!(c>='0' && c<='9');c=nc()) if (c=='-') b=-1; for (x=0;c>='0' && c<='9';x=x*10+c-'0',c=nc()); x*=b;}inline void read(uint &x){ char c=nc(),b=1; for (;!(c>='0' && c<='9');c=nc()) if (c=='-') b=-1; for (x=0;c>='0' && c<='9';x=x*10+c-'0',c=nc()); x*=b;}const int N=200005;int Q,d[N];uint a[N],b[N];map<uint,uint> Map;uint sx[N],sy[N]; int n;inline int Bin(uint x){ return lower_bound(sx+1,sx+n+1,x)-sx;}struct MAX{ abcd T[N<<2]; inline void Build(int x,int l,int r){ if (l==r) return void(T[x]=abcd(0,l)); int mid=(l+r)>>1; Build(x<<1,l,mid); Build(x<<1|1,mid+1,r); T[x]=max(T[x<<1],T[x<<1|1]); } inline void modify(int x,int l,int r,int t,uint a){ if (l==r) return void(T[x]=abcd(a,t)); int mid=(l+r)>>1; if (t<=mid) modify(x<<1,l,mid,t,a); else modify(x<<1|1,mid+1,r,t,a); T[x]=max(T[x<<1],T[x<<1|1]); } inline abcd query(int x,int l,int r,int ql,int qr){ if (ql<=l && r<=qr) return T[x]; int mid=(l+r)>>1; abcd ret=abcd(0,0); if (ql<=mid) ret=max(ret,query(x<<1,l,mid,ql,qr)); if (qr>mid) ret=max(ret,query(x<<1|1,mid+1,r,ql,qr)); return ret; } inline void Modify(int t,uint a){ modify(1,1,n,t,a); } inline int Query(int l,int r){ return query(1,1,n,l,r).second; }}Max;struct SEG{ int T[N<<2]; uint M[N<<2]; int l[N<<2],r[N<<2]; inline void Build(int x,int _l,int _r){ l[x]=_l; r[x]=_r; T[x]=1; M[x]=0; if (l[x]==r[x]) return; int mid=(_l+_r)>>1; Build(x<<1,_l,mid); Build(x<<1|1,mid+1,_r); } inline int find(int x,uint v){ if (l[x]==r[x]) return v<M[x]; if (M[x<<1]<v) return find(x<<1|1,v); else return find(x<<1,v)+T[x]-T[x<<1]; } inline void update(int x){ M[x]=max(M[x<<1],M[x<<1|1]); T[x]=T[x<<1]+find(x<<1|1,M[x<<1]); } inline void modify(int x,int t,uint a){ if (l[x]==r[x]) { T[x]=1; M[x]=a; return; } int mid=(l[x]+r[x])>>1; if (t<=mid) modify(x<<1,t,a); else modify(x<<1|1,t,a); update(x); } int ret; uint last; inline void query(int x,int ql,int qr){ if (ql<=l[x] && r[x]<=qr){ ret+=find(x,last); last=max(last,M[x]); return; } int mid=(l[x]+r[x])>>1; if (ql<=mid) query(x<<1,ql,qr); if (qr>mid) query(x<<1|1,ql,qr); } inline void Modify(int t,uint a){ modify(1,t,a); } inline int Query(int t,uint a){ if (t==n) return 1; ret=1; last=a; query(1,t+1,n); return ret; }}Seg,rSeg;inline int Dist(int p){ return Seg.Query(p,Map[sx[p]])+rSeg.Query(n-p+1,Map[sx[p]])-2;}int main(){ freopen("COT5.in","r",stdin); freopen("COT5.out","w",stdout); read(Q); for (int i=1;i<=Q;i++){ read(d[i]); read(a[i]); if (d[i]==0) read(b[i]),sx[++n]=a[i]; if (d[i]==2) read(b[i]); } sort(sx+1,sx+n+1); Max.Build(1,1,n); Seg.Build(1,1,n); rSeg.Build(1,1,n); for (int i=1;i<=Q;i++) if (d[i]==0){ Map[a[i]]=b[i]; int pos=Bin(a[i]); Max.Modify(pos,b[i]); Seg.Modify(pos,b[i]); rSeg.Modify(n-pos+1,b[i]); }else if (d[i]==1){ int pos=Bin(a[i]); Max.Modify(pos,0); Seg.Modify(pos,0); rSeg.Modify(n-pos+1,0); }else{ int p1=Bin(a[i]),p2=Bin(b[i]); if (p1>p2) swap(p1,p2); int lca=Max.Query(p1,p2),ans=0; ans=Dist(p1)+Dist(p2)-2*Dist(lca); PRintf("%d/n",ans); } return 0;}

上一篇：lua面向对象编程之点号与冒号的差异详细比较

下一篇：订单可视化（智能制造、流程再造、企业信息化）第一篇缘起