非旋平衡树,底下主函数操作不会了,玄2关,求请教
查看原帖
非旋平衡树,底下主函数操作不会了,玄2关,求请教
749811
Licis_Subway楼主2024/3/6 21:59

不用管那些define

#include<cstdio>
#include<string>
#include<stdlib.h>
#include<ctime>
using namespace std;
void __str_with_rl(string &s)
{
    s="";
    char cur;
    while(true)
    {
        cur=getchar();
        if(cur=='\n') return;
        if(cur>=32&&cur<=126) s.push_back(cur);
    }
}
#define MOVE 1
#define INSERT 2
#define DELETE 3
#define GET 4
#define PREV 5
#define NEXT 6
unsigned int __read_name()
{
    char first=getchar();
    while(true)
    {
        char cfcc=getchar();
        if(cfcc==32) break;
    }
    switch(first)
    {
        case 'M':
            return MOVE;
            break;
        case 'I':
            return INSERT;
            break;
        case 'D':
            return DELETE;
            break;
        case 'G':
            return GET;
            break;
        case 'P':
            return PREV;
            break;
        case 'N':
            return NEXT;
            break;
        default:
            return 12345;
            break;
    }
}
unsigned int read(int &x,string &s)
{
    s="";
    unsigned int nowname=__read_name();
    if(nowname==MOVE)
    {
        scanf("%d",&x);
        return MOVE;
    }
    else if(nowname==INSERT)
    {
        scanf("%d",&x);
        getchar();
        __str_with_rl(s);
        return INSERT;
    }
    else if(nowname==DELETE)
    {
        scanf("%d",&x);
        return DELETE;
    }
    else if(nowname==GET)
    {
        scanf("%d",&x);
        return GET;
    }
    else return nowname;
}
const int N=2097157;
struct Node
{
    int key;
    int ls,rs;
    int siz,pri;
}t[N];
int cnt=0,root=0;
#define L t[u].ls
#define R t[u].rs
#define LR t[l].rs
#define RL t[r].ls
void newNode(int x)
{
    ++cnt;
    t[cnt].key=x;
    t[cnt].ls=t[cnt].rs=0;
    t[cnt].siz=1;
    t[cnt].pri=rand();
}
void update(int u){t[u].siz=t[L].siz+t[R].siz+1;}
void Split(int u,int x,int &l,int &r)
{
    if(u==0)
    {
        l=r=0;
        return;
    }
    if(t[L].siz<=x)
    {
        l=u;
        Split(R,x,R,r);
    }
    else
    {
        r=u;
        Split(L,x,l,L);
    }
    update(u);
}
int merge(int l,int r)
{
    if(l==0||r==0) return l+r;
    if(t[l].pri>t[r].pri)
    {
        LR=merge(LR,r);
        update(l);
        return l;
    }
    else
    {
        RL=merge(l,RL);
        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);
    Split(l,x-1,l,p);
    p=merge(t[p].ls,t[p].rs);
    root=merge(merge(l,p),r);
}
int rank(int x)
{
    int l,r;
    Split(root,x,l,r);
    int ans=t[l].siz+1;
    root=merge(l,r);
    return ans;
}
int kth(int u,int k)
{
    if(t[L].siz==k-1) return t[u].key;
    else if(t[L].siz<k-1) return kth(R,k-t[L].siz-1);
    else return kth(L,k);
}
int pre(int x)
{
    int l,r;
    Split(root,x-1,l,r);
    int ans=kth(l,t[l].siz);
    root=merge(l,r);
    return ans;
}
int suc(int x)
{
    int l,r;
    Split(root,x-1,l,r);
    int ans=kth(r,1);
    root=merge(l,r);
    return ans;
}
int nown;

int main()
{
    srand((int)time(0));
    int x,n;
    string s;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        int op=read(x,s);
        if(op==PREV) --nown;
        else if(op==NEXT) ++nown;
        else if(op==MOVE) nown+=x;
        else if(op==INSERT)
        {
            
        }
    }
    
    return 0;
}
2024/3/6 21:59
加载中...