求助 TLE50pts

回复帖子

@Katsura_Hinagiku 2019-07-26 11:04 回复

写的fhq treap,是合并复杂度太高了吗。。。

那应该怎么合并啊。。

#include<bits/stdc++.h>
using namespace std;
struct node
{
    int l,r,sz,val,pri,id;
}tree[10000005];
int root[100005],tot=0;
char read()
{
    char c=getchar();
    while(c!='B'&&c!='Q')c=getchar();
    return c;
}
int newnode(int x,int y)
{
    tree[++tot].val=x;
    tree[tot].pri=rand();
    tree[tot].sz=1;
    tree[tot].id=y;
    return tot;
}
void pushup(int u)
{
    tree[u].sz=tree[tree[u].l].sz+tree[tree[u].r].sz+1;
}
void split_rank(int u,int rank,int &l,int &r)
{
    if(!u)
    {
        l=r=0;
        return;
    }
    if(tree[tree[u].l].sz+1<=rank)
    {
        l=u;
        split_rank(tree[u].r,rank-tree[tree[u].l].sz-1,tree[u].r,r);
    }
    else
    {
        r=u;
        split_rank(tree[u].l,rank,l,tree[u].l);
    }
    pushup(u);
}
void split_val(int u,int x,int &l,int &r)
{
    if(!u)
    {
        l=r=0;
        return;
    }
    if(tree[u].val<=x)
    {
        l=u;
        split_val(tree[u].r,x,tree[u].r,r);
    }
    else
    {
        r=u;
        split_val(tree[u].l,x,l,tree[u].l);
    }
    pushup(u);
}
int merge(int l,int r)
{
    if(!l||!r)return l+r;
    if(tree[l].pri<tree[r].pri)
    {
        tree[l].r=merge(tree[l].r,r);
        pushup(l);
        return l;
    }
    else
    {
        tree[r].l=merge(l,tree[r].l);
        pushup(r);
        return r;
    }
}
void ins(int &u,int x,int y)
{
    int L,R;
    split_val(u,x,L,R);
    u=merge(merge(L,newnode(x,y)),R);
}
int get_val(int &u,int rank)
{
    if(tree[u].sz<rank)return -1;
    int A,B,C;
    split_rank(u,rank,A,C);
    split_rank(A,rank-1,A,B);
    int temp=tree[B].id;
    u=merge(merge(A,B),C);
    return temp;
}
void MERGE(int &u,int uu)
{
    if(!uu)return;
    MERGE(u,tree[uu].l);
    MERGE(u,tree[uu].r);
    ins(u,tree[uu].val,tree[uu].id);
    tree[uu].val=tree[uu].id=tree[uu].l=tree[uu].r=0;
}
void change_root(int u,int uu)
{
    if(!uu)return;
    root[tree[uu].id]=u;
    change_root(u,tree[uu].l);
    change_root(u,tree[uu].r);
}
int main()
{
    srand(19260817);
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i)
    {
        int kk;
        scanf("%d",&kk);
        root[i]=newnode(kk,i);
    }
    for(int i=1;i<=m;++i)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        if(root[x]==root[y])continue;
        int xx=root[x],yy=root[y];
        if(tree[xx].sz<tree[yy].sz)
        {
            MERGE(yy,xx);
            change_root(yy,yy);
        }
        else
        {
            MERGE(xx,yy);
            change_root(xx,xx);
        }
    }
    int q;
    scanf("%d",&q);
    while(q--)
    {
        char c=read();
        int x,y;
        scanf("%d%d",&x,&y);
        if(c=='Q')
        {
            printf("%d\n",get_val(root[x],y));
        }
        if(c=='B')
        {
            int xx=root[x],yy=root[y];
            if(xx==yy)continue;
            if(tree[xx].sz<tree[yy].sz)
            {
                MERGE(yy,xx);
                change_root(yy,yy);
            }
            else
            {
                MERGE(xx,yy);
                change_root(xx,xx);
            }
        }
    }
    return 0;
}
反馈
如果你认为某个帖子有问题,欢迎向洛谷反馈,以帮助更多的同学。



请具体说明理由,以增加反馈的可信度。