首页 > 代码库 > 【BZOJ2733】永无乡[splay启发式合并or线段树合并]

【BZOJ2733】永无乡[splay启发式合并or线段树合并]

  题目大意:给你一些点,修改是在在两个点之间连一条无向边,查询时求某个点能走到的点中重要度第k大的点。题目中给定的是每个节点的排名,所以实际上是求第k小;题目求的是编号,不是重要度的排名。我一开始差点被这坑了。

  网址:http://www.lydsy.com/JudgeOnline/problem.php?id=2733

  这道题似乎挺经典的(至少我看许多神犇很早就做了这道题)。这道题有两种写法:并查集+(splay启发式合并or线段树合并)。我写的是线段树合并,因为……splay不会打+懒得学。

  线段树合并具体可以看ppt:https://wenku.baidu.com/view/88f4e134e518964bcf847c95.html(线段树的合并——杭州二中黄嘉泰)

  这道题可以一开始每个节点建一棵值域线段树(没用到的子树像trie一样,先指向null),然后合并操作就用上面文章中线段树合并的方法,同时把并查集合并一下(如果把树x合并到树y,那么在并查集里也要把fa[x]改为y,这样就能保证并查集的根和线段树的根是同一个节点),查询可以先用并查集查出这个节点属于哪棵树,然后在树上二分(就是在值域线段树上求序列第k大),然后就完了。

  P.S.似乎不加读入优化我的线段树合并要比我一位同学的splay快400ms+,不过splay很常用,还是过几天学一学吧。。。(第一行是我加了快读的线段树合并,第二行没有加快读,第三行是同学的splay)

技术分享

奇丑无比的代码:

技术分享
#include<cstdio>
using namespace std;
struct hh{
    int lc,rc,sum;
}a[3000010];
int rank[100010],id[100010],fa[100010],tot;
int read()
{
    char c=getchar(),flag=1;
    while(c<0||9<c){
        if(c==-)flag=-1; c=getchar(); 
    }
    int tmp=0;
    while(0<=c&&c<=9){
        tmp=tmp*10+c-0; c=getchar();
    }
    return tmp*flag;
}
void add(int now,int x,int l,int r)
{
    ++a[now].sum; if(l==r)return;
    if(x<=(l+r)>>1){
        if(!a[now].lc)a[now].lc=++tot;
        add(a[now].lc,x,l,(l+r)>>1);
    }
    else{
        if(!a[now].rc)a[now].rc=++tot;
        add(a[now].rc,x,((l+r)>>1)+1,r);
    }
}
int query(int now,int x,int l,int r)
{
    if(l==r)return l;
    if(a[a[now].lc].sum>=x)return query(a[now].lc,x,l,(l+r)>>1);
    else return query(a[now].rc,x-a[a[now].lc].sum,((l+r)>>1)+1,r);
}
void merge(int x,int y)
{
    a[x].sum+=a[y].sum;
    if(a[x].lc||a[x].rc){
        if(a[y].lc){
            if(!a[x].lc)a[x].lc=a[y].lc;
            else merge(a[x].lc,a[y].lc);
        }
        if(a[y].rc){
            if(!a[x].rc)a[x].rc=a[y].rc;
            else merge(a[x].rc,a[y].rc);
        }
    }
}
int find(int x)
{
    if(fa[x]==x)return x;
    return fa[x]=find(fa[x]);
}
int main()
{
    int n=read(),m=read(),i; tot=n;
    for(i=1;i<=n;i++){
        rank[i]=read(); id[rank[i]]=fa[i]=i;
        add(i,rank[i],1,n);
    }
    for(i=1;i<=m;i++){
        int x=read(),y=read(),fx,fy;
        fx=find(x); fy=find(y);
        if(fx!=fy){
            fa[fy]=fx; merge(fx,fy);
        }
    }
    m=read();
    for(i=1;i<=m;i++){
        char ch; scanf("%s",&ch);
        int x=read(),y=read();
        if(ch==Q){
            int fx=find(x);
            if(a[fx].sum<y)printf("-1\n"); else printf("%d\n",id[query(fx,y,1,n)]);
        }
        else{
            int fx=find(x),fy=find(y);
            if(fx!=fy){
                fa[fy]=fx; merge(fx,fy);
            }
        }
    }
}
View Code

  splay的等学了再补吧。。。

【BZOJ2733】永无乡[splay启发式合并or线段树合并]