CodeChef - GERALD07 Chef and Graph Queries

題面

題意

給出一張無向圖，每次詢問編号L到R的邊，問這些邊連上之後一共有幾個聯通塊。

做法

聽說可以用分塊加可持久并查集來做，可惜我不會。

我用的是LCT加樹狀數組，離線來做。

求連通塊的個數可以考慮轉化為求此時圖中樹邊的個數，我們可以将詢問按照右端點排序，然後随着詢問的右端點的右移，來不斷向LCT中加邊，此時LCT中的邊都是樹邊，将樹邊存入樹狀數組中，每次詢問L,R這段區間内樹邊的數量即可。

若向LCT中加邊之後會構成環，則将環上編号最小的邊去掉（貪心的去想，要使每次詢問的樹邊數量盡可能大，故應保留編号盡可能大的樹邊）即可。

代碼

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#define P pair<int,int>
#define mp make_pair
#define fi first
#define se second
#define C ch=getchar()
#define INF 0x3f3f3f3f
#define N 400100
#define M 200100
using namespace std;

int T,n,m,Q,son[N][],fa[N],mn[N],a[M],b[M],sz[M],an[M],faz[M],sum;
bool fz[N];
char ch;
vector<P>pos[N];

inline int read(){static int res;for(C;ch<'0';C);for(res=ch-'0',C;ch>='0';res=res*+ch-'0',C);return res;}
inline void write(int u){if(u>) write(u/);putchar(u%+'0');}
inline void Min(int &u,int v){if(v<u) u=v;}
inline int lb(int u){return u&(-u);}
inline void add(int u,int v){for(; u<=m; u+=lb(u)) sz[u]+=v;}
inline int ask(int u){int res=;for(; u; u-=lb(u)) res+=sz[u];return res;}
inline int ff(int u){return u==faz[u]?u:faz[u]=ff(faz[u]);}
inline bool as(int u){return u==son[fa[u]][];}
inline bool ar(int u){return u!=son[fa[u]][] && u!=son[fa[u]][];}

inline void up(int u)
{
    if(!u) return;
    mn[u]=u;
    if(son[u][]) Min(mn[u],mn[son[u][]]);
    if(son[u][]) Min(mn[u],mn[son[u][]]);
}

inline void down(int u)
{
    if(fz[u])
    {
        swap(son[u][],son[u][]);
        fz[son[u][]]^=;
        fz[son[u][]]^=;
        fz[u]=;
    }
}

inline void rot(int u)
{
    down(fa[u]),down(u);
    int p=fa[u],d=as(u);
    if(!ar(p)) son[fa[p]][as(p)]=u;
    fa[u]=fa[p];
    fa[p]=u;
    fa[son[u][!d]]=p;
    son[p][d]=son[u][!d];
    son[u][!d]=p;
    up(p),up(u);
}

inline void splay(int u)
{
    int p;
    for(; !ar(u);)
    {
        p=fa[u];
        if(!ar(p))
            as(u)==as(p)?rot(p):rot(u);
        rot(u);
    }
}

inline void acc(int u){int p,q;for(p=u,q=; p; q=p,p=fa[p]) splay(p),down(p),son[p][]=q,up(p);}
inline void mr(int u){acc(u),splay(u),fz[u]^=;}
inline int fr(int u){acc(u),splay(u);for(down(u); son[u][]; u=son[u][],down(u));return u;}
inline void spl(int u,int v){mr(u),acc(v),splay(v);}
inline void link(int u,int v){mr(u),fa[u]=v;}
inline void cut(int u,int v){spl(u,v),fa[u]=son[v][]=,up(v);}

inline void ade(int w)
{
    int u=a[w],v=b[w];
    if(u==v) return;
    add(w,);
    if(ff(u)!=ff(v))
    {
        faz[ff(u)]=ff(v);
        sum++;
        link(u+m,w),link(w,v+m);
        return;
    }
    int tmp;
    spl(u+m,v+m);
    tmp=mn[v+m];
    cut(a[tmp]+m,tmp),cut(b[tmp]+m,tmp);
    add(tmp,-);
    link(u+m,w),link(w,v+m);
}

int main()
{
    int i,j,p,q;
    T=read();
    while(T--)
    {
        sum=;
        memset(sz,,sizeof(sz));
        memset(fa,,sizeof(fa));
        memset(son,,sizeof(son));
        memset(fz,,sizeof(fz));
        n=read(),m=read(),Q=read();
        for(i=;i<=n;i++) mn[i]=faz[i]=i;
        for(i=;i<=m;i++) mn[i+n]=i;
        for(i=; i<=m; i++)
            a[i]=read(),b[i]=read();
        for(i=; i<=Q; i++)
            p=read(),q=read(),pos[q].push_back(mp(p,i));
        for(i=;i<=m;i++)
        {
            ade(i);
            for(j=;j<pos[i].size();j++)
            {
                an[pos[i][j].se]=sum-ask(pos[i][j].fi-);
            }
            pos[i].clear();
        }
        for(i=;i<=Q;i++) write(n-an[i]),puts("");
    }
}