求助,蒟蒻可能是已知唯一一个只WA了#5的人
查看原帖
求助,蒟蒻可能是已知唯一一个只WA了#5的人
310773
PCCP楼主2023/3/16 00:03

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;
} 
2023/3/16 00:03
加载中...