题
http://codeforces.com/contest/901/problem/C
codeforces 901C
解
首先因为图中没有偶数长度的环，所以：
1.图中的环长度全是奇数，也就是说，只要这个子图中存在环，那么这个子图肯定是不合法的。
2.图中任意两个环没有公共边，否则合成的环的长度必然是偶数
所以用一个dfs可以找到所有环
然后对于每个环，求出这个环里面的最大值 li 和最小值 ri 。那么显然对于区间 [1,li] 中的任意位置 x，这个数的右区间的取值范围必然小于 ri，
所以可以通过一个线段树找出所有左节点对应的右节点最大值，这里对于节点 x ，记其对应的右节点最大值为 rib[x]。
对于q个询问
设给定询问的左端点为 ql，右端点为 qr
那么二分找到 [ql,qr]区间中的第一个数，她的右端点最大值大于等于 qr，记这个位置为plc
那么 [ql,qr] 这个区间可以被分为 [ql,plc-1] [plc,qr]，分别计算答案，
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <queue>
using namespace std;
typedef long long ll;
const int INF=1e9+44;
const int M=3e5+44;
struct node{
int u,v;
int next;
}edge[2*M];
queue<int> que;
int head[M],num;
int dg[M];
void addedge(int u,int v)
{
edge[num].u=u;
edge[num].v=v;
edge[num].next=head[u];
head[u]=num++;
}
void init()
{
num=0;
memset (head,-1,sizeof(head));
}
int n,m;
int tree[M*3],tag[M*3];
void build(int rt,int li,int ri)
{
tag[rt]=INF;
if(li==ri)
{
tree[rt]=n;
return ;
}
int mid=(li+ri)>>1,lc=(rt<<1),rc=(rt<<1)+1;
build(lc,li,mid);
build(rc,mid+1,ri);
tree[rt]=min(tree[lc],tree[rc]);
}
void pushdown(int rt,int li,int ri)
{
if(li==ri)
{
tag[rt]=INF;
return ;
}
int mid=(li+ri)>>1,lc=(rt<<1),rc=(rt<<1)+1;
tag[lc]=min(tag[lc],tag[rt]);
tag[rc]=min(tag[rc],tag[rt]);
tag[rt]=INF;
tree[lc]=min(tree[lc],tag[lc]);
tree[rc]=min(tree[rc],tag[rc]);
}
void update(int rt,int li,int ri,int lq,int rq,int val) //change to val
{
if(lq<=li && ri<=rq)
{
tag[rt]=min(tag[rt],val);
tree[rt]=min(tree[rt],val);
return ;
}
int mid=(li+ri)>>1,lc=(rt<<1),rc=(rt<<1)+1;
if(tag[rt]!=INF)
pushdown(rt,li,ri);
if(mid>=lq)
update(lc,li,mid,lq,rq,val);
if(mid+1<=rq)
update(rc,mid+1,ri,lq,rq,val);
tree[rt]=min(tree[lc],tree[rc]);
}
int query(int rt,int li,int ri,int lq,int rq) //get min val
{
int ret=INF;
if(lq<=li && ri<=rq)
return tree[rt];
int mid=(li+ri)>>1,lc=(rt<<1),rc=(rt<<1)+1;
if(tag[rt]!=INF)
pushdown(rt,li,ri);
if(mid>=lq)
ret=min(ret,query(lc,li,mid,lq,rq));
if(mid+1<=rq)
ret=min(ret,query(rc,mid+1,ri,lq,rq));
return ret;
}
int stk[M],lstk,dlt[M],vis[M];
int dfs(int rt,int pa)
{
// cout<<"rt:"<<rt<<endl;
int v;
vis[rt]=1,stk[++lstk]=rt;
for(int i=head[rt];i!=-1;i=edge[i].next)
{
v=edge[i].v;
if(v==pa || dlt[v]) continue;
if(vis[v])
{
int li=INF,ri=0;
while(lstk>0)
{
// cout<<stk[lstk]<<" . ";
dlt[stk[lstk]]=1;
li=min(li,stk[lstk]),ri=max(ri,stk[lstk]);
lstk--;
if(stk[lstk+1]==v)
break;
}
// cout<<endl;
// cout<<li<<' '<<ri<<endl;
update(1,1,n,1,li,ri-1);
}
else
dfs(v,rt);
}
if(dlt[rt]==0)
lstk--;
}
void makeTree()
{
build(1,1,n);
memset(vis,0,sizeof(vis));
memset(dlt,0,sizeof(dlt));
for(int i=1;i<=n;i++)
if(vis[i]==0)
dfs(i,-1);
}
int q;
int rib[M];
ll pre[M];
void solve(int qli,int qri)
{
ll ans;
int i,j;
ll cnt1,cnt2;
int li=qli-1,ri=qri,mid;
while(li<ri-1)
{
mid=(li+ri)>>1;
if(rib[mid]>=qri)
ri=mid;
else li=mid;
}
cnt1=li-qli+1; cnt2=qri-li;
ans=pre[li]-pre[qli-1]-(2*qli-3+cnt1)*cnt1/2+(1+cnt2)*cnt2/2;
printf("%I64d
",ans);
}
int main()
{
int a,b;
init();
scanf("%d%d",&n,&m);
memset(dg,0,sizeof(dg));
for(int i=1;i<=m;i++)
{
scanf("%d%d",&a,&b);
addedge(a,b);
addedge(b,a);
dg[a]++,dg[b]++;
}
makeTree();
for(int i=1;i<=n;i++)
rib[i]=query(1,1,n,i,i);
pre[0]=0;
for(int i=1;i<=n;i++)
pre[i]=pre[i-1]+rib[i];
// for(int i=1;i<=n;i++)
// cout<<rib[i]<<' ';
// cout<<endl;
scanf("%d",&q);
for(int i=1;i<=q;i++)
{
scanf("%d%d",&a,&b);
solve(a,b);
}
return 0;
}