RT,调了一晚上了,就是死活不知道哪里有问题,提示显示第8247行有问题,不知道有没有大佬能帮蒟蒻看看代码究竟哪里可能有问题。
蒟蒻可以关注回报。
代码如下:
#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define int long long
using namespace std;
const int N=2e5+10;
int n,in=0;
long long minn,delta=0;
struct Splay{
int tot,root;
int ch[N][2],fa[N],siz[N],cnt[N];
long long value[N];
bool check(int pos){
return ch[fa[pos]][1]==pos;
}
void pushup(int pos){
siz[pos]=siz[ch[pos][0]]+siz[ch[pos][1]]+cnt[pos];
}
void rotate(int x){
int y=fa[x],z=fa[y],yet=check(x);
int w=ch[x][yet^1];//w: opp to x;
fa[x]=z;
if(z){
ch[z][check(y)]=x;//if have z,use x instead y;z->x->y
}
fa[y]=x;//x->y
ch[x][yet^1]=y;//y's position;
fa[w]=y;//y instead x become w's new father;
ch[y][yet]=w;//w's position wont change;
pushup(y);
pushup(x);
}
void splay(int pos,int goal=0 ){
if(pos==0){//if no place return
return;
}
for(int fat=fa[pos];fat=fa[pos],fat!=goal;rotate(pos)){
if(fa[fat]!=goal){
rotate(check(pos)==check(fat)?fat:pos);
}
}
if(goal==0){
root=pos;
}
}
int insert(int val){
int pos=root,pre=0;
while(pos&&value[pos]!=val){
pre=pos;
pos=ch[pos][val>value[pos]];
}
if(pos){
++cnt[pos];
}
else{
pos=++tot;
value[pos]=val;
cnt[pos]=siz[pos]=1;
ch[pos][0]=ch[pos][1]=0;
fa[pos]=pre;
if(pre){
ch[pre][val>value[pre]]=pos;
}
}
splay(pos);
return pos;
}
int find(int val){
int pos=root;
while(pos&&value[pos]!=val&&ch[pos][val>value[pos]]){
pos=ch[pos][val>value[pos]];
}
splay(pos);
return pos;
}
int bef(int val){
int pos=find(val);
if(value[pos]<val){
return pos;
}
pos=ch[pos][0];
while(ch[pos][1]){
pos=ch[pos][1];
}
return pos;
}
int aft(int val){
int pos=find(val);
if(value[pos]>val){
return pos;
}
pos=ch[pos][1];
while(ch[pos][0]){
pos=ch[pos][0];
}
return pos;
}
long long kth(int rk){
int pos=root;
if(siz[pos]<rk){
return 0;
}
while(1){
int lsize=siz[ch[pos][0]];
if(rk<=lsize){
pos=ch[pos][0];
}
else if(rk<=lsize+cnt[pos]){
return value[pos];
}
else{
rk-=lsize+cnt[pos];
pos=ch[pos][1];
}
}
}
int rank(int val){
int pos=find(val);
return siz[ch[pos][0]]+1;
}
void era(int val){
int be=bef(val),af=aft(val);
splay(be);
splay(af,be);
int pos=ch[af][0];
--cnt[pos];
if(cnt[pos]<=0){
ch[af][0]=fa[pos]=0;
}
else{
splay(pos);
}
}
void update(int pos){
if(ch[pos][0]){
update(ch[pos][0]);
}
if(ch[pos][1]){
update(ch[pos][1]);
}
pushup(pos);
}
}tree;
int main(){
scanf("%d%lld",&n,&minn);
char opt;
int x;
int l=tree.insert(-1e12);
int r=tree.insert(1e12);
for(int i=1;i<=n;i++){
cin>>opt>>x;
if(opt=='I'){
if(x<minn){
continue;
}
++in;
x-=delta;
tree.insert(x);
}
if(opt=='A'){
delta+=x;
}
if(opt=='S'){
delta-=x;
r=tree.aft(minn-delta-1);
tree.splay(r);
tree.ch[tree.root][0]=0;
tree.insert(-1e12);
}
if(opt=='F'){
if(tree.siz[tree.root]-2<x){
printf("-1\n");
continue;
}
x=tree.siz[tree.root]-2-x+1;
printf("%lld\n",tree.kth(x+1)+delta);
}
// tree.update(tree.root);
}
printf("%lld\n",in-(tree.siz[tree.root]-2));
return 0;
}