【CodeForces】901 C. Bipartite Segments

小程序：扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序

【题目】C. Bipartite Segments

【题意】给定n个点m条边的无向连通图，保证不存在偶数长度的简单环。每次询问区间[l,r]中包含多少子区间[x,y]满足只保留[x,y]之间的点和边构成的图是一个二分图。

【算法】Tarjan缩点（找环）

【题解】如果两个奇数长度的环相交，会得到一个偶数长度的简单环。所以原图是不存在偶数长度环的 仙人掌 （每条边只属于一个简单环）。

二分图的定义：一个图是二分图当且仅当不存在奇数长度的环。在当前仙人掌上，二分图实际上 要求选择的点不存在环 。

也就是对于图上已有的每个环x有最小编号点min(x)和最大编号点max(x)，区间不能同时包含min(x)和max(x)。（找环可以用Tarjan缩点）

为了统计区间数量，我们预处理r[i]表示以i为区间左端点，区间右端点最远到达r[i]，初始r[min(x)]=max(x)-1，然后统计后缀最小值就可以得到r[]数组。

对于询问的区间i∈[l,r]，若i>r则ans+=r-i+1，否则ans+=r[i]-i+1。容易发现r[]数组 单调递增 ，所以可以二分求解转折点。

复杂度O(n log n)。

边编号不能为0 QAQ

#include<cstdio>

#include<cstring>

#include<cctype>

#include<algorithm>

#define ll long long

using namespace std;

int read(){

    char c;int s=,t=;

    while(!isdigit(c=getchar()))if(c=='-')t=-;

    do{s=s*+c-'';}while(isdigit(c=getchar()));

    return s*t;

}

const int maxn=;

int tot=,first[maxn],low[maxn],dfn[maxn],dfsnum=,c[maxn],n,m,mins[maxn],maxs[maxn],s[maxn],d[maxn];

ll sum[maxn],ss[maxn];

bool iscut[maxn];

struct edge{int v,from;}e[maxn*];

void insert(int u,int v){tot++;e[tot].v=v;e[tot].from=first[u];first[u]=tot;}//

void tarjan(int x,int fa){

    low[x]=dfn[x]=++dfsnum;

    for(int i=first[x];i;i=e[i].from)if(e[i].v!=fa){

        if(!dfn[e[i].v]){

            tarjan(e[i].v,x);

            low[x]=min(low[x],low[e[i].v]);

            if(low[e[i].v]>dfn[x])iscut[i]=iscut[i^]=;

        }else low[x]=min(low[x],dfn[e[i].v]);

    }

}

void dfs(int x,int y){

    c[x]=y;d[y]++;

    for(int i=first[x];i;i=e[i].from)if(!iscut[i]&&!c[e[i].v])dfs(e[i].v,y);

}

int main(){

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

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

        int u=read(),v=read();

        insert(u,v);insert(v,u);

    }

    tarjan(,);int cnt=;

    for(int i=;i<=n;i++)if(!c[i])dfs(i,++cnt);

    memset(mins,0x3f,sizeof(mins));

    for(int i=;i<=n;i++){

        mins[c[i]]=min(mins[c[i]],i);

        maxs[c[i]]=max(maxs[c[i]],i);

    }

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

    for(int i=;i<=cnt;i++)if(d[i]>)s[mins[i]]=maxs[i]-;

    for(int i=n-;i>=;i--)s[i]=min(s[i],s[i+]);

    for(int i=;i<=n;i++)sum[i]=sum[i-]+(s[i]-i+),ss[i]=ss[i-]+i;

    int q=read();

    while(q--){

        int u=read(),v=read();

        int x=lower_bound(s+u,s+v+,v)-s;

        ll ans=;

        ans+=sum[x-]-sum[u-];

        ans+=1ll*(v-x+)*(v+)-(ss[v]-ss[x-]);

        printf("%lld\n",ans);

    }

    return ;

}