• <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爽| 国产精品久久新婚兰兰| 亚洲国产成人久久笫一页| 精品一二三区久久aaa片| 久久精品国产亚洲AV无码偷窥 | 国产午夜精品理论片久久影视| 热re99久久6国产精品免费| 狠狠色丁香婷婷久久综合不卡| 99热都是精品久久久久久| 亚洲精品第一综合99久久| 国内精品久久久久| 久久午夜福利电影| 成人综合伊人五月婷久久| 青青青青久久精品国产h久久精品五福影院1421 | 亚洲国产精品成人AV无码久久综合影院| 久久久精品国产免大香伊 | 欧美综合天天夜夜久久| 漂亮人妻被中出中文字幕久久 | 999久久久免费精品国产| 香蕉99久久国产综合精品宅男自 | 99久久国产亚洲高清观看2024 | 久久国产成人精品国产成人亚洲| 无码人妻精品一区二区三区久久| 香港aa三级久久三级| 久久综合给久久狠狠97色| 亚洲日本久久久午夜精品| 精品国产热久久久福利| 亚洲精品无码久久一线| 精品久久久久久久无码| 国产亚洲精品美女久久久| 久久精品中文字幕大胸| 久久九九久精品国产免费直播| 国产精品一久久香蕉国产线看| 亚洲国产精品无码久久久不卡| 97香蕉久久夜色精品国产 | 欧美性猛交xxxx免费看久久久| 嫩草影院久久国产精品| 潮喷大喷水系列无码久久精品| 无码人妻少妇久久中文字幕蜜桃| 一本久道久久综合狠狠爱|