2 条题解
-
0
scy的splay代码：
#include<bits/stdc++.h> using namespace std; struct trnode{int d,n,c,f,ch[2];}tr[110000];int len,root; void upd(int x){ tr[x].c=tr[tr[x].ch[0]].c+tr[x].n+tr[tr[x].ch[1]].c;} void add(int d,int f) { tr[++len]=trnode{d,1,1,f,0,0}; tr[f].ch[tr[f].d<d]=len; if(f==0)root=len; } void rotate(int x) { int y=tr[x].f,z=tr[y].f,w=(tr[y].ch[1]==x),v=tr[x].ch[1-w]; tr[y].ch[w]=v;tr[v].f=y; tr[x].ch[1-w]=y;tr[y].f=x; tr[z].ch[tr[z].ch[1]==y]=x;tr[x].f=z; upd(y);upd(x); } void splay(int x,int rt) { while(tr[x].f!=rt) { int y=tr[x].f,z=tr[y].f; if(z!=rt)((tr[z].ch[1]==y)==(tr[y].ch[1]==x))?rotate(y):rotate(x); rotate(x); } if(rt==0)root=x; } int findip(int d) { int x=root; while(tr[x].d!=d&&tr[x].ch[tr[x].d<d])x=tr[x].ch[tr[x].d<d]; return x; } int findnext(int d,int w) { int x=findip(d); if(tr[x].d>d&&w==1) return x; if(tr[x].d<d&&w==0) return x; splay(x,0);x=tr[x].ch[w];while(tr[x].ch[1-w])x=tr[x].ch[1-w]; return x; } void ins(int d) { if(root==0) add(d,0); else { int x=findip(d); if(tr[x].d==d) tr[x].n++,splay(x,0); else add(d,x),splay(len,0); } } int findkth(int k) { int x=root; while(1) { if(k<=tr[tr[x].ch[0]].c)x=tr[x].ch[0]; else if(k>tr[tr[x].ch[0]].c+tr[x].n) k-=tr[tr[x].ch[0]].c+tr[x].n,x=tr[x].ch[1]; else {splay(x,0);return x;} } } int main() { int n,minx;scanf("%d%d",&n,&minx); root=len=0;int ans=0,t=0; for(int i=1;i<=n;i++) { char s[10];int x;scanf("%s%d",s,&x); if(s[0]=='I'){ if(x>=minx)ins(x-t);} else if(s[0]=='A')t+=x; else if(s[0]=='S') { t-=x;int p=findnext(minx-t-1,1); if(p==0){ans+=tr[root].c;root=len=t=0;continue;} splay(p,0);if(tr[p].ch[0]){ans+=tr[tr[p].ch[0]].c;tr[p].ch[0]=0;upd(p);} } else if(s[0]=='F') { if(x>tr[root].c) printf("-1\n"); else printf("%d\n", tr[findkth(tr[root].c-x+1)].d+t); } } printf("%d\n",ans);return 0; } -
0
huangzheng
LV 6
@ 2025-10-8 17:03:55
scy的splay代码：
#include<bits/stdc++.h> using namespace std; struct trnode{int d,n,c,f,ch[2];}tr[110000];int len,root; void upd(int x){ tr[x].c=tr[tr[x].ch[0]].c+tr[tr[x].ch[1]].c+tr[x].n;} void add(int d,int f) { tr[++len]=trnode{d,1,1,f,0,0}; tr[f].ch[tr[f].d<d]=len; if(f==0)root=len; } void rotate(int x) { int y=tr[x].f,z=tr[y].f,w=(tr[y].ch[1]==x),v=tr[x].ch[1-w]; tr[y].ch[w]=v;tr[v].f=y; tr[x].ch[1-w]=y;tr[y].f=x; tr[z].ch[tr[z].ch[1]==y]=x;tr[x].f=z; upd(y);upd(x); } void splay(int x,int rt) { while(tr[x].f!=rt) { int y=tr[x].f,z=tr[y].f; if(z!=rt)((tr[z].ch[1]==y)==(tr[y].ch[1]==x))?rotate(y):rotate(x); rotate(x); } if(rt==0)root=x; } int findip(int d) { int x=root; while(tr[x].d!=d&&tr[x].ch[tr[x].d<d])x=tr[x].ch[tr[x].d<d]; return x; } int findnext(int d,int w) { int x=findip(d); if(tr[x].d>d&&w==1) return x; if(tr[x].d<d&&w==0) return x; splay(x,0);x=tr[x].ch[w]; while(tr[x].ch[1-w])x=tr[x].ch[1-w]; return x; } void ins(int d) { if(root==0) add(d,0); else { int x=findip(d); if(tr[x].d==d) tr[x].n++,splay(x,0); else add(d,x),splay(len,0); } } int findkth(int k) { int x=root; while(1) { if(k<=tr[tr[x].ch[0]].c)x=tr[x].ch[0]; else if(k>tr[tr[x].ch[0]].c+tr[x].n) k-=tr[tr[x].ch[0]].c+tr[x].n,x=tr[x].ch[1]; else {splay(x,0);return x;} } } int main() { int n,minx;scanf("%d%d",&n,&minx); root=len=0; int ans=0,t=0; for(int i=1;i<=n;i++) { char s[10];int x;scanf("%s%d",s,&x); if(s[0]=='I'){ if(x>=minx)ins(x-t);} else if(s[0]=='A')t+=x; else if(s[0]=='S') { t-=x; int p=findnext(minx-t-1,1); if(p==0){ans+=tr[root].c;root=len=t=0;continue;} splay(p,0); if(tr[p].ch[0]) { ans+=tr[tr[p].ch[0]].c; tr[p].ch[0]=0; upd(p); } } else if(s[0]=='F') { if(x>tr[root].c) printf("-1\n"); else printf("%d\n", tr[findkth(tr[root].c-x+1)].d+t); } } printf("%d\n",ans); return 0; }
- 1