luogu3224 永无乡（动态开点，权值线段树合并）

永无乡包含 n 座岛，编号从 1 到 n ，每座岛都有自己的独一无二的重要度，按照重要度可以将这 n 座岛排名，名次用 1 到 n 来表示。某些岛之间由巨大的桥连接，通过桥可以从一个岛到达另一个岛。如果从岛 a 出发经过若干座（含 0 座）桥可以到达岛 b ，则称岛 a 和岛 b 是连通的。现在有两种操作：B x y 表示在岛 x 与岛 y 之间修建一座新桥。Q x k 表示询问当前与岛 x 连通的所有岛中第 k 重要的是哪座岛，即所有与岛 x 连通的岛中重要度排名第 k 小的岛是哪座，请你输出那个岛的编号。n≤100000,m≤n,q≤300000。

首先，对于每个岛建一个权值线段树，然后根据初始边将它们合并。对于在同一个联通块里的点，通过并查集选出其中一个点x，root[x]代表这个联通块的线段树的根。对于查询，第k重要的岛可以通过在权值线段树里的二分来确定。合并时，规定将x合并到y。

为什么时间复杂度是nlogn呢？

考虑点数的变化。刚开始的时候有nlogn个结点，最后只有2n个结点。因此，消失的结点数目是nlogn级别的。由于对两个结点的一次合并，消耗了一个结点，同时花费\(O(1)\)，所以总的时间复杂度是\(O(nlogn)\)。

#include <cctype>

#include <cstdio>

using namespace std;

const int maxn=1e5+5, maxseg=maxn*20;

//v:表示一个岛的重要性 id：重要性反推是哪个结点 fa:用来找到与线段树对应的结点

int n, m, q, v[maxn], id[maxn], fa[maxn];

//root:将岛的编号映射在线段树根位置上 lc,rc:线段树结点的左右孩子

int cnt, root[maxn], lc[maxseg], rc[maxseg], seg[maxseg];

void get(int &x){

    int flag=1; char c;

    for (c=getchar(); !isdigit(c); c=getchar())

        if (c=='-') flag=-1;

    for (x=c-48; c=getchar(), isdigit(c); )

        x=(x<<3)+(x<<1)+c-48; x*=flag;

}

int find(int x){ return x==fa[x]?x:fa[x]=find(fa[x]); }

//给权值线段树增加一个值

void add(int &x, int l, int r, int pos){

    if (!x) x=cnt++;

    if (l==r){ ++seg[x]; return; }

    int mid=(l+r)>>1;

    if (pos>mid) add(rc[x], mid+1, r, pos);

    else add(lc[x], l, mid, pos);

    seg[x]=seg[lc[x]]+seg[rc[x]];

}

//将x归并到y上，并返回y（nlogn）

//普通的merge不能这样写！（两个孩子都是空结点）

int merge(int x, int y){

    //返回存在的子节点。如果子节点都不存在，返回的是空结点

    if (!x) return y; if (!y) return x;

    lc[y]=merge(lc[x], lc[y]);

    rc[y]=merge(rc[x], rc[y]);

    seg[y]=seg[lc[y]]+seg[rc[y]];

    return y;

}

//在权值线段树中找到第k个点(logn)

int query(int now, int l, int r, int k){

    if (l==r) return l;

    int mid=(l+r)>>1;

    if (seg[lc[now]]>=k) return query(lc[now], l, mid, k);

    else return query(rc[now], mid+1, r, k-seg[lc[now]]);

}

int main(){

    get(n); get(m);

    for (int i=1; i<=n; ++i){

        get(v[i]); id[v[i]]=i;

        fa[i]=i; root[i]=cnt++;

        add(root[i], 1, n, v[i]);

    }

    int t1, t2;

    for (int i=0; i<m; ++i){

        get(t1); get(t2);

        merge(root[find(t1)], root[find(t2)]);

        fa[find(t1)]=find(t2);

    }

    get(q); char c; int x, y;

    for (int i=0; i<q; ++i){

        while (!isgraph(c=getchar()));

        get(x); get(y);

        if (c=='Q'){

            x=root[find(x)];

            if (seg[x]<y) puts("-1");

            else printf("%d\n", id[query(x, 1, n, y)]);

        } else {

            merge(root[find(x)], root[find(y)]);

            fa[find(x)]=find(y);

        }

    }

    return 0;

}

巴特西

luogu3224 永无乡（动态开点，权值线段树合并）

luogu3224 永无乡（动态开点，权值线段树合并）

最新文章

热门文章