/////////////////////////////////////////
//作品名称:并查集及线段树应用
//作者姓名:满天飞
//作品时间:2008-8-18
//最后修改:2008-8-18
//Q Q 号码:280282813
//版权所有,翻版必究
////////////////////////////////////////
//写得要死终于过了
#include<iostream>
using namespace std;
typedef struct
{
    int lbound;   //左界
    int rbound;   //右界
    int left;   //左子树
    int right;   //右子树
    int ct;    //覆盖次数
}TreeNode;
class SegmentTree
{
    private:
        int nodenum;
        TreeNode* tree;
    public:
        SegmentTree(int);
        virtual ~SegmentTree(){delete[]tree;}
 //构建树
        void build(int, int);
 //插入一个数
        void insert(int);
 //删除一个数
        void erase(int);
 //查询第i大的数
        int search(int);
};
SegmentTree::SegmentTree(int a)
{
    tree = new TreeNode[2*a+10];
    memset(tree, 0, sizeof(TreeNode)*(2*a+10));
    nodenum = 0;
    build(a, 1);  
}
//采用先序从大到小递归构建
void SegmentTree::build(int a, int b)
{
    nodenum++;
    int v;
    v = nodenum;
    tree[v].lbound = a;
    tree[v].rbound = b;
    if((a-b)>1){
        tree[v].left = nodenum+1;
        build(a, (a+b)/2);
        tree[v].right = nodenum+1;
        build((a+b)/2, b);
    }
}
//插入某个数到叶子结点为止
void SegmentTree::insert(int a)
{
    int mid,f;
    f = 1;
    while((tree[f].lbound-tree[f].rbound) > 1){
  //对遍历过的结点依次增加覆盖次数
        tree[f].ct++;
  //取区间中值
        mid = (tree[f].lbound+tree[f].rbound)>>1;
  //比中值要大入左子树
        if(a > mid)
            f = tree[f].left;
  //否则进左子树
        else f = tree[f].right;
    }
 //叶子结点覆盖次数增加
    tree[f].ct++;
}
//类似插入操作
void SegmentTree::erase(int a)
{
    int mid, f;
    f = 1;
    while((tree[f].lbound-tree[f].rbound) > 1){
        tree[f].ct--;
        mid = (tree[f].lbound+tree[f].rbound)>>1;
        if(a > mid)
            f = tree[f].left;
        else f = tree[f].right;
    }
    tree[f].ct--;
}
//此树是从大到小排列,1是没有插入到树上的
int SegmentTree::search(int a)
{
    int f, l, r;
    f = 1;
 //此树的插入的数比所要查询的少则返回1
    if(tree[f].ct < a)
        return 1;
    else{
        while((tree[f].lbound-tree[f].rbound) > 1){
            l = tree[f].left;
            r = tree[f].right;
   //查询的第i个数比左子树存在的数的个数要多则进入右子树
            if(a > tree[l].ct){
    //减去左子树上的个数
                a = a-tree[l].ct;
                f = r;
            }
   //进左子树
            else f = l;
        }
    }
 //返回叶子结点的左边界
    return tree[f].lbound;
}
class Set
{
    public:
        int* ary;
        int length;
 //查找某个数的根结点
        int Find(int index);
 //合并两个数
        void Union(int first, int second);
        Set(int n);
        virtual ~Set(){delete[]ary;}
};
Set::Set(int n)
{
    int i;
    ary = new int[n+10];
    length = n;
    for(i = 1; i <= n; ++i)
        ary[i] = -1;
}
//将每次查找过的路线上的结点全部都指向根结点
int Set::Find(int index)
{
    int i, j, t;
    if(index <= 0 || index > length) return -1;
 //查找index元素的根结点
    for(i = index; ary[i] > 0; i = ary[i]);
 //将这条路线上的所有元素全部指向根结点
    for(j = index; j != i; j = t){
        t = ary[j];
        ary[j] = i;
    }
    return i;
}
//树的根结点保存树的元素个数,以负值的形式保存
void Set::Union(int f, int s)
{
 //如果第i棵树的元素比第j棵树的元素要多则将j加入到i中
    if(ary[f] <= ary[s]){
        ary[f] += ary[s];
        ary[s] = f;
    }
 //否则将i加入到j中
    else{
        ary[s] += ary[f];
        ary[f] = s;
    }
}
//算法:
//1.删除合并前的大小.
//2.插入合并后的大小.
//3.查询即可.
int main(int argv, char* argc[])
{
    int vex, opt, i;
    int optflag, f, s;
    int fsize, ssize, froot, sroot;
    cin>>vex>>opt;
    Set set(vex+10);
    SegmentTree tree(vex);
    for(i = 0; i < opt; ++i)
    {
        scanf("%d", &optflag);
        if(optflag == 0)
        {
            scanf("%d%d", &f, &s);
            froot = set.Find(f);
            sroot = set.Find(s);
            if(froot != sroot)
            {
    //得到树的大小
                fsize = -set.ary[froot];
                ssize = -set.ary[sroot];
    //将合并前的树大小删除
                if(fsize > 1)
                    tree.erase(fsize);
                if(ssize > 1)
                    tree.erase(ssize);
    //合并后的树大小插入
                tree.insert(fsize+ssize);
    //合并两棵树
                set.Union(froot, sroot);
            }
        }
        else
        {
            scanf("%d", &f);
            cout<<tree.search(f)<<endl;
        }
    }
    return 0;
}

评论