3 条题解
-
0
Guest LV 0 MOD
-
1
推荐一篇好的treap学习文章http://blog.csdn.net/qpswwww/article/details/41454367
还有splay的http://blog.csdn.net/clove_unique/article/details/50630280
不要问我为什么不用指针版本，你看看谁比较好调……不过工作中应该还是指针版本比较实用。#include<bits/stdc++.h> inline void read(int &a) { a=0;char c=getchar(); while(c<'0'||c>'9')c=getchar(); while(c>='0'&&c<='9') { a=(a<<1)+(a<<3)+c-'0'; c=getchar(); } } inline void write(int a) { if(a<0){a=-a;putchar('-');} if(a>9)write(a/10); putchar(a%10+'0'); } const int maxn=300001; int nodenum=0,root=0; struct node { int order,num,sum; int son[2]; inline int comp(int x) { if(x==num)return -1; if(x<num)return 0; return 1; } inline bool operator>(const node&a) { if(order>a.order)return true; return false; } }p[maxn]; inline void newnode(int x) { p[++nodenum].num=x; p[nodenum].son[0]=p[nodenum].son[1]=0; p[nodenum].order=rand()*rand(); p[nodenum].sum=1; } inline void update(int k) { p[k].sum=p[p[k].son[0]].sum+p[p[k].son[1]].sum+1; } inline void rotate(int &k,int d) { int t=p[k].son[d]; p[k].son[d]=p[t].son[d^1]; p[t].son[d^1]=k; update(k);update(t); k=t; } inline void insert(int &k,int x) { if(!k) { newnode(x); k=nodenum; } else { int d=p[k].comp(x); if(d==-1)d=0; insert(p[k].son[d],x); if(p[p[k].son[d]]>p[k])rotate(k,d); else update(k); } } inline void remove(int &k,int x) { int d=p[k].comp(x),t; if(d==-1) { if(!(p[k].son[0])&&!(p[k].son[1])) { k=0; return ; } if(!(p[k].son[0]*p[k].son[1])) { k=p[k].son[0]+p[k].son[1]; return ; } else { if(p[p[k].son[0]]>p[p[k].son[1]])t=0; else t=1; rotate(k,t); remove(p[k].son[t^1],x); update(k); return ; } } else { remove(p[k].son[d],x); update(k); return ; } } inline int query(int k,int x,int has) { if(p[p[k].son[0]].sum+1+has==x)return p[k].num; if(p[p[k].son[0]].sum+1+has>x)return query(p[k].son[0],x,has); else return query(p[k].son[1],x,has+p[p[k].son[0] ].sum+1); } int main() { srand(time(NULL)); p[0].num=p[0].order=-INT_MAX;p[0].sum=0; int m,opt,x; read(m); while(m--) { read(opt);read(x); if(opt==1)insert(root,x); if(opt==2)remove(root,x); if(opt==3){write(query(root,x,0));printf("\n");} } return 0; }-
Randle @ 2017-12-08 18:08:31
第一次写treap，写了三个多小时。被删除操作时候的第三种情况，旋转之后走反方向了……不过还是很开心。是noip爆炸之后的第一个新学知识点。
-
-
0
just remain the code,dont be confused!!!
#include<bits/stdc++.h> inline void read(int &a) { a=0;int b=1;char c=getchar(); while(c<'0'||c>'9') { if(c=='-')b=-1; c=getchar(); } while(c>='0'&&c<='9') { a=(a<<1)+(a<<3)+c-'0'; c=getchar(); } a*=b; } inline void write(int a) { if(a<0){a=-a;putchar('-');} if(a>9)write(a/10); putchar(a%10+'0'); } const int maxn=300001; int nodenum=0,root=0; struct node { int order,num,sum,repeat; int son[2]; inline int comp(int x) { if(num==x)return -1; if(num>x)return 0; return 1; } inline bool operator>(const node&b) { if(order>b.order)return true; return false; } }p[maxn<<1]; inline void update(int k) { p[k].sum=p[p[k].son[0]].sum+p[p[k].son[1]].sum+p[k].repeat; } inline void newnode(int x) { p[++nodenum].num=x; p[nodenum].order=rand()*rand(); p[nodenum].son[0]=p[nodenum].son[1]=0; p[nodenum].sum=p[nodenum].repeat=1; } inline void rotate(int &k,int d) { int t=p[k].son[d]; p[k].son[d]=p[t].son[d^1]; p[t].son[d^1]=k; update(k);update(t); k=t; } void insert(int &k,int x) { if(!k) { newnode(x); k=nodenum; return ; } int d=p[k].comp(x); if(d==-1){++p[k].repeat;return ;} insert(p[k].son[d],x); if(p[p[k].son[d]]>p[k])rotate(k,d); else update(k); } void remove(int &k,int x) { int d=p[k].comp(x); if(d==-1) { if(p[k].repeat>1){--p[k].repeat;return ;} if(!(p[k].son[0])&&!(p[k].son[1])){k=0;return ;} if(!(p[k].son[0]*p[k].son[1])){k=p[k].son[0]+p[k].son[1];return ;} else { int r; if(p[p[k].son[0]]>p[p[k].son[1]])r=0; else r=1; rotate(k,r); remove(p[k].son[r^1],x); update(k); } } else { remove(p[k].son[d],x); update(k); return ; } } int rank(int &k,int x,int has) { int d=p[k].comp(x); if(d==-1)return has+p[p[k].son[0]].sum+1; if(d==0)return rank(p[k].son[0],x,has); if(d==1)return rank(p[k].son[1],x,has+p[p[k].son[0]].sum+p[k].repeat); } int _rank(int &k,int x,int has) { int d=p[k].comp(x); if(d==-1)return has+p[p[k].son[0]].sum+p[k].repeat; if(d==0)return rank(p[k].son[0],x,has); if(d==1)return rank(p[k].son[1],x,has+p[p[k].son[0]].sum+p[k].repeat); } int kth(int &k,int x,int has) { if(k==0)return 0; if(x>=has+p[p[k].son[0]].sum+1&&x<=has+p[p[k].son[0]].sum+p[k].repeat)return p[k].num; if(x<=has+p[p[k].son[0]].sum)return kth(p[k].son[0],x,has); else return kth(p[k].son[1],x,has+p[p[k].son[0]].sum+p[k].repeat); } int main() { freopen("test.txt","r",stdin); srand(time(NULL)); p[0].son[0]=p[0].son[1]=p[0].num=p[0].order=p[0].repeat=0; int m,opt,x; read(m); while(m--) { read(opt);read(x); if(opt==1)insert(root,x); if(opt==2)remove(root,x); if(opt==3)write(rank(root,x,0)); if(opt==4)write(kth(root,x,0)); if(opt==5)write(kth(root,rank(root,x,0)-1,0)); if(opt==6)write(kth(root,_rank(root,x,0)+1,0)); if(opt>=3)printf("\n"); } return 0; } -
0
真的暴力，敢于直面惨淡的人生，敢于直视淋漓的鲜血！！！
#include<bits/stdc++.h> inline void read(int &a) { a=0;char c=getchar(); while(c<'0'||c>'9')c=getchar(); while(c>='0'&&c<='9') { a=(a<<1)+(a<<3)+c-'0'; c=getchar(); } } inline void write(int a) { if(a<0){putchar('-');a=-a;} if(a>9)write(a/10); putchar(a%10+'0'); } int line[100001],num=0; inline int find(int x) { int l=1,r=num; while(l!=r) { int mid=l+r>>1; if(line[mid]==x)return mid; if(line[mid]>x)r=mid-1; else l=mid+1; } return l; } int main() { memset(line,0,sizeof(line)); int m;int order,x; read(m); while(m--) { read(order);read(x); if(order==1) { line[++num]=x; int d=num; while(d-1&&line[d]<line[d-1]){std::swap(line[d],line[d-1]);--d;} } if(order==2) { int k=find(x); line[k]=0; for(int i=k;i<=num-1;i++)line[i]=line[i+1]; line[num]=0; --num; } if(order==3) { write(line[x]);puts(""); } } return 0; }
Guest
LV 0
MOD
- 1