Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

树状数组+并查集

Posted by yc5_yc at 2012-11-18 22:06:52 on Problem 2985
使用树状数组记录个数为i的集合的数目
在并查集操作的同时更新树状数组
最后二分查找即可
主要代码:
inline int lowbit(int a) {...}
int Sum(int a) {int ret=0;while(a>0){ret+=F[a];a-=lowbit(a);}return ret;}
void Add(int a) {while(a<=N){F[a]++;a+=lowbit(a);}}
void Minn(int a) {while(a<=N){F[a]--;a+=lowbit(a);}}
int Find(int a) {...}
void Union(int a,int b) {
    int x=Find(a),y=Find(b);
	if(x==y) return ;
	Minn(-father[x]);   //根节点永远是负的
	Minn(-father[y]);
	father[x]+=father[y];
	father[y]=x;
	Add(-father[x]);
	num--;
}
int Get(int a) {
	int l=0,r=N+1;
	a=num-a+1;   //因为是第K大
	while(l<r) {
		if(l+1==r) break;
		int mid=(l+r)/2,tmp=Sum(mid);
		if(tmp>=a) r=mid;
		else l=mid;
	}
	return r;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator