ZOJ 4100 浙江省第16届大学生程序设计竞赛 A题 Vertices in the Pocket

题意

$n$ 个点，一开始没有边，有两种操作
一是连接点 $(x, y)$
二是假如向图中加入 $k$ 条边，问最小、最大的联通块个数分别是多少

题解

最少联通块个数，就是加入的边都连接两个不同的联通块
最多联通块个数，首先要把各个联通块补成完全图，如果还有剩的边，则按照联通块的大小从大到小排序，每次合并最大的两个联通块，直到没有边剩下
问题的关键是如何求解最多联通块个数，暴力排序是肯定不行的
线段树+二分
$S e g [l, r]$ 表示将大小介于 $[l, r]$ 的联通块合并为一个联通块
我们要维护那些信息呢？
首先要想到的是这个合并成完全图的过程中要新加入的边的数量
然后，用两个儿子维护父亲结点时，发现还需要维护大小介于 $[l, r]$ 的联通块的<stron>的数量
这是因为 $f a_{边} = S o n 1_{边} + S o n 2_{边} + S o n 1_{点} * S o n 2_{点}$
很好理解，两个儿子需要的边要继承到父亲，新需要的边就是两个儿子中的点两两连边
$f a_{点} = S o n 1_{点} * S o n 2_{点}$
还需要维护一个变量，我们最终要求的是合并的联通块的个数，所以还需要维护大小介于 $[l, r]$ 的联通块的联通块个数
当线段树走到叶子节点 $x$ 时，我们再用二分求解需要将多少个大小为 $x$ 的联通块合并
复杂度 $O (l o g n)$ </stron>

细节见代码

代码

#include<bits/stdc++.h>
#define N 100010
#define INF 0x3f3f3f3f
#define eps 1e-10
// #define pi 3.141592653589793
// #define P 1000000007
#define LL long long
#define pb push_back
#define fi first
#define se second
#define cl clear
#define si size
#define lb lower_bound
#define ub upper_bound
#define mem(x) memset(x,0,sizeof x)
#define sc(x) scanf("%d",&x)
#define scc(x,y) scanf("%d%d",&x,&y)
#define sccc(x,y,z) scanf("%d%d%d",&x,&y,&z)
using namespace std;
typedef pair<int,int> pp;

int fa[N],num[N],sz[N],T,n,m,op,x,y;LL tg,pv,pe,pt;
LL cal[N];

int getfa(int x){
    return fa[x]==x?x:fa[x]=getfa(fa[x]);
}

struct node{
    LL v,e,t;			//联通块个数、边的个数、点的个数
}a[N<<2];

void up(int x,int l,int r,int p,int d){
    if (l==r){
        a[x].v+=d;
        a[x].t=a[x].v*l;
        a[x].e=cal[a[x].t]-cal[l]*a[x].v;
        return;
    }
    int t=l+r>>1;
    if (p<=t) up(x<<1,l,t,p,d);else
        up(x<<1|1,t+1,r,p,d);
    a[x].v=a[x<<1].v+a[x<<1|1].v;
    a[x].t=a[x<<1].t+a[x<<1|1].t;
    a[x].e=a[x<<1].t*a[x<<1|1].t+a[x<<1].e+a[x<<1|1].e;
}

void spy(int x,int l,int r){
    if (l==r){
        int k=l,ans=1;
        int l=1,r=a[x].v;
        while(l<=r){
            int t=l+r>>1;
            LL tm=cal[k*t]-cal[k]*t+pe+pt*k*t;
            if (tm>=tg) ans=t,r=t-1;
                else    l=t+1;
        }
        pv+=ans;
        return;
    }else{
        int t=l+r>>1;
        if (a[x<<1|1].e+pe+a[x<<1|1].t*pt>=tg)
            spy(x<<1|1,t+1,r);
        else{
            pe+=a[x<<1|1].e+a[x<<1|1].t*pt;
            pt+=a[x<<1|1].t;
            pv+=a[x<<1|1].v;
            spy(x<<1,l,t);
        }
    }
}

int main(){
    for (LL i=1;i<N;i++) cal[i]=i*(i-1)/2; //点个数为i的完全图的边的个数
    sc(T);
    while(T--){
        scc(n,m); int cnt=n; LL lack=0;
        for (int i=1;i<=n;i++) fa[i]=i,num[i]=0,sz[i]=1;
        for (int i=1;i<=(n<<2);i++) a[i]=node{0,0,0};
        up(1,1,n,1,n);    
        while(m--){
            sc(op);
            if (op==1){
                scc(x,y); 
                int a=getfa(x),b=getfa(y);                
                if (a!=b){
                    fa[b]=a;  //lack表示补成完全图需要边的个数
                    lack-=cal[sz[a]]-num[a]+cal[sz[b]]-num[b];
                    up(1,1,n,sz[a],-1);  up(1,1,n,sz[b],-1);
                    num[a]+=num[b]+1;
                    sz[a]+=sz[b];
                    up(1,1,n,sz[a],1);
                    lack+=cal[sz[a]]-num[a];
                    cnt--;		//当前联通块个数
                }else{
                    num[a]++;
                    lack--;
                }
            }else{
                LL x; scanf("%lld",&x);
                printf("%lld ",x>=cnt-1?1ll:cnt-x);
                if (x<=lack) printf("%d\n",cnt);else{
                    x-=lack; tg=x; pv=pe=pt=0;
                    spy(1,1,n);
                    printf("%d\n",cnt-pv+1);
                }
            }
        }
    }
}