BZOJ3237 AHOI2013连通图（线段树分治+并查集）

把查询看做是在一条时间轴上。那么每条边都有几段存在时间。于是线段树分治就好了。

然而在bzoj上t掉了，不知道是常数大了还是写挂了。

以及brk不知道是啥做数组名过不了编译。

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstdlib>

#include<cstring>

#include<algorithm>

#include<vector>

#include<stack>

using namespace std;

int read()

{

    int x=,f=;char c=getchar();

    while (c<''||c>'') {if (c=='-') f=-;c=getchar();}

    while (c>=''&&c<='') x=(x<<)+(x<<)+(c^),c=getchar();

    return x*f;

}

#define N 100010

#define M 200010

int n,m,k,L[N<<],R[N<<],fa[N],size[N];

bool ans[N];

struct edge{int x,y;}e[M];

vector<edge> tree[N<<];

vector<int> bre[M];

stack<edge> undo[N<<];

void build(int k,int l,int r)

{

    L[k]=l,R[k]=r;

    if (l==r) return;

    int mid=l+r>>;

    build(k<<,l,mid);

    build(k<<|,mid+,r);

}

void add(int k,int l,int r,edge e)

{

    if (L[k]==l&&R[k]==r) {tree[k].push_back(e);return;}

    int mid=L[k]+R[k]>>;

    if (r<=mid) add(k<<,l,r,e);

    else if (l>mid) add(k<<|,l,r,e);

    else add(k<<,l,mid,e),add(k<<|,mid+,r,e);

}

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

void merge(int k,int x,int y)

{

    if (size[x]<size[y]) swap(x,y);

    edge a;a.x=x,a.y=y;

    undo[k].push(a);

    fa[y]=x;size[x]+=size[y];

}

void solve(int k)

{

    int s=tree[k].size();

    for (int i=;i<s;i++)

    {

        int p=find(tree[k][i].x),q=find(tree[k][i].y);

        if (p!=q) merge(k,p,q);

    }

    if (size[find()]==n) for (int i=L[k];i<=R[k];i++) ans[i]=;

    else if (L[k]<R[k]) solve(k<<),solve(k<<|);

    while (!undo[k].empty())

    {

        edge a=undo[k].top();

        fa[a.y]=a.y;size[a.x]-=size[a.y];

        undo[k].pop();

    }

}

int main()

{

    n=read(),m=read();

    for (int i=;i<=m;i++) e[i].x=read(),e[i].y=read();

    k=read();

    for (int i=;i<=k;i++)

    {

        int s=read();

        for (int j=;j<=s;j++)

        {

            int x=read();

            bre[x].push_back(i);

        }

    }

    build(,,k);

    for (int i=;i<=m;i++)

    {

        int s=bre[i].size();

        if (s==) add(,,k,e[i]);

        else

        {

            if (bre[i][]->=) add(,,bre[i][]-,e[i]);

            for (int j=;j<s;j++)

            if (bre[i][j]->=bre[i][j-]+) add(,bre[i][j-]+,bre[i][j]-,e[i]);

            if (bre[i][s-]+<=k) add(,bre[i][s-]+,k,e[i]);

        }

    }

    for (int i=;i<=n;i++) fa[i]=i,size[i]=;

    solve();

    for (int i=;i<=k;i++)

    if (ans[i]) printf("Connected\n");

    else printf("Disconnected\n");

    return ;

}