bzoj2733 [HNOI2012]永无乡

74 阅读 0 评论 49 点赞

我是靠谱客的博主认真金鱼，最近开发中收集的这篇文章主要介绍bzoj2733 [HNOI2012]永无乡，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

http://www.elijahqi.win/2018/02/16/bzoj2733/
题目描述

永无乡包含 n 座岛，编号从 1 到 n，每座岛都有自己的独一无二的重要度，按照重要度可以将这 n 座岛排名，名次用 1 到 n 来表示。某些岛之间由巨大的桥连接，通过桥可以从一个岛到达另一个岛。如果从岛 a 出发经过若干座（含 0 座）桥可以到达岛 b，则称岛 a 和岛 b 是连通的。

现在有两种操作：

B x y 表示在岛 x 与岛 y 之间修建一座新桥。

Q x k 表示询问当前与岛 x连通的所有岛中第 k 重要的是哪座岛，即所有与岛 x 连通的岛中重要度排名第 k 小的岛是哪座，请你输出那个岛的编号。
输入输出格式

输入格式：

输入文件第一行是用空格隔开的两个正整数 n 和 m，分别表示岛的个数以及一开始存在的桥数。接下来的一行是用空格隔开的 n 个数，依次描述从岛 1 到岛 n 的重要度排名。随后的 m 行每行是用空格隔开的两个正整数 ai 和 bi，表示一开始就存在一座连接岛 ai 和岛 bi 的桥。后面剩下的部分描述操作，该部分的第一行是一个正整数 q，表示一共有 q 个操作，接下来的 q 行依次描述每个操作，操作的格式如上所述，以大写字母 Q 或B 开始，后面跟两个不超过 n 的正整数，字母与数字以及两个数字之间用空格隔开。对于 20%的数据 n<=1000,q<=1000 对于 100%的数据 n<=100000,m<=n，q<=300000

输出格式：

对于每个 Q x k 操作都要依次输出一行，其中包含一个整数，表示所询问岛屿的编号。如果该岛屿不存在，则输出-1。
输入输出样例

输入样例#1：复制

5 1
4 3 2 5 1
1 2
7
Q 3 2
Q 2 1
B 2 3
B 1 5
Q 2 1
Q 2 4
Q 2 3

输出样例#1：复制

-1
2
5
1
2

线段树合并：根据题意首先把初始给定的一些桥都连起来然后我针对每个桥建一棵以重要度为权值的线段树然后并查集维护他们的连通性每当这两个之前没有连起来的时候就给他们连起来将两个合并起来的时候用线段树合并即可一开始写的时候觉得复杂度不对然后写着写着发现大概是对的可能是均摊logn? (口胡ing

#include<cstdio>
#include<algorithm>
#define N 110000
using namespace std;
inline char gc(){
    static char now[1<<16],*S,*T;
    if (T==S){T=(S=now)+fread(now,1,1<<16,stdin);if (T==S) return EOF;}
    return *S++;
}
inline int read(){
    int x=0,f=1;char ch=gc();
    while(ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=gc();}
    while(ch<='9'&&ch>='0') x=x*10+ch-'0',ch=gc();
    return x*f;
}
struct node{
    int left,right,sum; 
}tree[N*40];
int fa[N],id[N],cnt,n,m,root[N];
inline int find(int x){
    while(x!=fa[x]) x=fa[x]=fa[fa[x]];return x;
}
inline void update(int x){
    int l=tree[x].left,r=tree[x].right;
    tree[x].sum=tree[l].sum+tree[r].sum;
}
inline int merge(int x1,int x2){
    if (!x1||!x2) return x1+x2;
    tree[x1].left=merge(tree[x1].left,tree[x2].left);
    tree[x1].right=merge(tree[x1].right,tree[x2].right);
    update(x1);return x1;
}
inline void insert1(int &x,int l,int r,int p){
    if (!x) x=++cnt;++tree[x].sum;if (l==r) return;
    int mid=l+r>>1;if (p<=mid) insert1(tree[x].left,l,mid,p);
    else insert1(tree[x].right,mid+1,r,p);
}
inline int qr(int x,int l,int r,int p){ 
    if (l==r) return l;int mid=l+r>>1;
    if (p<=tree[tree[x].left].sum) return qr(tree[x].left,l,mid,p);
    return qr(tree[x].right,mid+1,r,p-tree[tree[x].left].sum);
}
int main(){
    freopen("bzoj2733.in","r",stdin);
    n=read();m=read();for (int i=1;i<=n;++i) fa[i]=i;int t;
    for (int i=1;i<=n;++i){id[t=read()]=i;insert1(root[i],1,n,t);}
    for (int i=1;i<=m;++i){
        int x=read(),y=read(),fx=find(x),fy=find(y);
        if(fx!=fy) fa[fx]=fy,root[fy]=merge(root[fx],root[fy]);
    }m=read();
    while(m--){
        char ch=gc();while(ch!='Q'&&ch!='B') ch=gc();
        if(ch=='B'){
            int x=read(),y=read(),fx=find(x),fy=find(y);
            if(fx!=fy) fa[fx]=fy,root[fy]=merge(root[fx],root[fy]);
        }
        if (ch=='Q'){
            int x=read(),k=read();x=find(x);if (tree[root[x]].sum<k) {puts("-1");continue;}
            printf("%dn",id[qr(root[x],1,n,k)]);
        }
    }
    return 0;
}

我弟一边打游戏一边还和同学语音..我写不下去代码就写了代码结果一个小错调试到3点多菜菜啊

启发式合并平衡树：和线段树合并一样只不过是每次合并的时候用一种启发式合并的思想每次把子树小的往子树大的里面插入即可 $复杂度也是n*log(n)^{2}$ 的

#include<cstdio>
#include<algorithm>
#define N 110000
#define N1 4400000
using namespace std;
inline char gc(){
    static char now[1<<16],*S,*T;
    if (T==S) {T=(S=now)+fread(now,1,1<<16,stdin);if (T==S) return EOF;}
    return *S++;
}
inline int read(){
    int x=0,f=1;char ch=gc();
    while(ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=gc();}
    while(ch<='9'&&ch>='0') x=x*10+ch-'0',ch=gc();
    return x*f;
}
int fa[N1],rt[N],size[N1],fa1[N],c[N1][2],v[N1],q[N],n,m,cnt,id[N];
inline int find(int x){while(x!=fa1[x]) x=fa1[x]=fa1[fa1[x]];return x;}
inline void update(int x){
    size[x]=size[c[x][0]]+size[c[x][1]]+1;
}
inline void insert1(int &x,int p,int f){
    if (!x){x=++cnt;v[x]=p;size[x]=1;fa[x]=f;return;}
    if (p<v[x]) insert1(c[x][0],p,x);else insert1(c[x][1],p,x);update(x);
}
inline void rotate(int x,int &tar){
    int y=fa[x],z=fa[y];
    if (y==tar) tar=x;else c[z][c[z][1]==y]=x;
    int l=c[y][1]==x,r=l^1;
    fa[c[x][r]]=y;fa[y]=x;fa[x]=z;
    c[y][l]=c[x][r];c[x][r]=y;update(y);update(x);
}
inline void splay(int x,int &tar){
    while(x!=tar){
        int y=fa[x],z=fa[y];
        if (y!=tar){
            if (c[y][0]==x^c[z][0]==y) rotate(x,tar);else rotate(y,tar);
        }rotate(x,tar);
    }
}
inline int find1(int x,int p){
    int l=c[x][0],r=c[x][1];
    if (size[l]+1==p) return x;
    if (p<=size[l]) return find1(l,p);else return find1(r,p-size[l]-1);
}
inline void print(int x){
    if (c[x][0]) print(c[x][0]);
    printf("%d ",v[x]);
    if (c[x][1]) print(c[x][1]);
}
int main(){
    freopen("bzoj2733.in","r",stdin);
    n=read();m=read();int x;for (int i=1;i<=n;++i) fa1[i]=i;
    for (int i=1;i<=n;++i){id[x=read()]=i;insert1(rt[i],x,rt[i]);splay(cnt,rt[i]);}
    while(m--){
        int x=read(),y=read(),fx=find(x),fy=find(y);
        if (fx!=fy){
            int l=1,r=0;
            if (size[fx]<size[fy]){
                q[++r]=rt[fx];
                while(l<=r){
                    x=q[l++];if (c[x][0])q[++r]=c[x][0];
                    if (c[x][1]) q[++r]=c[x][1];
                }
                for (int i=1;i<=r;++i) insert1(rt[fy],v[q[i]],rt[fy]),splay(cnt,rt[fy]);fa1[fx]=fy;
            }else{
                q[++r]=rt[fy];
                while(l<=r){
                    x=q[l++];if (c[x][0])q[++r]=c[x][0];
                    if (c[x][1]) q[++r]=c[x][1];
                }
                for (int i=1;i<=r;++i) insert1(rt[fx],v[q[i]],rt[fx]),splay(cnt,rt[fx]);fa1[fy]=fx;
            }
        }
    }m=read();//print(rt[1]);puts("");
    while(m--){
        char ch=gc();while(ch!='B'&&ch!='Q') ch=gc();
        if(ch=='B'){
            int x=read(),y=read(),fx=find(x),fy=find(y);
            if (fx!=fy){
                int l=1,r=0;
                if (size[fx]<size[fy]){
                    q[++r]=rt[fx];
                    while(l<=r){
                        x=q[l++];if (c[x][0])q[++r]=c[x][0];
                        if (c[x][1]) q[++r]=c[x][1];
                    }
                    for (int i=1;i<=r;++i) insert1(rt[fy],v[q[i]],rt[fy]),splay(cnt,rt[fy]);fa1[fx]=fy;
                }else{
                    q[++r]=rt[fy];
                    while(l<=r){
                        x=q[l++];if (c[x][0])q[++r]=c[x][0];
                        if (c[x][1]) q[++r]=c[x][1];
                    }
                    for (int i=1;i<=r;++i) insert1(rt[fx],v[q[i]],rt[fx]),splay(cnt,rt[fx]);fa1[fy]=fx;
                }
            }   
        }
        if (ch=='Q'){
            int x=read(),k=read();x=find(x);
            if (size[rt[x]]<k) {puts("-1");continue;}
            int t=find1(rt[x],k);printf("%dn",id[v[t]]);
        }
        //for (int i=1;i<=n;++i) printf("%d ",size[rt[i]]);puts("");
    }
    return 0;
}