上面的代码没处理无前/后驱的情况(虽然加了仍然28PTS,又WA又MLE),下面的已更新
```cpp
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
#define TNP pair<node * ,node * >
const LL N=5e5+115;
mt19937_64 ra(114514);
struct node
{
node *ch[2];
LL r,v,s;
inline node(LL v):v(v) {ch[0]=ch[1]=nullptr;s=1;r=ra();}
inline node(node* sn) {ch[0]=sn->ch[0],ch[1]=sn->ch[1],v=sn->v,r=sn->v;}
//bool operator < (const node* & rhs) const {return this->r<=rhs->r;}
inline void up()
{
this->s=1;
if(this->ch[0]) this->s+=this->ch[0]->s;if(this->ch[1]) this->s+=this->ch[1]->s;
}
} *roots[N];
inline LL sz(node* &rt) {return rt?rt->s:0;}
inline node* copy(node* rs) {return rs?new node(rs):nullptr;}
inline TNP csplit_s(node* rt,LL k)
{
if(!rt) return TNP(nullptr,nullptr);TNP t;node* cpy=copy(rt);
if(k<=sz(rt->ch[0])) {t=csplit_s(cpy->ch[0],k);cpy->ch[0]=t.second;cpy->up();t.second=cpy;}
else {t=csplit_s(cpy->ch[1],k-sz(cpy->ch[0])-1);cpy->ch[1]=t.first;cpy->up();t.first=cpy;}
return t;
}
inline TNP csplit(node* rt,LL k)
{
if(!rt) return TNP(nullptr,nullptr);TNP t;node* cpy=copy(rt);
if(rt->v<=k) {t=csplit(cpy->ch[1],k);cpy->ch[1]=t.first;cpy->up();t.first=cpy;}
else {t=csplit(cpy->ch[0],k);cpy->ch[0]=t.second;cpy->up();t.second=cpy;}
return t;
}
inline node* merge(node* a,node* b)
{
if(!a) return b;if(!b) return a;
if(a->r<b->r) {a->ch[1]=merge(a->ch[1],b);a->up();return a;}
else {b->ch[0]=merge(a,b->ch[0]);b->up();return b;}
}
inline LL getrank(node* rt,LL k)//作为结果时要将返回值+1
{
if(!rt) return 0;
else if(k<=rt->v) return getrank(rt->ch[0],k);else return getrank(rt->ch[1],k)+sz(rt->ch[0])+1;
}
inline LL getkth(node* &rt,LL k)
{
//if(!rt) return 0;
TNP a=csplit_s(rt,k-1);TNP b=csplit_s(a.second,1);
node* t=b.first;rt=merge(a.first,merge(t,b.second));
return t?t->v:2147483647;
}
inline void insert(node* &rt,LL v)
{
TNP t=csplit(rt,v);
rt=merge(t.first,merge(new node(v),t.second));
}
inline void rem(node* &rt,LL v)
{
TNP t=csplit(rt,v-1);
TNP u=csplit_s(t.second,1);delete u.first;
rt=merge(t.first,u.second);
}
inline LL getlst(node* &rt,LL v) {LL dla=getrank(rt,v);return dla+1==1?-2147483647:getkth(rt,dla);}
inline LL getnxt(node* &rt,LL v) {return getkth(rt,getrank(rt,v+1)+1);}
LL n,op,ver,nver;
inline LL qread()
{
LL a=0,f=1;char ch=getchar();
while(ch<'0' || ch>'9') {if(ch=='-') f*=-1;ch=getchar();}
while(ch>='0' && ch<='9') {a=a*10+ch-'0';ch=getchar();}
return a*f;
}
inline void qwrite(LL x)
{
if(x==0) {putchar('0'),putchar('\n');return;}
char w[128];LL cnt=0;
if(x<0) putchar('-'),x*=-1;
while(x) {w[cnt++]=(x%10)+'0';x/=10;}
while(cnt--) putchar(w[cnt]);putchar('\n');
}
int main()
{
n=qread();
for(auto i=1;i<=n;i++)
{
ver=qread(),op=qread();LL in=qread();++nver;roots[nver]=copy(roots[ver]);
if(op==1){insert(roots[nver],in);}
else if(op==2){rem(roots[nver],in);}
else if(op==3){qwrite(getrank(roots[nver],in)+1);}
else if(op==4){qwrite(getkth(roots[nver],in));}
else if(op==5){qwrite(getlst(roots[nver],in));}
else if(op==6){qwrite(getnxt(roots[nver],in));}
}
return 0;
}
```
by 2020kanade @ 2022-03-18 16:40:17
@[2020kanade](/user/456724) 删除操作不能真的把节点删掉,因为可能还会用到之前版本的这个节点。
by _ @ 2022-03-22 11:06:46