我的代码(以前)就被卡死了
```
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;
const int MAXN = 1e5 + 5;
int val[MAXN] , pr[MAXN] , sz[MAXN] , lc[MAXN] , rc[MAXN] , addv[MAXN];
int root , cnt;
int minn , n;
int ans;
inline void up(int o){sz[o] = sz[lc[o]] + sz[rc[o]] + 1;}
inline void add(int o , int k)
{
addv[o] += k;
val[o] += k;
}
inline void down(int o)
{
if(addv[o])
{
if(lc[o])
add(lc[o] , addv[o]);
if(rc[o])
add(rc[o] , addv[o]);
addv[o] = 0;
}
}
void split(int o , int& a , int& b , int x)
{
if(!o)
{
a = b = 0;
return ;
}
down(o);
if(val[o] <= x)
{
a = o;
split(rc[o] , rc[o] , b , x);
}
else
{
b = o;
split(lc[o] , a , lc[o] , x);
}
up(o);
}
int merge(int a , int b)
{
if(!a || !b) return a + b;
if(pr[a] > pr[b])
{
lc[b] = merge(a , lc[b]);
up(b);
return b;
}
else
{
rc[a] = merge(rc[a] , b);
up(a);
return a;
}
}
int newnode(int x)
{
val[++cnt] = x;
pr[cnt] = rand();
sz[cnt] = 1;
return cnt;
}
void insert(int x)
{
int a , b;
split(root , a , b , x);
root = merge(a , merge(newnode(x) , b));
}
int kth(int rk)
{
int now = root;
while(now)
{
down(now);
int g = sz[lc[now]] + 1;
if(g == rk)
return val[now];
if(g > rk)
now = lc[now];
else
rk -= g , now = rc[now];
}
}
int main()
{
scanf("%d %d",&n,&minn);
while(n--)
{
char opt;int x;
scanf(" %c %d",&opt,&x);
int a , b;
split(root , a , b , minn - 1);
root = b;
ans += sz[a];
if(opt == 'I')
{
if(x >= minn)
insert(x);
}
if(opt == 'A')
add(root , x);
if(opt == 'S')
add(root , -x);
if(opt == 'F')
{
if(x > sz[root] || x <= 0)
puts("-1");
else
printf("%d\n",kth(sz[root] - x + 1));
}
}
printf("%d",ans);
}
```
by xhhkwy @ 2018-11-17 10:59:12
循环结束后应当再分裂一次,因为最后还有可能有人退出.
by xhhkwy @ 2018-11-17 11:00:00
@[chen_zhe](/space/show?uid=8457)
by xhhkwy @ 2018-11-17 11:04:27
第4篇题解被卡到15s
by xhhkwy @ 2018-11-17 11:11:16
还有用vector的题解被卡到6s
by xhhkwy @ 2018-11-17 11:17:29
%%%
by AThousandSuns @ 2018-11-17 11:20:31
好像所有splay都给我卡死了诶...
by xhhkwy @ 2018-11-17 11:21:25
%%%
by MornEveGlow @ 2018-11-17 11:23:44
%%%
by hpbl @ 2018-11-17 11:23:53
@[AThousandSuns](/space/show?uid=72118) %%%您世界第一
by xhhkwy @ 2018-11-17 11:23:55