这是什么奇怪的错误啊喂!
查看原帖
这是什么奇怪的错误啊喂!
754467
f_hxr_楼主2023/9/26 16:34

rt,萌新刚学FHQTreap,你可以看见WAon#4,但是就在我下载#4数据的时候我发现一个很奇怪的问题:

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
LL N,A,B;
struct Treap{
	LL cnt,root;
	struct node
	{LL key,val,size=0,ls=0,rs=0;}tree[200005];
	#define ls(p) (tree[p].ls)
	#define rs(p) (tree[p].rs)
	void pushup(LL p)
	{tree[p].size=tree[ls(p)].size+tree[rs(p)].size+1;}
	LL New(LL X){
		tree[++cnt].key=X;tree[cnt].val=rand();
		tree[cnt].size=1;ls(cnt)=rs(cnt)=0;
		return cnt;
	}
	LL Merge(LL X,LL Y){
		if(!X||!Y)return X|Y;
		if(tree[X].val<=tree[Y].val){
			rs(X)=Merge(rs(X),Y);
			pushup(X);return X;
		}
		else{
			ls(Y)=Merge(X,ls(Y));
			pushup(Y);return Y;
		}
	}
	void Split(LL p,LL X,LL& L,LL& R){
		if(!p){L=R=0;return;}
		if(tree[p].key<=X)
		{L=p;Split(rs(p),X,rs(p),R);}
		else
		{R=p,Split(ls(p),X,L,ls(p));}
		pushup(p);
	}
	void insert(LL X){
		Split(root,X-1,A,B);
		root=Merge(Merge(A,New(X)),B);
	}
	void del(LL X){
		LL T;
		Split(root,X-1,A,B);
		Split(B,X,T,B);
		T=Merge(ls(T),rs(T));
		root=Merge(Merge(A,B),T);
	}
	LL rank(LL X){
		Split(root,X-1,A,B);
		LL ret=tree[A].size+1;
		root=Merge(A,B);
		return ret;
	}
	LL get(LL p,LL inx){
		LL mid=tree[ls(p)].size+1;
		if(mid==inx)return tree[p].key;
		if(mid<inx)return get(rs(p),inx-mid);
		else return get(ls(p),inx);
	}
}FHQ;
int main(){
	freopen("P3369_4.in","r",stdin);
	freopen("ans.txt","w",stdout);
	scanf("%lld",&N);
	while(N--){
		LL op,X;
		scanf("%lld%lld",&op,&X);
		if(op==1)FHQ.insert(X);
		else if(op==2)FHQ.del(X);
		else if(op==3)printf("%lld\n",FHQ.rank(X));
		else if(op==4)printf("%lld\n",FHQ.get(1,X));
		else if(op==5){
			FHQ.Split(FHQ.root,X-1,A,B);
			printf("%lld\n",FHQ.get(A,FHQ.tree[A].size));
			FHQ.root=FHQ.Merge(A,B);
		}else{
			FHQ.Split(FHQ.root,X,A,B);
			printf("%lld\n",FHQ.get(B,1));
			FHQ.root=FHQ.Merge(A,B);
		}
	}
	return 0;
}

这段代码读入"P3369_4.in",也就是本题的测试点#4,但是ans.txt却和"P3369_4.out"一模一样!

大佬们不信可以下个数据试试QAQ

2023/9/26 16:34
加载中...