agc002d

整体二分裸题

#include <bits/stdc++.h>
using namespace std;
#define N 110000
#define PA pair<int,int>
int n,m,Q;
int X[N],Y[N],ans[N];
struct node
{
    int x,y,tar,pos;
}a[N],b[N];
struct Ufs
{
    int now;
    int fa[N],size[N],mem[N];
    void init()
    {
        for(int i=1;i<=n;i++)
            fa[i]=i,size[i]=1;
    }
    int find(int x){return fa[x]==x ? x : find(fa[x]);}
    void move(int tar)
    {
        int x,y;
        while(now<tar)
        {
            now++;
            if((x=find(X[now]))==(y=find(Y[now])))
                mem[now]=0;
            else
            {
                if(size[y]>size[x])swap(x,y);
                size[x]+=size[y];
                fa[y]=x;
                mem[now]=y;
            }
        }
        while(now>tar)
        {
            if(x=mem[now])
            {
                size[fa[x]]-=size[x];
                fa[x]=x;
            }
            now--;
        }
    }
    int calc(int x,int y)
    {
        x=find(x);y=find(y);
        if(x==y)return size[x];
        return size[x]+size[y];
    }
}ufs;
void solve(int l1,int r1,int l2,int r2)
{
    if(l2>r2)return;
    if(l1==r1)
    {
        for(int i=l2;i<=r2;i++)
            ans[a[i].pos]=l1;
        return;
    }
    int mid=(l1+r1)>>1,lm=l2,rm=r2;
    ufs.move(mid);
    for(int i=l2;i<=r2;i++)
    {
        if(ufs.calc(a[i].x,a[i].y)>=a[i].tar)
            b[lm++]=a[i];
        else b[rm--]=a[i];
    }
    for(int i=l2;i<=r2;i++)a[i]=b[i];
    solve(l1,mid,l2,lm-1);
    solve(mid+1,r1,rm+1,r2);
}
int main()
{
    //freopen("tt.in","r",stdin);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
        scanf("%d%d",&X[i],&Y[i]);
    scanf("%d",&Q);
    for(int i=1;i<=Q;i++)
    {
        scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].tar);
        a[i].pos=i;
    }
    ufs.init();
    solve(1,m,1,Q);
    for(int i=1;i<=Q;i++)
        printf("%d\n",ans[i]);
    return 0;
}