///////////////////////////////////////////作品名称:并查集及线段树应用//作者姓名:满天飞//作品时间: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;}

评论