#include <bits/stdc++.h>
typedef long long LL;
typedef unsigned long long ULL;
typedef long double LD;
using namespace std;
const int INF = 2147483647;
struct Treap{int l,r,val,dat,cnt,size;}a[100005];
int tot,root,n,Min,sum,s,e;
inline int read()
{
int x=0,f=1;
char ch = getchar();
while(!isdigit(ch)) {if(ch == '-') f = -1;ch = getchar();}
while(isdigit(ch)) {x=x*10+ch-48;ch=getchar();}
return f*x;
}
inline int New(int val)
{
a[++tot].val = val;
a[tot].dat = rand();
a[tot].cnt = a[tot].size = 1;
return tot;
}
inline void Update(int p){a[p].size = a[a[p].l].size + a[a[p].r].size + a[p].cnt;}
inline int Get1(int p,int val)
{
if(!p) return 0;
if(val == a[p].val) return a[a[p].l].size + 1;
if(val < a[p].val) return Get1(a[p].l,val);
return Get1(a[p].r,val) + a[a[p].l].size + a[p].cnt;
}
inline int Get2(int p,int rank)
{
if(!p) return INF;
if(a[a[p].l].size >= rank) return Get2(a[p].l,rank);
if(a[a[p].l].size + a[p].cnt >= rank) return a[p].val;
return Get2(a[p].r,rank - a[a[p].l].size - a[p].cnt);
}
inline void zig(int &p)
{
int q = a[p].l;
a[p].l = a[q].r,a[q].r = p,p = q;
Update(a[p].r),Update(p);
}
inline void zag(int &p)
{
int q = a[p].r;
a[p].r = a[q].l,a[q].l = p,p = q;
Update(a[p].l),Update(p);
}
inline void Insert(int &p,int val)
{
if(!p)
{
p = New(val);
return;
}
if(val == a[p].val)
{
a[p].cnt++,Update(p);
return;
}
if(val < a[p].val)
{
Insert(a[p].l,val);
if(a[p].dat < a[a[p].l].dat) zig(p);
}
else
{
Insert(a[p].r,val);
if(a[p].dat < a[a[p].r].dat) zag(p);
}
Update(p);
}
inline int Getpre(int val)
{
int ans = 1,p = root;
while(p)
{
if(val == a[p].val)
{
if(a[p].l > 0)
{
p = a[p].l;
while(a[p].r > 0) p = a[p].r;
ans = p;
}
break;
}
if(a[p].val < val && a[p].val > a[ans].val) ans = p;
p = val<a[p].val?a[p].l:a[p].r;
}
return a[ans].val;
}
inline int Getnext(int val)
{
int ans = 2,p = root;
while(p)
{
if(val == a[p].val)
{
if(a[p].r > 0)
{
p = a[p].r;
while(a[p].l > 0) p = a[p].l;
ans = p;
}
break;
}
if(a[p].val > val && a[p].val < a[ans].val) ans = p;
p = val<a[p].val?a[p].l:a[p].r;
}
return a[ans].val;
}
inline void Remove(int &p,int val)
{
if(!p) return;
if(val == a[p].val)
{
if(a[p].cnt > 1)
{
--a[p].cnt;
Update(p);
return;
}
if(a[p].l || a[p].r)
{
if(!a[p].r || a[a[p].l].dat > a[a[p].r].dat) zig(p),Remove(a[p].r,val);
else zag(p),Remove(a[p].l,val);
Update(p);
}
else p = 0;
return;
}
val < a[p].val?Remove(a[p].l,val):Remove(a[p].r,val);
Update(p);
}
int main(int argc,char *argv[])
{
freopen("data.in","r",stdin);
freopen("data.out","w",stdout);
New(-INF),New(INF);
root = 1;a[1].r = 2;
Update(root);
n = read(),Min = read();
while(n--)
{
char ch;
scanf("%c",&ch);
int k = read();
if(ch == 'I' && k-sum >= Min) Insert(root,k-sum),++s,++e;
else if(ch == 'A') Min -= k,sum += k;
else if(ch == 'S')
{
Min += k,sum -= k;
int tmp = Min-1,tmp2;
while(Getpre(tmp) != -INF)
{
tmp2 = tmp,tmp = Getpre(tmp);
Remove(root,Getpre(tmp2));
--e;
}
}
else if(ch == 'F')
{
if(e < k) puts("-1");
else printf("%d\n",Get2(root,e-k+2)+sum);
}
}
printf("%d",s-e+1);
return 0;
}
就这个很丑的代码,全WA,我把测试点1的数据下载了下来,本机vsc跑了一遍,结果一模一样,结果我上IDE一测,不管是样例还是测试点1,只会输出个‘1’?这是为什么?
附数据点1:
20 0
I 4
F 1
I 6
S 9
F 14
I 6
I 7
A 8
I 3
F 2
I 9
I 6
I 6
S 3
S 5
I 6
F 1
I 3
A 2
F 5