关于splay的教程可以在哔站上查询我校前辈算法讲堂
然后代码对标的是两篇博客(实际上是一种姿势,因为这种代码姿势非常的优美)
Splay入门解析【保证让你看不懂(滑稽)】 - 小蒟蒻yyb - 博客园 (cnblogs.com)
Splay树详解 - 秦淮岸灯火阑珊 - 博客园 (cnblogs.com)
最开始搞完只有两个问题,一个是没有PushDown,这在最开始第一遍检查的时候就发现了这个问题。第二个是边界出了锅。
第二个问题搞了我三个小时。先是lutece上tle了,然后找半天找不出来错,ljj提醒我可以先找个大数据看一下,于是laj搞了个大数据。然后缩小范围搞了个小数据,可是这个数据又很弱,没有搞出锅来,这时chaber在群里说可以先在洛谷上测。遂上洛谷测评,果然给我搞出tle了,然后就下载tle的数据,这个数据很小,但是把锅弄出来了,可惜我没意识到是一个原则性问题,我以为就是一个特判没有考虑到。于是就略微治了标没治本,上去测就wa了,wa掉的数据特别大,很难去具体认识发生了什么问题还把我引到沟里去了。然后ljj提醒我可能是边界出了锅,建议先预设两个虚拟节点。改了以后就过了。ac的那一刻真是有种如释重负的感觉。其实标程一开始就有这个预设了,但我没有意识到会有问题就把删了。再次感谢ljj大佬!!!!!!
1 #include <cstdio> 2 #include <cmath> 3 #include <cstring> 4 #include <cstdlib> 5 #include <queue> 6 #include <stack> 7 #include <vector> 8 #include <iostream> 9 #include "algorithm" 10 using namespace std; 11 const int MAX=3e5+5; 12 int n,root,tot; 13 struct Node{int ff,val,ch[2],cnt,size;}t[MAX]; 14 inline int read(){ 15 int an(0),x=1;char c=getchar(); 16 while (c<'0' || c>'9'){if (c=='-') x=-1;c=getchar();} 17 while (c>='0' && c<='9'){an=an*10+c-'0';c=getchar();} 18 return x*an; 19 } 20 void update(int x){ 21 t[x].size=t[t[x].ch[0]].size+t[t[x].ch[1]].size+t[x].cnt; 22 } 23 void rotate(int x){ 24 int y,z,k; 25 y=t[x].ff;z=t[y].ff;k=(t[y].ch[1]==x); 26 t[z].ch[t[z].ch[1]==y]=x; 27 t[x].ff=z; 28 t[y].ch[k]=t[x].ch[k^1]; 29 t[t[x].ch[k^1]].ff=y; 30 t[x].ch[k^1]=y; 31 t[y].ff=x; 32 update(y);update(x); 33 } 34 void splay(int x,int goal){ 35 int y,z; 36 while (t[x].ff!=goal){ 37 y=t[x].ff;z=t[y].ff; 38 if (z!=goal) 39 (t[z].ch[0]==y)^(t[y].ch[0])?rotate(x):rotate(y); 40 rotate(x); 41 } 42 if (goal==0) root=x; 43 } 44 inline void find(int x){ 45 int u=root; 46 if (!u) return; 47 while (t[u].ch[x>t[u].val] && t[u].val!=x) 48 u=t[u].ch[x>t[u].val]; 49 splay(u,0); 50 } 51 inline void insert(int x){ 52 int u=root,ff=0; 53 while (u && t[u].val!=x){ 54 ff=u; 55 u=t[u].ch[x>t[u].val]; 56 } 57 if (u) t[u].cnt++; 58 else{ 59 u=++tot; 60 if (ff) t[ff].ch[x>t[ff].val]=u; 61 t[u].ch[0]=t[u].ch[1]=0; 62 t[u].ff=ff;t[u].val=x;t[u].cnt=t[u].size=1; 63 } 64 splay(u,0); 65 } 66 inline int Next(int x,int f){ 67 find(x); 68 int u=root; 69 if (t[u].val>x && f) return u; 70 if (t[u].val<x && !f) return u; 71 u=t[u].ch[f]; 72 while (t[u].ch[f^1]) u=t[u].ch[f^1]; 73 return u; 74 } 75 inline void Delete(int x){ 76 int last,next; 77 last=Next(x,0),next=Next(x,1); 78 splay(last,0);splay(next,last); 79 int del=t[next].ch[0]; 80 if (t[del].cnt>1){ 81 t[del].cnt--; 82 splay(del,0); 83 } 84 else t[next].ch[0]=0; 85 } 86 inline int kth(int x){ 87 int u=root,y; 88 if (t[u].size<x) return 0; 89 while (1){ 90 y=t[u].ch[0]; 91 if (x>t[y].size+t[u].cnt){ 92 x-=t[y].size+t[u].cnt; 93 u=t[u].ch[1]; 94 } 95 else{ 96 if (t[y].size>=x) u=y; 97 else return t[u].val; 98 } 99 } 100 } 101 int main(){ 102 freopen ("n.in","r",stdin); 103 freopen ("n.out","w",stdout); 104 int i,j,x,y,an; 105 n=read(); 106 insert(2e9+5); 107 insert(-2e9-5); 108 for (i=1;i<=n;i++){ 109 x=read(),y=read(); 110 if (x==1) insert(y); 111 if (x==2) Delete(y); 112 if (x==3){ 113 find(y); 114 an=t[t[root].ch[0]].size; 115 if (t[root].val<y) an+=t[root].cnt; 116 printf("%d\n",an-1); 117 } 118 if (x==4) printf("%d\n",kth(y+1)); 119 if (x==5) printf("%d\n",t[Next(y,1)].val); 120 } 121 return 0; 122 }