实际提交时将freopen删去了
求dalao帮忙
by League丶翎 @ 2018-01-02 22:06:07
可以试下洛谷IDE
by LPA20020220 @ 2018-01-02 22:09:00
捕捉dalao一只
by Mirach @ 2018-01-02 22:18:44
检查一下询问和删除，我在本地帮你拍出错了
数据文件：
```cpp
#include<bits/stdc++.h>
using namespace std;
int main()
{
srand(time(NULL));
int n=1000;
int minn=10000;
printf("%d %d\n",n,minn);
for(int i=0;i<n;++i)
{
switch(rand()%5)
{
case 0:
putchar('I'),printf(" %d\n",rand()%10000+10000);
break;
case 1:
putchar('A'),printf(" %d\n",rand()%10000);
break;
case 2:
putchar('S'),printf(" %d\n",rand()%10000);
break;
case 3:
putchar('F'),printf(" %d\n",rand()%500);
break;
case 4:
putchar('F'),printf(" %d\n",rand()%100);
break;
}
}
return 0;
}
```
删除删多的可能比较大。。。
我的代码：
```cpp
#pragma GCC optimize(3)
#include<cstdio>
#define N 500100
#define R register
static int son[N][2],fat[N],key[N],val[N],siz[N],rt,tot,pos,sum;
inline void PU(int x){siz[x]=son[x][0][siz]+son[x][1][siz]+val[x];}
inline void Rot(int x)
{
R int y=fat[x],z=fat[y],k=son[y][0]==x;
son[z][son[z][1]==y]=x;fat[x]=z;
son[y][!k]=son[x][k];son[x][k][fat]=y;
son[x][k]=y;fat[y]=x;PU(y);
}
inline void Spl(int x,int goal)
{
for(;fat[x]!=goal;Rot(x))
{
R int y=fat[x],z=fat[y];
if(z!=goal)(son[y][0]==x)^(son[z][0]==y)?Rot(x):Rot(y);
}PU(x);if(!goal)rt=x;
}
inline void Fin(int x)
{for(pos=rt;son[pos][x>key[pos]]&&x!=key[pos];pos=son[pos][x>key[pos]]);Spl(pos,0);}
inline void Nex(int x,int k)
{
Fin(x);if(!(key[pos]>x&&k||key[pos]<x&&!k))
for(pos=son[pos][k];son[pos][!k];pos=son[pos][!k]);
}
inline void Ins(int x)
{
R int fa=0;
for(pos=rt;pos&&key[pos]!=x;pos=son[pos][x>key[pos]])fa=pos;
if(pos)++val[pos];else
{
pos=++tot;
son[fa][x>key[fa]]=pos;
son[pos][0]=son[pos][1]=0;
fat[pos]=fa;key[pos]=x;val[pos]=siz[pos]=1;
}Spl(pos,0);
}
inline void Del(int x)
{
Nex(x,1);R int p=pos;
Fin(-1e9);Spl(p,rt);
sum+=p[son][0][siz];
son[p][0]=0;
PU(p);PU(rt);
}
inline int Kth(int k)
{
if(k<2||k+1>siz[rt])return 0;
for(pos=rt;;)
{
R int y=son[pos][0];
if(k>siz[y]+val[pos])
{
k-=siz[y]+val[pos];
pos=son[pos][1];
}else
if(siz[y]<k)return 1;
else pos=y;
}
}
inline int read(){int x=0,f=0;register char ch=getchar();for(;ch<48||ch>57;ch=getchar())f|=ch=='-';for(;ch>47&&ch<58;ch=getchar())x=(x<<1)+(x<<3)+(ch^48);return f?-x:x;}
int main()
{
char s[5];int now=0;
Ins(-1e9);Ins(+1e9);
int n=read(),minn=read();
for(int i=0;i<n;++i)
{
scanf("%s",s);int k=read();
switch(s[0])
{
case 'I':if(k>=minn)Ins(k-now);break;
case 'A':now+=k;break;
case 'S':now-=k;Del(minn-now-1);break;
case 'F':printf("%d\n",Kth(siz[rt]-k)?key[pos]+now:-1);break;
}
}printf("%d\n",sum);
}
```
by Hades18 @ 2018-01-03 09:51:34
@[League丶翎](/space/show?uid=20601)
你的输出和标算很近了，但差了一点
标算：
```cpp
***** ans.txt
25858
46209
-1
44682
-1
```
你的输出：
```cpp
***** OUT.TXT
25858
49314
-1
47407
-1
```
by Hades18 @ 2018-01-03 09:55:17
谢谢dalao，已经改正
放上我的代码
by League丶翎 @ 2018-01-03 20:04:55
@[尘染梦](/space/show?uid=27029)
by League丶翎 @ 2018-01-03 20:05:03
```cpp
#include <bits/stdc++.h>
using namespace std;
#define maxn 100010
int ch[maxn][2],key[maxn],f[maxn],size[maxn],cnt[maxn];
int sz,root,n,m,add,del;
int read() {
int ans=0,flag=1;
char c=getchar();
while( (c>'9' || c<'0') && c!='-' ) c=getchar();
if(c=='-') flag=-1,c=getchar();
while(c>='0' && c<='9') ans=ans*10+c-'0',c=getchar();
return ans*flag;
}
bool get(int x) {return ch[f[x]][1]==x;}
void clear(int x) {
ch[x][0]=ch[x][1]=size[x]=f[x]=cnt[x]=key[x]=0;
return ;
}
void update(int x) {
int &l=ch[x][0],&r=ch[x][1];
size[x]=cnt[x]+size[l]+size[r];
return ;
}
void rotate(int x) {
int old=f[x],oldf=f[old],w=get(x);
ch[old][w]=ch[x][w^1];
f[ch[old][w]]=old;
ch[x][w^1]=old;
f[old]=x;
f[x]=oldf;
if(oldf)
ch[oldf][ch[oldf][1]==old]=x;
update(old);
update(x);
return ;
}
void splay(int x,int tar) {
for(int fa;(fa=f[x])!=tar;rotate(x))
if(f[fa]!=tar)
rotate(get(x)==get(fa)?fa:x);
if(!tar)
root=x;
return ;
}
int findx(int x) { //by search the ranking return the treenumber
int now=root;
while(1) {
if(ch[now][1] && x<=size[ch[now][1]])
now=ch[now][1];
else {
int tmp=(ch[now][1]?size[ch[now][1]]:0)+cnt[now];
if(x<=tmp) {
splay(now,0);
return now;
}
x-=tmp;
now=ch[now][0];
}
}
}
void insert(int x) {
if(root==0) {
sz++;
ch[sz][0]=ch[sz][1]=f[sz]=0;
root=sz;
cnt[sz]=size[sz]=1;
key[sz]=x;
return ;
}
int now=root,fa=0;
while(1) {
if(x==key[now]) {
cnt[now]++;
update(now);update(fa);
splay(now,0);
break;
}
fa=now;
now=ch[now][key[now]<x];
if(now==0) {
sz++;
ch[sz][0]=ch[sz][1]=0;
f[sz]=fa;
cnt[sz]=size[sz]=1;
ch[fa][key[fa]<x]=sz;
key[sz]=x;
update(fa);
splay(sz,0);
break;
}
}
return ;
}
int main() {
freopen("in","r",stdin);
n=read(),m=read();
while(n--) {
char str[10];
scanf("%s",str);
int k=read();
switch(str[0]) {
case 'I':{
if(k>=m)
insert(k-add);
break;
}
case 'A':{
add+=k;
break;
}
case 'S':{
add-=k;
insert(m-add);
if(ch[root][0])
del+=size[ch[root][0]],ch[root][0]=0;
if(cnt[root]>1) {
cnt[root]--;
size[root]--;
clear(ch[root][0]);
ch[root][0]=0;
}
else {
int old=root;
root=ch[root][1];
f[root]=0;
clear(old);
}
break;
}
case 'F':{
if(k<=0 || k>size[root]) puts("-1");
else printf("%d\n",key[findx(k)]+add);
break;
}
}
}
printf("%d\n",del);
return 0;
}
```
by League丶翎 @ 2018-01-03 20:05:08