• <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)論
              
            精品免费tv久久久久久久| 亚洲va久久久久| 久久精品国产亚洲av麻豆色欲 | 久久亚洲AV永久无码精品| 国产成人精品久久综合 | 亚洲国产精品无码久久青草| 久久99精品国产麻豆宅宅| 2021久久国自产拍精品| 久久久久国产一级毛片高清板| 午夜精品久久久久久影视riav| 久久天天躁夜夜躁狠狠| www.久久精品| 久久精品国产欧美日韩99热| 国产精品久久影院| 欧美日韩精品久久久免费观看| 2020久久精品国产免费| 一本色综合久久| 久久99精品国产| 色婷婷久久综合中文久久蜜桃av| 四虎国产精品免费久久5151 | 久久天天躁狠狠躁夜夜网站 | 亚洲国产另类久久久精品| 国产精品熟女福利久久AV| 久久妇女高潮几次MBA| 久久精品国产只有精品66| 综合网日日天干夜夜久久 | 久久青草国产手机看片福利盒子| 亚洲综合日韩久久成人AV| 久久久久亚洲AV综合波多野结衣| 国产成人精品免费久久久久| 久久人做人爽一区二区三区| 亚洲国产香蕉人人爽成AV片久久| 9999国产精品欧美久久久久久| 久久久久久久久久久久中文字幕 | 99精品久久久久久久婷婷| 四虎久久影院| 久久久噜噜噜久久| 久久99精品国产99久久6| 亚洲欧美日韩精品久久| 精品国产乱码久久久久久浪潮| 久久久精品国产sm调教网站 |