【bzoj3514】Codechef MARCH14 GERALD07加强版

2015.06.15 08:57 Mon | 24次阅读 | 旧日oi | 固定链接 | 源码

Description

N个点M条边的无向图,询问保留图中编号在[l,r]的边的时候图中的联通块个数。强制在线

题解

这题很经典啊,昨天noi模拟赛就出这个的弱化版了,然后别人都a了,我写个暴力才50……
离线的话莫队也能做?
在线的话做法比较巧妙,我们用lct维护图的连通性,同时记录一个st数组,这个数组表示如果加入这条边时形成了环,那么就弹出一条这个环里最先加入的边,st[i]记录弹出这个边的编号,然后切断st[i]这个边,加入新的这条边,如果是自环,st[i]=i,如果没形成环,st[i]=0,然后就是正常的lct操作了,其中加点的做法很巧妙,值得学习一下。
处理完毕m条边后,把st数组建成一颗主席树,范围(0,m).
这个st[i]是什么意思呢?我们考虑一个询问【l,r】中哪些边是有用的,首先,st[i]=0的边肯定有用,然后,所有st[i]l的边都是没用的,因为st[i]要加进去,所以i加进去一定会形成环。于是每个查询就相当于在主席树上查[l,r]之间st值小于x的个数。
虽然38秒,但是1A了还不错~

我的程序

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define N 200005
#define inf 0x7fffffff
#define isroot(x) (son[fa[x]][0]!=x&&son[fa[x]][1]!=x)
#define is(x) (son[fa[x]][1]==x)
#define ls son[x][0]
#define rs son[x][1]
int n,m,k,type,sz;
int u[N],v[N];
int val[N<<1],mn[N<<1],st[N<<1],fa[N<<1],son[N<<1][2],stack[N<<1];
bool rev[N<<1];
int root[N],sum[N*50],lson[N*50],rson[N*50];
void add(int &x,int t,int l,int r,int pos)
{
    sum[x=++sz]=sum[t]+1;
    if(l==r) return;
    int mid=(l+r)>>1;
    if(pos<=mid) rson[x]=rson[t],add(lson[x],lson[t],l,mid,pos);
    else lson[x]=lson[t],add(rson[x],rson[t],mid+1,r,pos);
}
int get_ans(int x,int y,int l,int r,int pos)
{
    if(r==pos) return sum[x]-sum[y];
    int mid=(l+r)>>1;
    if(pos<=mid) return get_ans(lson[x],lson[y],l,mid,pos);
    else return sum[lson[x]]-sum[lson[y]]+get_ans(rson[x],rson[y],mid+1,r,pos);
}
int find(int x)
{
    while(fa[x]) x=fa[x];
    return x;
}
void reverse(int x)
{
    if(!x) return;
    swap(ls,rs);
    rev[x]^=1;
}
void pushdown(int x)
{
    if(rev[x])
    {
        reverse(ls);
        reverse(rs);
        rev[x]=0;
    }
}
void pushpath(int x)
{
    int top;
    for(top=0;!isroot(x);x=fa[x]) stack[++top]=x;
    stack[++top]=x; 
    while(top) pushdown(stack[top--]);
}
void pushup(int x)
{
    mn[x]=x;
    if(val[mn[ls]]<val[mn[x]]) mn[x]=mn[ls];
    if(val[mn[rs]]<val[mn[x]]) mn[x]=mn[rs];
}
void link(int x,int y,int d)
{
    fa[x]=y;son[y][d]=x;
}
void rotate(int x)
{
    int y=fa[x],z=fa[y],id=is(x),t=son[x][!id];
    if(isroot(y)) fa[x]=z;else link(x,z,is(y));
    link(y,x,!id);link(t,y,id);
    fa[0]=son[0][0]=son[0][1]=0;pushup(y);
}
void splay(int x)
{
    pushpath(x);
    int y,z;
    while(!isroot(x))
    {
        y=fa[x],z=fa[y];
        if(isroot(y))
        {
            rotate(x);
            break;
        }
        rotate(is(y)==is(x)?y:x);rotate(x);
    }
    pushup(x);
}
void access(int x)
{
    int p=0;
    while(x)
    {
        splay(x);
        rs=p;pushup(x);
        p=x;x=fa[x];
    }
}
void makeroot(int x)
{
    access(x);splay(x);reverse(x);
}
int query(int x,int y)
{
    makeroot(y);access(x);splay(x);
    return mn[x];
}
void cut(int x,int y)
{
    makeroot(y);access(x);splay(x);
    fa[ls]=0;ls=0;
}
void link(int x,int y)
{
    makeroot(x);
    fa[x]=y;
}
void work()
{
    int tot=n;
    for(int i=1;i<=m;i++)
    {
        if(u[i]==v[i])
        {
            st[i]=i;
            continue;
        }
        if(find(u[i])==find(v[i]))
        {
            int t=query(u[i],v[i]),x=val[t];
            st[i]=x;
            cut(u[x],t);cut(v[x],t);
        }
        val[++tot]=i;mn[tot]=tot;
        link(u[i],tot);link(v[i],tot);
    }
    for(int i=1;i<=m;i++) add(root[i],root[i-1],0,m,st[i]);
}
int main()
{
    cin>>n>>m>>k>>type;
    for(int i=0;i<=n;i++) val[mn[i]=i]=inf;
    for(int i=1;i<=m;i++) scanf("%d%d",&u[i],&v[i]);
    work();
    for(int ans=0,l,r,i=1;i<=k;i++)
    {
        scanf("%d%d",&l,&r);
        if(type) l^=ans,r^=ans;
        printf("%d\n",ans=n-get_ans(root[r],root[l-1],0,m,l-1));
    } 
}```