1420 . 區間三元環個數
TopCoder
Tags
Description
中餅非常熱愛有多筆詢問的問題，這也是為什麼他非常開心能來到 IOICamp 學習資料結構與分塊技巧。
一來到 IOICamp，中餅就滿心期待的翻開講義。可惜的是，迎接他的卻是一題沒有詢問的題目：
給定一張 $N$ 個點 $M$ 條邊的簡單無向圖，數有多少長度為 3 的簡單環。
看不到多筆詢問的中餅非常火大，於是他擅自主張塗改了講義，把題目改為：
給定一張 $N$ 個點 $M$ 條邊的簡單無向圖，邊的編號從 $1$ 到 $M$。接著有 $Q$ 筆詢問，每筆詢問輸入一個區間 $[l_i, r_i]$，請回答：如果只考慮編號介於 $l_i$ 和 $r_i$ 中的邊，有多少長度為 3 的簡單環？
麻煩的是，經過中餅的塗改後，編講義的講者居然不會這一題了！為了避免如此不堪的情形發生，請撰寫一個程式幫助講者解決這個問題。
Input Format
輸入第一行有兩個正整數 $N, M$，代表圖的點數和邊數。
接下來的 $M$ 行中，每一行有兩個正整數 $a_i, b_i$，代表圖中有一條編號為 $i$ 且連接 $a_i$ 和 $b_i$ 的無向邊。
接下來一行有一個正整數 $Q$，代表詢問的數量。
接下來的 $Q$ 行中，每一行有兩個正整數 $l_i, r_i$，意義如題目所述。
- $1 \leq N \leq 3 \times 10 ^ 5$
- $1 \leq M \leq 4 \times 10 ^ 5$
- $1 \leq a_i, b_i \leq N$
- 保證給定的圖為簡單無向圖
- $1 \leq Q \leq 10 ^ 5$
- $1 \leq l_i \leq r_i \leq M$
Output Format
請輸出 $Q$ 行，第 $i$ 行包含一個數字，為第 $i$ 筆詢問的答案。
Sample Input 1
4 6 1 2 2 3 3 1 4 1 2 4 3 4 3 1 6 1 3 2 5
Sample Output 1
4 1 0
Sample Input 2
8 20 7 1 8 6 2 6 1 8 1 6 8 7 5 8 6 3 5 1 8 2 3 4 6 7 5 7 2 7 3 8 5 6 4 6 3 7 5 4 4 7 6 11 19 15 19 1 5 5 7 3 4 8 20
Sample Output 2
2 1 1 0 0 7
Hints
對於三個編號分別為 $a, b, c$ 的點，如果邊 $(a, b)$、邊 $(b, c)$、跟邊 $(a, c)$ 都存在，則這三條邊組成一個長度為 3 的簡單環。
Problem Source
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0~1 | 範例測資。 | 0 |
| 2 | 2~9 | $Q = 1$。 | 29 |
| 3 | 0~19 | 無特別限制。 | 71 |