shz

pku 2985 The k-th Largest Group

  1#include<iostream>
  2#define max 200005
  3using namespace std;
  4int set[max],rank[max];
  5int n,m,num1,num2;
  6struct
  7{
  8  int left;
  9  int right;
 10  int num;
 11}tree[max*3];
 12int findset(int x)
 13{
 14  if(set[x]!=x)
 15  set[x]=findset(set[x]);
 16  return set[x];
 17}
 18void Init(int n)
 19{
 20  int i;
 21  for(i=1;i<=n;i++)
 22  {
 23    rank[i]=-1;
 24    set[i]=i;
 25  }
 26}
 27
 28void link(int a,int b)
 29{
 30  int tmp=rank[a]+rank[b];
 31  if(rank[a]<rank[b])
 32  {
 33    set[b]=a;
 34    rank[a]=tmp;
 35  }
 36  else
 37  {
 38    set[a]=b;
 39    rank[b]=tmp;
 40  }
 41}
 42void Union(int a,int b)
 43{
 44  link(findset(a),findset(b));
 45}
 46void Creat(int l,int r,int p)
 47{
 48
 49    tree[p].left=l;
 50    tree[p].right=r;
 51    if(l==1) tree[p].num=n;
 52    else     tree[p].num=0;
 53    if(l==r) return ;
 54    int mid=(l+r)/2;
 55    Creat(l,mid,2*p);
 56    Creat(mid+1,r,2*p+1);
 57}
 58void find(int p,int k)
 59{
 60  if(tree[p].left==tree[p].right)
 61  {
 62    printf("%d\n",tree[p].left);
 63    return ;
 64  }
 65  if(tree[2*p].num<k)
 66  find(2*p+1,k-tree[2*p].num);
 67  else
 68  find(2*p,k);
 69}
 70void delet(int x,int p)
 71{
 72  tree[p].num--;
 73  if(tree[p].left==tree[p].right)  return ;
 74  if(x<=tree[2*p].right)
 75  delet(x,2*p);
 76  else
 77  delet(x,2*p+1);
 78}
 79void add(int x,int p)
 80{
 81  tree[p].num++;
 82  if(tree[p].left==tree[p].right)  return ;
 83  if(x<=tree[2*p].right)
 84  add(x,2*p);
 85  else
 86  add(x,2*p+1);
 87}
 88int main()
 89{
 90  int i,j,c,k;
 91  while(scanf("%d%d",&n,&m)!=EOF)
 92    {
 93      Init(n);
 94      Creat(1,n,1);
 95      while(m--)
 96      {
 97             scanf("%d",&c);
 98             if(c==1)
 99             {
100                scanf("%d",&k);
101                find(1,tree[1].num-k+1);
102             }
103             else
104             {
105                scanf("%d%d",&i,&j);
106                if(findset(i)!=findset(j))
107                {
108                  delet(-rank[set[i]],1);
109                  delet(-rank[set[j]],1);
110                  add(-rank[set[i]]-rank[set[j]],1);
111                  Union(i,j);
112                }
113              }
114        }
115    }
116    return 0;
117}
118                  
119

posted on 2008-02-21 18:59 shengzan 阅读(226) 评论(1)  编辑 收藏 引用

Feedback

# re: pku 2985 The k-th Largest Group 2008-02-21 19:03 shengzan

en  回复  更多评论   


只有注册用户登录后才能发表评论。
网站导航:   博客园   博客园最新博文   博问   管理