• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            隨筆 - 87  文章 - 279  trackbacks - 0
            <2007年4月>
            25262728293031
            1234567
            891011121314
            15161718192021
            22232425262728
            293012345

            潛心看書研究!

            常用鏈接

            留言簿(19)

            隨筆分類(81)

            文章分類(89)

            相冊(cè)

            ACM OJ

            My friends

            搜索

            •  

            積分與排名

            • 積分 - 217972
            • 排名 - 117

            最新評(píng)論

            閱讀排行榜

            評(píng)論排行榜

            USE?并查集和線段樹

            The k-th Largest Group
            Time Limit:2000MS? Memory Limit:131072K
            Total Submit:1222 Accepted:290

            Description

            Newman likes playing with cats. He possesses lots of cats in his home. Because the number of cats is really huge, Newman wants to group some of the cats. To do that, he first offers a number to each of the cat (1, 2, 3, …, n). Then he occasionally combines the group cat i is in and the group cat j is in, thus creating a new group. On top of that, Newman wants to know the size of the k-th biggest group at any time. So, being a friend of Newman, can you help him?

            Input

            1st line: Two numbers N and M (1 ≤ N, M ≤ 200,000), namely the number of cats and the number of operations.

            2nd to (m + 1)-th line: In each line, there is number C specifying the kind of operation Newman wants to do. If C = 0, then there are two numbers i and j (1 ≤ i, jn) following indicating Newman wants to combine the group containing the two cats (in case these two cats are in the same group, just do nothing); If C = 1, then there is only one number k (1 ≤ k ≤ the current number of groups) following indicating Newman wants to know the size of the k-th largest group.

            Output

            For every operation “1” in the input, output one number per line, specifying the size of the kth largest group.

            Sample Input

            10 10
            0 1 2
            1 4
            0 3 4
            1 2
            0 5 6
            1 1
            0 7 8
            1 1
            0 9 10
            1 1

            Sample Output

            1
            2
            2
            2
            2

            Hint

            When there are three numbers 2 and 2 and 1, the 2nd largest number is 2 and the 3rd largest number is 1.

            Source
            POJ Monthly--2006.08.27, zcgzcgzcg

            #include?<iostream>
            using?namespace?std;
            const?int?MAXN?=?200001;

            class?UFset
            {
            public:
            ????
            int?parent[MAXN];
            ????UFset();
            ????
            int?Find(int);
            ????
            void?Union(int,?int);
            }
            ;

            UFset::UFset()
            {
            ????memset(parent,?
            -1,?sizeof(parent));
            }


            int?UFset::Find(int?x)
            {
            ????
            if?(parent[x]?<?0)
            ????????
            return?x;
            ????
            else
            ????
            {
            ????????parent[x]?
            =?Find(parent[x]);
            ????????
            return?parent[x];
            ????}
            //?壓縮路徑
            }


            void?UFset::Union(int?x,?int?y)
            {
            ????
            int?pX?=?Find(x);
            ????
            int?pY?=?Find(y);
            ????
            int?tmp;
            ????
            if?(pX?!=?pY)
            ????
            {
            ????????tmp?
            =?parent[pX]?+?parent[pY];?//?加權(quán)合并
            ????????if?(parent[pX]?>?parent[pY])
            ????????
            {
            ????????????parent[pX]?
            =?pY;
            ????????????parent[pY]?
            =?tmp;
            ????????}

            ????????
            else
            ????????
            {
            ????????????parent[pY]?
            =?pX;
            ????????????parent[pX]?
            =?tmp;
            ????????}

            ????}

            }


            int?f[(MAXN+1)*3]?=?{0};
            int?n,?m;

            void?initTree()
            {
            ????
            int?l?=?1,?r?=?n;
            ????
            int?c?=?1;
            ????
            while?(l?<?r)
            ????
            {
            ????????f[c]?
            =?n;
            ????????c?
            =?c?*?2;
            ????????r?
            =?(l?+?r)?/?2;
            ????}

            ????f[c]?
            =?n;//葉子初始化
            }


            void?insertTree(int?k)
            {
            ????
            int?l?=?1,?r?=?n;
            ????
            int?c?=?1;
            ????
            int?mid;

            ????
            while?(l?<?r)
            ????
            {
            ????????f[c]
            ++;
            ????????mid?
            =?(r?+?l)?/?2;
            ????????
            if?(k?>?mid)
            ????????
            {
            ????????????l?
            =?mid?+?1;
            ????????????c?
            =?c?*?2?+?1;
            ????????}

            ????????
            else
            ????????
            {
            ????????????r?
            =?mid;
            ????????????c?
            =?c?*?2;
            ????????}

            ????}

            ????f[c]
            ++;//葉子增加1
            }


            void?delTree(int?k)
            {
            ????
            int?l?=?1,?r?=?n;
            ????
            int?c?=?1;
            ????
            int?mid;

            ????
            while?(l?<?r)
            ????
            {
            ????????f[c]
            --;
            ????????mid?
            =?(r?+?l)?/?2;
            ????????
            if?(k?>?mid)
            ????????
            {
            ????????????l?
            =?mid?+?1;
            ????????????c?
            =?c?*?2?+?1;
            ????????}

            ????????
            else
            ????????
            {
            ????????????r?
            =?mid;
            ????????????c?
            =?c?*?2;
            ????????}

            ????}

            ????f[c]
            --;//葉子減少1
            }


            int?searchTree(int?k)
            {
            ????
            int?l?=?1,?r?=?n;
            ????
            int?c?=?1;
            ????
            int?mid;

            ????
            while?(l?<?r)
            ????
            {
            ????????mid?
            =?(l?+?r)?/?2;
            ????????
            if?(k?<=?f[2*c+1])
            ????????
            {
            ????????????l?
            =?mid?+?1;
            ????????????c?
            =?c?*?2?+?1;
            ????????}

            ????????
            else
            ????????
            {
            ????????????k?
            -=?f[2*c+1];
            ????????????r?
            =?mid;
            ????????????c?
            =?c?*?2;
            ????????}

            ????}

            ????
            return?l;
            }


            int?main()
            {
            ????
            int?i,?j;
            ????
            int?x,?y;
            ????
            int?k;
            ????
            int?l,?r;
            ????
            int?cmd;
            ????
            int?px,?py;
            ????
            int?tx,?ty,?tz;
            ????UFset?UFS;

            ????
            ????scanf(
            "%d%d",?&n,?&m);
            ????initTree();
            ????
            for?(i=0;?i<m;?i++)
            ????
            {
            ????????scanf(
            "%d",?&cmd);
            ????????
            if?(cmd?==?0)
            ????????
            {
            ????????????scanf(
            "%d%d",?&x,?&y);
            ????????????px?
            =?UFS.Find(x);
            ????????????py?
            =?UFS.Find(y);
            ????????????
            if?(px?!=?py)
            ????????????
            {
            ????????????????tx?
            =?-UFS.parent[px];
            ????????????????ty?
            =?-UFS.parent[py];
            ????????????????tz?
            =?tx?+?ty;
            ????????????????UFS.Union(x,?y);
            ????????????????insertTree(tz);
            ????????????????delTree(tx);
            ????????????????delTree(ty);
            ????????????}

            ????????}

            ????????
            else
            ????????
            {
            ????????????scanf(
            "%d",?&k);
            ????????????printf(
            "%d\n",?searchTree(k));
            ????????}

            ????}

            ????
            return?0;
            }
            posted on 2006-09-06 13:30 閱讀(816) 評(píng)論(4)  編輯 收藏 引用 所屬分類: 算法&ACM

            FeedBack:
            # re: 第一次用兩種數(shù)據(jù)結(jié)構(gòu)解的題目, 紀(jì)念一下 2006-09-08 23:01 Optimistic
            哇...偶木了  回復(fù)  更多評(píng)論
              
            # re: 第一次用兩種數(shù)據(jù)結(jié)構(gòu)解的題目, 紀(jì)念一下 2006-09-08 23:11 
            其實(shí)線段樹比較好懂, 但是難在怎么運(yùn)用-_-個(gè)人感覺, 摸索中!~~~  回復(fù)  更多評(píng)論
              
            # re: 第一次用兩種數(shù)據(jù)結(jié)構(gòu)解的題目, 紀(jì)念一下 2006-09-28 12:21 踏雪赤兔
            進(jìn)步很快哩~~贊一個(gè)!
            P.S.博客手拉手弄好了~  回復(fù)  更多評(píng)論
              
            # re: 第一次用兩種數(shù)據(jù)結(jié)構(gòu)解的題目, 紀(jì)念一下 2006-09-28 12:57 
            thx!~:)  回復(fù)  更多評(píng)論
              
            久久亚洲av无码精品浪潮| 伊人色综合久久天天| 精品久久久久久无码中文字幕 | 国产欧美久久一区二区| 久久天天躁夜夜躁狠狠躁2022| 久久久久国产| 日本精品久久久久久久久免费| 国产2021久久精品| 精品乱码久久久久久夜夜嗨| 久久精品国产清自在天天线| 亚洲成av人片不卡无码久久| 久久天天躁狠狠躁夜夜不卡| 久久亚洲2019中文字幕| 久久久黄色大片| 亚洲av伊人久久综合密臀性色| 亚洲精品tv久久久久久久久 | 2022年国产精品久久久久| 精品久久8x国产免费观看| 97r久久精品国产99国产精| 久久精品成人免费看| 久久久WWW成人| 成人综合久久精品色婷婷| 久久亚洲精品成人av无码网站| 精品久久一区二区三区| 久久99亚洲综合精品首页| 久久中文字幕精品| 2021久久国自产拍精品| 九九久久精品无码专区| 久久久久久久精品妇女99 | 国产精品99久久久久久www| 久久久久久久国产免费看| 亚洲AV无码1区2区久久| 97精品伊人久久久大香线蕉| 久久天天躁夜夜躁狠狠| 久久久久久国产a免费观看不卡| 久久婷婷五月综合97色直播| 狠狠人妻久久久久久综合蜜桃| 国产美女亚洲精品久久久综合| 伊人久久大香线焦综合四虎| 亚洲国产精品无码久久SM| 久久久久综合国产欧美一区二区|