青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

隨筆 - 87  文章 - 279  trackbacks - 0
<2006年1月>
25262728293031
1234567
891011121314
15161718192021
22232425262728
2930311234

潛心看書研究!

常用鏈接

留言簿(19)

隨筆分類(81)

文章分類(89)

相冊

ACM OJ

My friends

搜索

  •  

積分與排名

  • 積分 - 219411
  • 排名 - 118

最新評論

閱讀排行榜

評論排行榜

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];?//?加權合并
????????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 閱讀(827) 評論(4)  編輯 收藏 引用 所屬分類: 算法&ACM

FeedBack:
# re: 第一次用兩種數據結構解的題目, 紀念一下 2006-09-08 23:01 Optimistic
哇...偶木了  回復  更多評論
  
# re: 第一次用兩種數據結構解的題目, 紀念一下 2006-09-08 23:11 
其實線段樹比較好懂, 但是難在怎么運用-_-個人感覺, 摸索中!~~~  回復  更多評論
  
# re: 第一次用兩種數據結構解的題目, 紀念一下 2006-09-28 12:21 踏雪赤兔
進步很快哩~~贊一個!
P.S.博客手拉手弄好了~  回復  更多評論
  
# re: 第一次用兩種數據結構解的題目, 紀念一下 2006-09-28 12:57 
thx!~:)  回復  更多評論
  
青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <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>
              国产欧美在线视频| 欧美成年人网站| 国产精品一卡二卡| 亚洲免费在线看| 亚洲一区二区三区四区在线观看| 欧美另类极品videosbest最新版本| 亚洲激情自拍| 亚洲午夜影视影院在线观看| 国产专区一区| 亚洲电影免费观看高清| 老司机凹凸av亚洲导航| 正在播放亚洲| 夜夜夜久久久| 国内精品**久久毛片app| 欧美不卡在线视频| 欧美午夜宅男影院在线观看| 久久久91精品国产一区二区三区 | 亚洲视频电影在线| 国内精品久久久久久| 麻豆久久精品| 欧美精品一区二区高清在线观看| 亚洲欧美日本日韩| 欧美mv日韩mv国产网站| 欧美中文字幕在线观看| 欧美成人午夜| 久久国产手机看片| 欧美大片网址| 久久精品99无色码中文字幕 | 欧美一区二区在线| 一区二区电影免费观看| 欧美一区二区日韩| 99一区二区| 亚洲欧美另类综合偷拍| 亚洲美女在线观看| 欧美在线短视频| 99国产精品久久久久久久| 久久aⅴ国产欧美74aaa| 亚洲一二三区精品| 欧美精品手机在线| 欧美国产91| 国产在线精品一区二区中文| 亚洲精选一区| 亚洲精品色图| 久久久www免费人成黑人精品| 亚洲精品免费一区二区三区| 久久视频这里只有精品| 久久精品夜色噜噜亚洲a∨| 欧美日韩在线高清| 亚洲精品欧洲精品| 亚洲经典视频在线观看| 久久综合久久美利坚合众国| 久久精品免费播放| 国产伦精品一区二区三区免费| 99re视频这里只有精品| 日韩亚洲不卡在线| 欧美激情国产高清| 亚洲国产精品123| 亚洲国产视频一区二区| 久久免费黄色| 欧美国产日韩精品| 亚洲国产精品热久久| 麻豆国产精品va在线观看不卡| 老司机午夜精品视频| 中国av一区| 在线观看一区视频| 久久久99爱| 亚洲一本大道在线| 欧美日韩午夜剧场| 亚洲精品综合久久中文字幕| 亚洲理论电影网| 欧美激情导航| 一本一本久久a久久精品牛牛影视| 99pao成人国产永久免费视频| 欧美精品久久久久a| 日韩视频免费看| 亚洲免费影视| 国产欧美视频一区二区三区| 久久精品国产在热久久| 欧美成人69av| 一本一本久久| 国产视频久久网| 久久这里有精品视频| 亚洲国产天堂久久综合网| 一本色道久久99精品综合 | 久久天堂av综合合色| 久久综合国产精品| 亚洲激精日韩激精欧美精品| 欧美三级小说| 欧美在线观看www| 女女同性精品视频| 一区二区三区四区蜜桃| 国产精品家教| 浪潮色综合久久天堂| 99国产精品久久久久老师| 欧美亚洲自偷自偷| 亚洲高清123| 国产精品高清免费在线观看| 久久久国产精彩视频美女艺术照福利| 亚洲电影欧美电影有声小说| 亚洲——在线| 亚洲国产高清在线| 国产欧美日韩免费看aⅴ视频| 久久婷婷国产麻豆91天堂| 日韩亚洲欧美中文三级| 蜜桃av噜噜一区二区三区| 亚洲专区一区| 女女同性精品视频| 亚洲精品在线免费| 久久久久免费观看| 亚洲午夜激情网站| 亚洲国产精品悠悠久久琪琪| 欧美一区二区观看视频| 亚洲精品乱码久久久久久按摩观| 国产精品老牛| 欧美激情久久久久久| 欧美在线免费视屏| 日韩视频免费在线| 欧美国产日本| 久久精品人人做人人综合| 亚洲精品乱码久久久久久蜜桃91| 国产精品入口福利| 欧美日韩中文在线| 欧美日韩精品三区| 欧美成人四级电影| 免费久久精品视频| 久久精品国产免费| 香蕉av福利精品导航| 亚洲一区综合| 亚洲一二区在线| 99精品欧美| 夜夜爽夜夜爽精品视频| 日韩午夜av电影| 最新日韩中文字幕| 亚洲精品欧美激情| 亚洲日本电影在线| 亚洲国产精品久久久久| 欧美成人免费小视频| 欧美国产日韩xxxxx| 欧美高清视频一区二区三区在线观看| 久久亚洲欧美| 米奇777在线欧美播放| 欧美成人精品在线视频| 猫咪成人在线观看| 久久裸体艺术| 国产精品久久久久9999高清| 久久精品国产久精国产思思| 欧美精品一区三区在线观看| 亚洲一二三四区| 悠悠资源网亚洲青| 国产一区二区无遮挡| 国产亚洲精品资源在线26u| 国产精品亚洲一区二区三区在线| 国产精品女人毛片| 国产亚洲视频在线| 91久久精品www人人做人人爽| 亚洲精品久久嫩草网站秘色| aⅴ色国产欧美| 亚洲一区二区三区777| 午夜天堂精品久久久久| 久久精品午夜| 亚洲国产裸拍裸体视频在线观看乱了中文| 欧美96在线丨欧| 亚洲人成网站影音先锋播放| 一区二区免费看| 亚洲欧美日韩综合| 久久精品视频免费观看| 欧美91大片| 国产精品欧美风情| 樱桃国产成人精品视频| 一本久道久久综合中文字幕| 亚洲欧美日韩国产成人精品影院| 久久久久久穴| 亚洲国产一区在线| 亚洲综合精品四区| 欧美jizzhd精品欧美巨大免费| 国产精品www色诱视频| 国语精品中文字幕| 亚洲一区二区三区高清 | 一区二区欧美日韩| 久久精品国产精品亚洲| 亚洲福利专区| 香蕉成人啪国产精品视频综合网| 麻豆成人精品| 国产精品亚洲不卡a| 亚洲精华国产欧美| 久久精品1区| 洋洋av久久久久久久一区| 久久成人一区二区| 国产精品国产a级| 91久久精品美女高潮| 久久狠狠久久综合桃花| 亚洲精品日韩在线| 久久综合久久综合久久综合| 国产欧美精品日韩精品| 正在播放亚洲一区| 亚洲国产精品久久精品怡红院| 欧美一区二区高清在线观看| 国产精品久久夜| 亚洲午夜国产一区99re久久 | 你懂的网址国产 欧美|