随笔 - 97, 文章 - 22, 评论 - 81, 引用 - 0
数据加载中……

PKU 2985 The k-th Largest Group

题目链接:http://poj.org/problem?id=2985

/*
题意:
    给定N(N <= 200000)个操作,每个操作是以下两种形式:
0 x y : 合并x所在的组和y所在的组,如果x和y同组,不合并。
1 k:输出第k大的组的元素个数。

解法:
树状数组 + 并查集

思路:
     将元素的个数对应树状数组的下标,每次合并操作,在树状
数组中对应两个集合大小的位置分别减1,两集合之后的位置+1,
询问操作只需要二分答案,然后每次统计比k大的数的个数判可行
即可。
*/


#include 
<iostream>

using namespace std;

#define maxn 200010

int c[maxn];
int prev[maxn], num[maxn];
int n;

int lowbit(int x) {
    
return x & (-x);
}

void add(int pos, int num) {
    
while(pos <= n) {
        c[pos] 
+= num;
        pos 
+= lowbit(pos);
    }

}


int sum(int pos) {
    
int s = 0;
    
while(pos > 0{
        s 
+= c[pos];
        pos 
-= lowbit(pos);
    }

    
return s;
}


int find(int x) {
    
int q = x;
    
while(x != prev[x]) {
        x 
= prev[x];
    }

    
return x;
}


void Union(int x, int y) {
    x 
= find(x);
    y 
= find(y);

    
if(x != y) {
        
if(num[x] == num[y])
            add(num[x], 
-2);
        
else {
            add(num[x], 
-1);
            add(num[y], 
-1);
        }

        add(num[x] 
+ num[y], 1);

        
if(num[x] < num[y]) {
            prev[x] 
= y;
            num[y] 
+= num[x];
        }
else {
            prev[y] 
= x;
            num[x] 
+= num[y];
        }

    }

}



int Query(int k) {
    
int l = 1;
    
int r = n;
    
int ans = 0;
    
int all = sum(n);
    
while(l <= r) {
        
int m = (l + r) >> 1;
        
if(k <= all - sum(m-1)) {
            l 
= m + 1;
            ans 
= m;
        }
else
            r 
= m - 1;
    }

    
return ans;
}


int main() {
    
int i, m;
    
int op, x, y;
    
while(scanf("%d %d"&n, &m) != EOF) {
        
for(i = 1; i <= n; i++{
            c[i] 
= 0;
            prev[i] 
= i;
            num[i] 
= 1;
        }

        add(
1, n);
        
while(m--{
            scanf(
"%d"&op);
            
if(op == 0{
                scanf(
"%d %d"&x, &y);
                Union(x, y);
            }
else {
                scanf(
"%d"&x);
                printf(
"%d\n", Query(x));
            }

        }


    }

    
return 0;
}

posted on 2011-04-07 09:31 英雄哪里出来 阅读(1210) 评论(2)  编辑 收藏 引用 所属分类: 树状数组

评论

# re: PKU 2985 The k-th Largest Group  回复  更多评论   

那个x与-x为与位运算时用来干嘛的啊?
2012-07-11 21:08 | 秋秋

# re: PKU 2985 The k-th Largest Group[未登录]  回复  更多评论   

真的会死很多脑细胞啊周仁兄。。
2013-06-02 01:41 | Grace

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理