萌新刚学OI,全部TLE求助QAQ

回复帖子

@TLE自动机 2019-07-09 17:19 回复

用Splay启发式合并,每次合并把size小的Splay全取出来再一个一个insert到大的里面 (我菜)

是我复杂度假了?如果假了的话请问怎么合并啊QAQ

复杂度不假的话就是写挂了,求DALAO帮忙康康(:з」∠)

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int read(){
    int x=0;char ch=getchar();int pos=1;
    for(;!isdigit(ch);ch=getchar()) if(ch=='-') pos=0;
    for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';
    return pos?x:-x; 
}
const int N=5000001;
int n,m,q;
int ff[N],val[N],rt[N],son[N][2],sz[N],tot,rb[N<<2],b[N],top,lnk[N],a[N],fa[N];
int gf(int num){
    if(num==ff[num]) return num;
    else {
        ff[num]=gf(ff[num]);
        return ff[num];
    }
}
void push_up(int x){
    sz[x]=sz[son[x][1]]+sz[son[x][0]]+1;
}
int get(int x){
    return (x==son[fa[x]][1]);
}
void rotate(int x){
    int f=fa[x];int g=fa[f];
    int gx=get(x),gf=get(f);
    fa[son[x][gx^1]]=f;
     son[f][gx]=son[x][gx^1];
    fa[f]=x;
     son[x][gx^1]=f;
     fa[x]=g;
     son[g][gf]=x;
    push_up(f);
    push_up(x); 
}
void splay(int x,int v,int i){
    while(fa[x]!=v){
        int f=fa[x];
        if(fa[f]!=v){
            rotate((get(x)==get(f))?f:x); 
        }
        rotate(x);
    }
    if(v==0) rt[i]=x;
}
void find(int i,int x){
    int now=rt[i];
    while(son[now][val[now]>x]){
        now=son[now][val[now]>x];
    }
    splay(now,0,i);
}
void insert(int i,int x){
    int now=rt[i],p;
    while(val[now]!=x&&now){
        p=now;
        now=son[now][val[now]<x];
    }
    if(top){
        now=rb[top--];
    }else now=++tot;
    val[now]=x;
    fa[now]=p;
    son[p][x>val[p]]=now;
    sz[now]=1;
    sz[p]++;
    son[now][1]=son[now][0]=0;
    splay(now,0,i);
}
char S[10];
int ava[N],hie;
void add(int v){
    if(val[v]==192608170||val[v]==-192608170) return;
    rb[++top]=v;
    ava[++hie]=val[v];
    if(son[v][1]) add(son[v][1]);
    if(son[v][0]) add(son[v][0]);
}
int kth(int i,int k){
    k++;
    int now=rt[i];
    while(k){
        if(sz[son[now][0]]>k){
            now=son[now][0];
        }else if(k==sz[son[now][0]]+1){
            return lnk[val[now]];
        }else{
            k-=(sz[son[now][0]]+1);
            now=son[now][1];
        }
    }
}
int main(){
    n=read(),m=read();
    for(int i=1;i<=n;i++){
        a[i]=read();
        b[i]=a[i];
    }
    sort(b+1,b+n+1);
    for(int i=1;i<=n;i++){
        a[i]=lower_bound(b+1,b+n+1,a[i])-b;
        lnk[a[i]]=i;
    }
    for(int i=1;i<=n;i++){
        ff[i]=i;
        rt[i]=++tot;
        fa[tot]=0;
        val[tot]=a[i];
        sz[tot]=3;
        int xx=tot;

        son[xx][1]=++tot;
        val[tot]=192608170;
        sz[tot]=1;
        son[tot][0]=son[tot][1]=0;
        fa[tot]=xx;

        son[xx][0]=++tot;
        val[tot]=-192608170;
        sz[tot]=1;
        son[tot][0]=son[tot][1]=0;
        fa[tot]=xx;
    }
    int u,v; 
    for(int i=1;i<=m;i++){
        u=read(),v=read();
        int fu=gf(u),fv=gf(v);
        if(fu==fv) continue;
        if(sz[rt[fu]]<sz[rt[fv]]) swap(fu,fv);
        hie=0;
        add(rt[fv]);
        for(int i=1;i<=hie;i++){
            insert(fu,ava[i]);
        }
        ff[fv]=fu;
    }
    int q=read();
    for(int i=1;i<=q;i++){
        scanf("%s",S);
        u=read(),v=read();
        if(S[0]=='Q'){
            int fu=gf(u);
            if(sz[rt[fu]]-2<v){
                printf("-1\n");
                continue;
            }else{
                printf("%d\n",kth(fu,v));
            }
        }else{
            int fu=gf(u),fv=gf(v);
            if(fu==fv) continue;
            if(sz[rt[fu]]<sz[rt[fv]]) swap(fu,fv);
            hie=0;
            add(rt[fv]);
            for(int i=1;i<=hie;i++){
                insert(fu,ava[i]);
            }
            ff[fv]=fu;
        }
    }
    return 0;
} 
反馈
如果你认为某个帖子有问题,欢迎向洛谷反馈,以帮助更多的同学。



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