为什么我的treap会MLE了?

回复帖子

@86158615777a 2019-02-12 15:07 回复
#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<cstdlib>
using namespace std;
struct tree{
    int l,r,v,pro,size,c;
}; tree t[1100000];
long long int T,A;
int ans[1001000],root;
int unit(int x) {return t[t[x].l].size+t[t[x].r].size+1;}
void left_turn(int &x)
{
    int y=t[x].r;
    t[x].r=t[y].l, t[y].l=x;
    t[y].size=t[x].size, t[x].size=unit(x);
    if(x==root) root=y;
    x=y;
}
void right_turn(int &x)
{
    int y=t[x].l;
    t[x].l=t[y].r, t[y].r=x;
    t[y].size=t[x].size, t[x].size=unit(x);
    if(x==root) root=y;
    x=y;
}
void insert(int &x,int y)
{
    if(!x) {x=++T; t[x].v=y; t[x].size++; t[x].pro=rand(); t[x].c=1; return;}
    else {
        t[x].size++;
        if(t[x].v==y) t[x].c++;
        else if(t[x].v>y)  {insert(t[x].l,y); if(t[x].pro<t[t[x].l].pro) right_turn(x);}
        else  {insert(t[x].r,y); if(t[x].pro>t[t[x].r].pro) left_turn(x);}
    }
}
void delet(int &x,int y)
{
    if(t[x].v==y)
    {
        if(t[x].c>1) {t[x].c--; t[x].size--;}
        else{
        while(1)
      {
        if(!t[x].l) {x=t[x].l; break;}
        else if(!t[x].r) {x=t[x].r; break;}
        else{
            if(t[x].pro<t[t[x].r].pro) left_turn(x);
          }
      }
        }
    }
    else {
        t[x].size--;
        if(t[x].v>y) delet(t[x].l,y);
        else delet(t[x].r,y);
    }
}
int find_grade(int x,int y)
{
    if(!x) return 0;
    if(t[x].v==y) return t[t[x].l].size+1;
    else if(t[x].v>y) return find_grade(t[x].l,y);
    else return t[t[x].l].size+1+find_grade(t[x].r,y);
}
int find_x(int x,int y)
{
    if(!x) return 0;
    if(t[t[x].l].size+1==y) return t[x].v;
    else if(t[t[x].l].size+1<y) {y-=t[t[x].l].size-1; return find_x(t[x].r,y);}
    else return find_x(t[x].l,y);
}
int front(int x,int y)
{
    if(t[x].v>=y) return front(t[x].l,y);
    else if(!t[x].r) return t[x].v;
    else return front(t[x].r,y);
}
int back(int x,int y)
{
    if(t[x].v<=y) return back(t[x].r,y);
    else if(!t[x].l) return t[x].v;
    else return back(t[x].l,y);
}
int main()
{
    int opt,m,n,i;
    cin>>n;
    for(i=1;i<=n;i++)
    {
        scanf("%d%d",&opt,&m);
        if(opt==1) insert(root,m);
        if(opt==2) delet(root,m);
        if(opt==3) ans[++A]=find_grade(root,m);
        if(opt==4) ans[++A]=find_x(root,m);
        if(opt==5) ans[++A]=front(root,m);
        if(opt==6) ans[++A]=back(root,m);
    }
    for(i=1;i<=A;i++)
    printf("%d\n",ans[i]);
}