50pts求助

陈志轩  •  2个月前


为啥洛谷过了这里过不去,而且我的输出和答案是一样的

code:

#include<bits/stdc++.h>
#define int long long
using namespace std;
namespace PingHengTree{
	const int MAXN = 2e6 + 10;
	int PHTroot = 0,PHTcnt = 0;
	struct PHT{
		int val,ls,rs,pri,siz;
	}t[MAXN];
	int PHTnewnode(int x){
		PHTcnt++;
		t[PHTcnt] = (PHT){x,0,0,rand(),1};
		return PHTcnt;
	}
	void PHTupdate(int x){
		t[x].siz = t[t[x].ls].siz + t[t[x].rs].siz + 1;
	}
	void PHTSplit(int idx,int x,int &l,int &r){
		if (idx == 0){
			l = r = 0;
			return ;
		}
		if (t[idx].val <= x){
			l = idx;
			PHTSplit(t[idx].rs,x,t[idx].rs,r);
		}
		else{
			r = idx;
			PHTSplit(t[idx].ls,x,l,t[idx].ls);
		}
		PHTupdate(idx);
	}
	int PHTMerge(int l,int r){
		//l_allval<=r_allval
		if (l == 0 || r == 0){
			return l + r;
		}
		if (t[l].pri > t[r].pri){
			t[l].rs = PHTMerge(t[l].rs,r);
			PHTupdate(l);
			return l;
		}
		else{
			t[r].ls = PHTMerge(l,t[r].ls);
			PHTupdate(r);
			return r;
		}
	}
	void PHTInsert(int x){
		int l = 114514,r = 1919810;
		PHTSplit(PHTroot,x,l,r);
		PHTroot = PHTMerge(PHTMerge(l,PHTnewnode(x)),r);
	}
	void PHTDelete(int x){
		int l = 114514,r = 1919810,o = 1234567;
		PHTSplit(PHTroot,x,l,r);
		PHTSplit(l,x - 1,l,o);
		PHTroot = PHTMerge(PHTMerge(l,PHTMerge(t[o].ls,t[o].rs)),r);
	}
	int PHTRank(int x){
		int l = 114514,r = 1919810;
		PHTSplit(PHTroot,x - 1,l,r);
		int ans = t[l].siz + 1;
		PHTroot = PHTMerge(l,r);
		return ans;
	}
	int PHTkth(int idx,int x){
		if (t[t[idx].ls].siz + 1 == x){
			return idx;
		}
		if (x <= t[t[idx].ls].siz){
			return PHTkth(t[idx].ls,x);
		}
		return PHTkth(t[idx].rs,x - t[t[idx].ls].siz - 1);
	}
	int PHTPrev(int x){
		int l = 114514,r = 1919810;
		PHTSplit(PHTroot,x - 1,l,r);
		int ans = t[PHTkth(l,t[l].siz)].val;
		PHTroot = PHTMerge(l,r);
		return ans; 
	}
	int PHTNext(int x){
		int l = 114514,r = 1919810;
		PHTSplit(PHTroot,x,l,r);
		int ans = t[PHTkth(r,1)].val;
		PHTroot = PHTMerge(l,r);
		return ans; 
	}
}

using namespace PingHengTree;
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int n;
	cin>>n;
	for (int i = 1;i <= n;i++){
		int opt,x;
		cin>>opt>>x;
		if (opt == 1){
			PHTInsert(x);
		}
		if (opt == 2){
			PHTDelete(x);
		}
		if (opt == 3){
			cout<<PHTRank(x)<<'\n';
		}
		if (opt == 4){
			cout<<t[PHTkth(PHTroot,x)].val<<'\n';
		}
		if (opt == 5){
			cout<<PHTPrev(x)<<'\n';
		}
		if (opt == 6){
			cout<<PHTNext(x)<<'\n';
		}
	}
	return 0;
}

评论:


陈志轩  •  2个月前

magicoj独有的输入和标答一样但是WA


LYZ  •  2个月前