一道平衡树裸题。。
codevs过了 BZOJ显示RE。。郁闷的oier
我已经对每道题都判我RE的BZOJ绝望了
管他的 反正codevs上A了 233
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 |
// <1503.cpp> - 01/30/16 22:23:31 // This file is created by XuYike's black technology automatically. // Copyright (C) 2015 ChangJun High School, Inc. // I don't know what this program is. #include <iostream> #include <vector> #include <algorithm> #include <cstring> #include <cstdio> #include <cmath> using namespace std; typedef long long lol; int getint(){ int res=0,fh=1;char ch=getchar(); while((ch>'9'||ch<'0')&&ch!='-')ch=getchar(); if(ch=='-')fh=-1,ch=getchar(); while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar(); return fh*res; } const int INF=1000000000; const int MAXN=110001; int root,tot,mn,ans,flag; int val[MAXN],size[MAXN]; int s[MAXN][2],f[MAXN]; void update(int a){ int l=s[a][0],r=s[a][1]; size[a]=size[l]+size[r]+1; } void R(int a,int &k){ int p=f[a],g=f[p]; bool l=a==s[p][1],r=!l; if(p==k)k=a; else s[g][s[g][1]==p]=a;f[a]=g; f[s[a][r]]=p;s[p][l]=s[a][r]; f[p]=a;s[a][r]=p; update(p);update(a); } void splay(int a,int &k){ while(a!=k){ int p=f[a]; if(p!=k){ if((s[p][0]==a)^(s[f[p]][0]==p))R(a,k); else R(p,k); } R(a,k); } } void insert(int x){ if(x+flag<mn)return; int a=++tot; val[a]=x;size[a]=1; if(!root){root=a;return;} int now=root; while(s[now][val[a]>val[now]])now=s[now][val[a]>val[now]]; s[now][val[a]>val[now]]=a;f[a]=now; splay(a,root); } int kill(int x){ insert(x); splay(tot,root); int ans=size[s[root][0]]; root=s[root][1]; return ans; } int src(int now,int k){ int l=s[now][0],r=s[now][1]; if(size[r]+1==k)return now; if(size[r]>=k)return src(r,k); return src(l,k-size[r]-1); } int main(){ int n=getint();mn=getint(); char s; insert(INF); while(n--){ cin>>s; if(s=='I')insert(getint()-flag); else if(s=='A')flag+=getint(); else if(s=='S'){flag-=getint();ans+=kill(mn-flag);} else{ int k=getint(); if(k+1>size[root])cout<<-1<<endl; else printf("%d\n",val[src(root,k+1)]+flag); } } cout<<ans; return 0; } |
说点什么