Time Limits: 1000 ms Memory Limits: 262144 KB
Description
琥珀色黄昏像糖在很美的远方，思念跟影子在傍晚一起被拉长……
小 B 带着 GF 去逛公园，公园一共有 n 个景点，标号为 1 . . . n。景点之间有 m 条路径相连。
小 B 想选择编号在一段区间 [l, r] 内的景点来游玩，但是如果这些景点的诱导子图形成了环，那么 GF 将会不高兴。
小 B 给出很多个询问 [x, y]，想让你求有多少个区间 [l, r] 满足 x ≤ l, r ≤ y 且不会使 GF不高兴。
Input
第一行为两个整数 n, m，表示景点和路径的数量。 第 2 . . . m + 1 行每行两个整数 ui, vi 表示第 i 路径的两端。 第 m + 2 行是一个整数 q 表示询问的个数，接下来 m 行每行两个整数 xi, yi 表示询问。
Output
q 行，每行一个整数表示答案。
Sample Input
8 9 1 2 2 3 3 1 4 5 5 6 6 7 7 8 8 4 7 2 3 1 8 1 4 3 8
Sample Output
27 8 19
Data Constraint
对于 30% 的数据，n, m ≤ 100。 对于另外 10% 的数据，n = m + 1。 对于另外 10% 的数据，n = m 对于 100% 的数据，n, m ≤ 3 × 10^5, xi ≤ yi，不存在重边、自环，不存在一条边同时存在于两个不同的简单环。
Hint
诱导子图：子图 G′ = (V′, E′)，原图 G = (V, E)。V′ 是 V 的子集，E′ = {(u, v)|u, v ∈V′,(u, v) ∈ E}
Solution
题目意思就是求出不包含环的区间的个数显然对于每个点开始往右最远可达的位置是递增的我们在找环的时候就处理好每个点往右最远可达的不包含环的位置，记为
R
[
i
]
R[i]
R[i]为方便求答案，处理出前缀和数组
S
[
i
]
S[i]
S[i]对于每个询问
l
,
r
l,r
l,r ，我们将
R
[
i
]
<
=
r
R[i]<=r
R[i]<=r 的前缀和求，后面的等差数列求和即可
Code
#include<algorithm>
#include<cstdio>
#define fo(i,a,b) for(int i=a;i<=b;++i)
#define fd(i,a,b) for(int i=a;i>=b;--i)
#define ll long long
using namespace std
;
const int N
=3e5+5;
int n
,m
,q
,num
,cnt
,time
;
int R
[N
],z
[N
],dfn
[N
],low
[N
],last
[N
];
ll S
[N
];
struct edge
{int to
,next
;}e
[2*N
];
void link(int x
,int y
)
{
e
[++num
]=(edge
){y
,last
[x
]},last
[x
]=num
;
}
void Tarjan(int x
,int fa
)
{
dfn
[x
]=low
[x
]=++time
,z
[++z
[0]]=x
;
for(int w
=last
[x
];w
;w
=e
[w
].next
)
{
int y
=e
[w
].to
;
if(y
==fa
) continue;
if(!dfn
[y
])
{
Tarjan(y
,x
),low
[x
]=min(low
[x
],low
[y
]);
if(dfn
[x
]<=low
[y
])
{
int mn
=n
+1,mx
=0,gs
=z
[0];
while(z
[0])
{
int now
=z
[z
[0]--];
mn
=min(mn
,now
);
mx
=max(mx
,now
);
if(now
==y
) break;
}
mn
=min(mn
,z
[z
[0]]);
mx
=max(mx
,z
[z
[0]]);
if(gs
-z
[0]>1) R
[mn
]=min(R
[mn
],mx
-1);
}
}
else low
[x
]=min(low
[x
],dfn
[y
]);
}
}
int main()
{
freopen("graph.in","r",stdin);
freopen("graph.out","w",stdout);
scanf("%d%d",&n
,&m
);
fo(i
,1,m
)
{
int x
,y
;
scanf("%d%d",&x
,&y
);
link(x
,y
),link(y
,x
);
}
fo(i
,1,n
) R
[i
]=n
;
fo(i
,1,n
) if(!dfn
[i
]) Tarjan(1,0);
fd(i
,n
-1,1) R
[i
]=min(R
[i
],R
[i
+1]);
fo(i
,1,n
) S
[i
]=S
[i
-1]+R
[i
]-i
+1;
scanf("%d",&q
);
while(q
--)
{
int x
,y
;
scanf("%d%d",&x
,&y
);
int pos
=upper_bound(R
+x
,R
+y
,y
)-R
;
ll ans
=(ll
)S
[pos
-1]-S
[x
-1]+(ll
)(1+y
-pos
+1)*(ll
)(y
-pos
+1)/2;
printf("%lld\n",ans
);
}
}
