陈志轩 • 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;
}
评论: