COJ1013 ： WZJ的数据结构（十三）

这道题有这样一个解法：

首先把边依次加到图中，若当前这条边与图中的边形成了环，那么把这个环中最早加进来的边弹出去
并将每条边把哪条边弹了出去记录下来：ntr[i] = j，特别地，要是没有弹出边，ntr[i] = 0;
这个显然是可以用LCT来弄的对吧。
然后对于每个询问，我们的答案就是对l~r中ntr小于l的边求和，并用n减去这个值
正确性可以想一下：
如果一条边的ntr >= l,那么显然他可以与从l ~ r中的边形成环，那么它对答案没有贡献
反之如果一条边的ntr < l那么它与从l ~ r中的边是不能形成环的，那么他对答案的贡献为-1

#include<cstdio>

#include<cctype>

#include<cstring>

#define lc ch[x][0]

#define rc ch[x][1]

#include<algorithm>

using namespace std;

inline int read()

{

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

    for(;!isdigit(c);c=getchar()) if(c=='-') f=-;

    for(;isdigit(c);c=getchar()) x=x*+c-'';

    return x*f;

}

const int maxn=;

const int maxnode=;

const int INF=;

int fa[maxn],pre[maxn],mn[maxn],val[maxn],flip[maxn],ch[maxn][];

void maintain(int x)

{

    mn[x]=x;

    if(val[mn[lc]]<val[mn[x]]) mn[x]=mn[lc];

    if(val[mn[rc]]<val[mn[x]]) mn[x]=mn[rc];

}

void pushdown(int x)

{

    if(!flip[x]) return;

    flip[lc]^=;flip[rc]^=;

    swap(lc,rc);flip[x]=;

}

void rotate(int x,int d)

{

    pushdown(x);int y=pre[x],z=pre[y];

    ch[y][d^]=ch[x][d];pre[ch[x][d]]=y;

    ch[z][ch[z][]==y]=x;pre[x]=z;

    ch[x][d]=y;pre[y]=x;maintain(y);

}

void splay(int x)

{

    int rt=x;while(pre[rt]) rt=pre[rt];

    if(rt!=x)

    {

        fa[x]=fa[rt];fa[rt]=;

        while(pre[x]) pushdown(pre[x]),rotate(x,ch[pre[x]][]==x);

        maintain(x);

    }

    else pushdown(x);

}

void access(int x)

{

    for(int y=;x;x=fa[x])

    {

        splay(x);pre[ch[x][]]=;fa[ch[x][]]=x;

        ch[x][]=y;pre[y]=x;fa[y]=;

        maintain(x);y=x;

    }

}

void makeroot(int x) {access(x);splay(x);flip[x]^=;}

void link(int x,int y){makeroot(x);fa[x]=y;}

void cut(int x,int y)

{

    makeroot(x);access(y);splay(y);

    pre[ch[y][]]=;ch[y][]=;maintain(y);

}

int find(int x)

{

    access(x);splay(x);

    while(ch[x][]) x=ch[x][];

    return x;

}

int query(int x,int y)

{

    makeroot(x);access(y);splay(y);

    return mn[y];

}

int u[maxn],v[maxn],f[maxn],root[maxn],ToT;

int ls[maxnode],rs[maxnode],s[maxnode];

void build(int& y,int x,int l,int r,int pos)

{

    s[y=++ToT]=s[x]+;if(l==r) return;

    ls[y]=ls[x];rs[y]=rs[x];int mid=l+r>>;

    if(pos<=mid) build(ls[y],ls[x],l,mid,pos);

    else build(rs[y],rs[x],mid+,r,pos);

}

int query(int y,int l,int r,int pos)

{

    if(l==r) return s[y];

    int mid=l+r>>;

    if(pos<=mid) return query(ls[y],l,mid,pos);

    return query(rs[y],mid+,r,pos)+s[ls[y]];

}

int main()

{

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

    for(int i=;i<=n;i++) val[i]=INF;

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

    {

        u[i]=read();v[i]=read();val[i+n]=i;

        if(u[i]==v[i]) {f[i]=i;continue;}

        if(find(u[i])!=find(v[i])) link(u[i],i+n),link(i+n,v[i]);

        else

        {

            int k=query(u[i],v[i]);f[i]=k-n;

            cut(u[k-n],k);cut(k,v[k-n]);

            link(u[i],i+n);link(i+n,v[i]);

        }

    }

    for(int i=;i<=m;i++) build(root[i],root[i-],,m,f[i]);

    while(q--)

    {

        int l=read(),r=read();

        printf("%d\n",n-query(root[r],,m,l-)+query(root[l-],,m,l-));

    }

    return ;

}