3224: Tyvj 1728 普通平衡树
Time Limit: 10 Sec Memory Limit: 128 MBSubmit: 20328 Solved: 8979[][][]Description
您需要写一种数据结构(可参考题目标题),来维护一些数,其中需要提供以下操作:
1. 插入x数2. 删除x数(若有多个相同的数,因只删除一个)3. 查询x数的排名(若有多个相同的数,因输出最小的排名)4. 查询排名为x的数5. 求x的前驱(前驱定义为小于x,且最大的数)6. 求x的后继(后继定义为大于x,且最小的数)Input
第一行为n,表示操作的个数,下面n行每行有两个数opt和x,opt表示操作的序号(1<=opt<=6)
Output
对于操作3,4,5,6每行输出一个数,表示对应答案
Sample Input
10 1 106465 4 1 1 317721 1 460929 1 644985 1 84185 1 89851 6 81968 1 492737 5 493598Sample Output
106465 84185 492737HINT
1.n的数据范围:n<=1000002.每个数的数据范围:[-2e9,2e9]
Source
[ ][ ][ ]
刷点模板题。。发现自己treap忘光了。。
没什么好说的,题目里的排名是指从小到大,其余没有什么坑点,那些作为函数哪些作为过程要想清楚。
比无旋treap快,所以说到现在都没有遇上必须用无旋treap的题,除了WC的那道可持久化treap。
1 #include2 #include 3 #include 4 #include 5 #define rep(i,l,r) for (int i=l; i<=r; i++) 6 using namespace std; 7 8 const int N=100100,inf=1000000000; 9 int n,rt,nd,ans,op,x,ls[N],rs[N],sz[N],h[N],v[N],w[N];10 11 void rrot(int &x){12 int y=ls[x]; ls[x]=rs[y]; rs[y]=x;13 sz[y]=sz[x]; sz[x]=sz[ls[x]]+sz[rs[x]]+w[x]; x=y;14 }15 16 void lrot(int &x){17 int y=rs[x]; rs[x]=ls[y]; ls[y]=x;18 sz[y]=sz[x]; sz[x]=sz[ls[x]]+sz[rs[x]]+w[x]; x=y;19 }20 21 void ins(int &x,int k){22 if (!x){23 x=++nd; v[x]=k; h[x]=rand(); sz[x]=w[x]=1; return;24 }25 sz[x]++;26 if (v[x]==k) { w[x]++; return; }27 if (k 1) { w[x]--; sz[x]--; return; }34 if (!ls[x] || !rs[x]) { x=ls[x]+rs[x]; return; }35 if (h[ls[x]] =k) return v[x];51 if (sz[ls[x]]>=k) return find(ls[x],k);52 else return find(rs[x],k-sz[ls[x]]-w[x]);53 }54 55 void pre(int x,int k){56 if (!x) return;57 if (v[x] k) ans=min(ans,v[x]),nxt(ls[x],k); else nxt(rs[x],k);63 }64 65 int main(){66 freopen("bzoj3224.in","r",stdin);67 freopen("bzoj3224.out","w",stdout);68 for (scanf("%d",&n); n--; ){69 scanf("%d%d",&op,&x);70 if (op==1) ins(rt,x);71 if (op==2) del(rt,x);72 if (op==3) printf("%d\n",get(rt,x));73 if (op==4) printf("%d\n",find(rt,x));74 if (op==5) ans=0,pre(rt,x),printf("%d\n",ans);75 if (op==6) ans=inf,nxt(rt,x),printf("%d\n",ans);76 }77 return 0;78 }
懒得写这么多怎么办,上STL-vector,所有操作都能在库函数里找到。
据说单次操作理论复杂度是线性的,实际上可以看作是根号的,但这里也只慢了一倍而已。
1 #include2 #include 3 #include 4 #define rep(i,l,r) for (int i=l; i<=r; i++) 5 using namespace std; 6 7 const int inf=1000000000; 8 int n,op,x; 9 vector a;10 11 int main(){12 scanf("%d",&n); a.reserve(200000);13 rep(i,1,n){14 scanf("%d%d",&op,&x);15 if (op==1) a.insert(upper_bound(a.begin(),a.end(),x),x);16 if (op==2) a.erase(lower_bound(a.begin(),a.end(),x));17 if (op==3) printf("%d\n",int(lower_bound(a.begin(),a.end(),x)-a.begin()+1));18 if (op==4) printf("%d\n",a[x-1]);19 if (op==5) printf("%d\n",*(--lower_bound(a.begin(),a.end(),x)));20 if (op==6) printf("%d\n",*upper_bound(a.begin(),a.end(),x));21 }22 return 0;23 }