悬一关
by _zqh_ @ 2024-02-22 10:04:21
@[TengMax](/user/731704) 你这个splay过于阴间了啊
看看我的,Solay写什么zigzag，直接写rotate
```
#include <bits/stdc++.h>
#define rep(i,j,k) for(int i=(j);i<=(k);++i)
#define per(i,j,k) for(int i=(j);i>=(k);--i)
#define pb push_back
#define yn(x) printf(x?"Yes\n":"No\n")
using namespace std;
const int N=100010,inf=1e9;
typedef pair<int,int> pii;
typedef long long ll;
typedef unsigned long long ull;
int n,m,delta;
struct node{
int s[2],p,v,size;
void init(int _v,int _p){
v=_v,p=_p,size=1;
}
}tr[N];
int root,idx;
void pushup(int u){
tr[u].size=tr[tr[u].s[0]].size+tr[tr[u].s[1]].size+1;
}
void rotate(int x){
int y=tr[x].p,z=tr[y].p,k=tr[y].s[1]==x;
tr[z].s[tr[z].s[1]==y]=x,tr[x].p=z;
tr[y].s[k]=tr[x].s[k^1],tr[tr[x].s[k^1]].p=y;
tr[x].s[k^1]=y,tr[y].p=x,pushup(y),pushup(x);
}
void splay(int x,int k){
while(tr[x].p!=k){
int y=tr[x].p,z=tr[y].p;
if(z!=k)if((tr[y].s[1]==x)^(tr[z].s[1]==y))rotate(x);
else rotate(y);rotate(x);
}
if(!k)root=x;
}
int insert(int v){
int u=root,p=0;
while(u)p=u,u=tr[u].s[v>tr[u].v];
u=++idx;if(p)tr[p].s[v>tr[p].v]=u;
tr[u].init(v,p),splay(u,0);return u;
}
int get(int v){
int u=root,res;
while(u){
if(tr[u].v>=v)res=u,u=tr[u].s[0];
else u=tr[u].s[1];
}
return res;
}
int get_k(int k){
int u=root;
while(u){
if(tr[tr[u].s[0]].size>=k)u=tr[u].s[0];
else if(tr[tr[u].s[0]].size+1==k)return tr[u].v;
else k-=tr[tr[u].s[0]].size+1,u=tr[u].s[1];
}return -1;
}
int main()
{
scanf("%d%d",&n,&m);
int l=insert(-inf),r=insert(inf),tot=0;
while(n--){
char op[2];int k;
scanf("%s%d",op,&k);
if(*op=='I'){if(k>=m)k-=delta,insert(k),tot++;}
else if(*op=='A')delta+=k;
else if(*op=='S'){
delta-=k,r=get(m-delta);
splay(r,0),splay(l,r),tr[l].s[1]=0;
pushup(l),pushup(r);
}else{
if(tr[root].size-2<k)printf("-1\n");
else printf("%d\n",get_k(tr[root].size-k)+delta);
}
}
printf("%d\n",tot-(tr[root].size-2));
return 0;
}
```
by rsy_ @ 2024-02-22 17:04:13
@[rsy_](/user/550775) 别忘了你的Splay在普通平衡树中没过哦
by chenzhaoxu2027 @ 2024-02-22 17:36:29
吃瓜
by yangmeinaixi @ 2024-02-22 19:20:17
@[rsy_](/user/550775) 如果我说rotate我不会写捏？
by _zqh_ @ 2024-02-22 20:42:46
我调了快一天了，都快郁闷到自闭了
by _zqh_ @ 2024-02-22 20:51:42
@[TengMax](/user/731704) 看我的a
by rsy_ @ 2024-02-25 16:28:17