| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
树状数组+并查集使用树状数组记录个数为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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator