萌新FHQ Treap求条
查看原帖
萌新FHQ Treap求条
1344956
BestCNSoda楼主2025/1/22 16:14

很奇怪,有时候不会爆,有时候会爆,有时候能做到一半才会爆

#include<bits/stdc++.h>
using namespace std;
const int M=1e7+10;
int cnt,root;
struct Node{
   int ls,rs;
   int key,pri;
   int siz;
}t[M];
void update(int x)
{
    t[x].siz=t[t[x].ls].siz+t[t[x].rs].siz+1;
}
void newnode(int x)
{
    cnt++;
    t[cnt].key=x;
    t[cnt].siz=1;
    t[cnt].pri=rand();
}
void Split(int rt,int x,int &L,int &R)
{
    if(rt==0) {L=R=0;return;}
    if(x>=t[rt].key){
        L=rt;
        Split(t[rt].rs,x,t[rt].rs,R);
    }
    else{
        R=rt;
        Split(t[rt].ls,x,L,t[rt].ls);
    }
    update(rt);
}
int Merge(int &L,int &R)
{
    if(L==0||R==0) return L+R;
    if(t[L].pri>t[R].pri){
        t[L].rs=Merge(t[L].rs,R);
        update(L);
        return L;
    }
    else{
        t[R].ls=Merge(L,t[R].ls);
        update(R);
        return R;
    }
}
void Insert(int x){
    int L,R;
    Split(root,x,L,R);
    newnode(x);
    int aa=Merge(L,cnt);
    root=Merge(aa,R);
}
void Del(int x){
    int L,R,p;
    Split(root,x,L,R);//L,R:<=x的子树,>x的子树
    Split(root,x-1,L,p);//L,p:<=x-1的子树,就是<x的子树,>x-1的子树,就是>=x的子树
    //又因为前面一行将根、左子树与右子树剥离,所以这里>=x就是==x
    p=Merge(t[p].ls,t[p].rs);//将==x为根的左右子树合并,p点就相当于被删除了,p‘点此时更新为左右子树根节点优先级高的那一个
    int aa=Merge(L,p);//中间量aa:合并<x的子树与原p点,现p’点的子树
    root=Merge(aa,R);
}
void Rank(int x){
    int L,R;
    Split(root,x-1,L,R);//同del函数
    printf("%d\n",t[L].siz+1);
    root=Merge(L,R);
}
int kth(int rt,int k)
{
    int siz=t[t[rt].ls].siz;
    if(siz+1==k) return rt;
    if(siz>=k) return kth(t[rt].ls,k);
    return kth(t[rt].rs,k-siz-1);
}
void Precursor(int x)
{
    int L,R;
    Split(root,x-1,L,R);
    printf("%d\n",t[kth(L,t[L].siz)].key);
    root=Merge(L,R);
}
void Successor(int x)
{
    int L,R;
    Split(root,x,L,R);
    printf("%d\n",t[kth(R,1)].key);
    root=Merge(L,R);
}
int main(){
    //freopen("3369.in","r",stdin);
    //freopen("3369.out","w",stdout);
    srand(time(NULL));
    int n;
    cin>>n;
    while(n--){
        int opt,x;
        scanf("%d%d",&opt,&x);
        switch(opt){
            case 1:Insert(x);break;//加点
            case 2:Del(x);break;//删点
            case 3:Rank(x);break;//查询比 x 小的个数,并且将得到的答案加一
            case 4:printf("%d\n",t[kth(root,x)].key);break;//询问排名为x的权值
            case 5:Precursor(x);break;//前驱
            case 6:Successor(x);break;//后驱
        }
    }
    return 0;
}
2025/1/22 16:14
加载中...