304725: CF901C. Bipartite Segments

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Bipartite Segments

题意翻译

给你一个有$n$个点的无向图,没有偶环。我们把节点标记为$1..n$。 你需要回答$q$个询问,每一个询问由一个区间`[L,R](1<=L<=R<=n)`组成,你需要计算出有多少个点对`[x,y](L<=x<=y<=R)`,满足由`[x,y]`之间的所有点组成的子图是一个二分图。 输入数据第一行两个整数 $n,m$ ($1\le n\le 3\times 10^5,1\le m\le 3\times10^5$)代表点数和边数 接下来的$m$行,每行两个整数,表示一条无向边,保证无自环,保证无重边 一个整数 $q(1\le q\le3\times 10^5)$,表示询问个数 接下来$q$行,每行一个询问`[L,R]` 对于每个询问,输出一个整数,表示满足条件的点对`[x,y]`的个数

题目描述

You are given an undirected graph with $ n $ vertices. There are no edge-simple cycles with the even length in it. In other words, there are no cycles of even length that pass each edge at most once. Let's enumerate vertices from $ 1 $ to $ n $ . You have to answer $ q $ queries. Each query is described by a segment of vertices $ [l;r] $ , and you have to count the number of its subsegments $ [x;y] $ ( $ l<=x<=y<=r $ ), such that if we delete all vertices except the segment of vertices $ [x;y] $ (including $ x $ and $ y $ ) and edges between them, the resulting graph is bipartite.

输入输出格式

输入格式


The first line contains two integers $ n $ and $ m $ ( $ 1<=n<=3·10^{5} $ , $ 1<=m<=3·10^{5} $ ) — the number of vertices and the number of edges in the graph. The next $ m $ lines describe edges in the graph. The $ i $ -th of these lines contains two integers $ a_{i} $ and $ b_{i} $ ( $ 1<=a_{i},b_{i}<=n $ ; $ a_{i}≠b_{i} $ ), denoting an edge between vertices $ a_{i} $ and $ b_{i} $ . It is guaranteed that this graph does not contain edge-simple cycles of even length. The next line contains a single integer $ q $ ( $ 1<=q<=3·10^{5} $ ) — the number of queries. The next $ q $ lines contain queries. The $ i $ -th of these lines contains two integers $ l_{i} $ and $ r_{i} $ ( $ 1<=l_{i}<=r_{i}<=n $ ) — the query parameters.

输出格式


Print $ q $ numbers, each in new line: the $ i $ -th of them should be the number of subsegments $ [x;y] $ ( $ l_{i}<=x<=y<=r_{i} $ ), such that the graph that only includes vertices from segment $ [x;y] $ and edges between them is bipartite.

输入输出样例

输入样例 #1

6 6
1 2
2 3
3 1
4 5
5 6
6 4
3
1 3
4 6
1 6

输出样例 #1

5
5
14

输入样例 #2

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

输出样例 #2

27
8
19

说明

The first example is shown on the picture below: ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF901C/9b1dc17b2719bb085fa0c10624f2d9373bdbe5c5.png) For the first query, all subsegments of $ [1;3] $ , except this segment itself, are suitable. For the first query, all subsegments of $ [4;6] $ , except this segment itself, are suitable. For the third query, all subsegments of $ [1;6] $ are suitable, except $ [1;3] $ , $ [1;4] $ , $ [1;5] $ , $ [1;6] $ , $ [2;6] $ , $ [3;6] $ , $ [4;6] $ . The second example is shown on the picture below: ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF901C/d6699797f2ea521389d1d5d2e2e1a5397ed46123.png)

Input

题意翻译

给你一个有$n$个点的无向图,没有偶环。我们把节点标记为$1..n$。 你需要回答$q$个询问,每一个询问由一个区间`[L,R](1<=L<=R<=n)`组成,你需要计算出有多少个点对`[x,y](L<=x<=y<=R)`,满足由`[x,y]`之间的所有点组成的子图是一个二分图。 输入数据第一行两个整数 $n,m$ ($1\le n\le 3\times 10^5,1\le m\le 3\times10^5$)代表点数和边数 接下来的$m$行,每行两个整数,表示一条无向边,保证无自环,保证无重边 一个整数 $q(1\le q\le3\times 10^5)$,表示询问个数 接下来$q$行,每行一个询问`[L,R]` 对于每个询问,输出一个整数,表示满足条件的点对`[x,y]`的个数

加入题单

上一题 下一题 算法标签: