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