e182. 框架區間 (加強版) - 高中生程式解題系統

內容

基因是含有特定遺傳信息的結構,用來決定生物的種性特徵。

生物學家發現,與特定功能相關的一群基因在基因序列上的位置通常十分靠近, 因此在基因序列中的連續片段被認為是有意義的。

一個包含 $n$ 個基因的序列可以用 ${1, 2, \dots, n}$ 所組成的排列 $S = (s_{1}, s_{2}, \dots, s_{n})$ 來表示。

為了預測基因序列 $S$ 上可能有意義的片段,一位生物學家遭遇了下列問題。

令 $F (a, b)$ 代表在基因序列 $S$ 上位置落在基因 $a$ 和基因 $b$ 之間的所有整數所構成的集合 (含 $a$ 和 $b$ )。

例如，令 $S = (2, 7, 6, 4, 14, 13, 5, 8, 1, 9, 11, 10, 12, 3)$ ，

則 $F (6, 8) = F (8, 6) = {6, 4, 14, 13, 5, 8}$ 。

令 $I (a, b)$ 代表數線上 $a$ 和 $b$ 這兩個整數間所有整數所構成的集合 (含 $a$ 和 $b$ )。

例如， $I (6, 8) = I (8, 6) = {6, 7, 8}$ 。在基因序列 $S$ 上如果兩個整數 $a$ 和 $b$ ， $1 \leq a < b \leq n$ ，

滿足 $F (a, b) = I (a, b)$ 則稱 $(a, b)$ 構成一個「框架區間」 (framed interval)。

舉例來說, 考慮基因序列 $S = (2, 7, 6, 4, 14, 13, 5, 8, 1, 9, 11, 10, 12, 3)$ ，以 $(a, b) = (9, 12)$ 為例，

因為 $F (9, 12) = {9, 11, 10, 12} = {9, 10, 11, 12} = I (9, 12)$ ，所以 $(9, 12)$ 是一個框架區間。

相同的 $(6, 7)$ 、 $(10, 11)$ 和 $(13, 14)$ 也是框架區間。

這位生物學家想知道給定一個基因序列 $S$ ，有多少數對 $(a, b)$ ， $1 \leq a < b \leq n$ ，是一個框架區間?

例如，在基因序列 $S = (2, 1, 5, 4, 3)$ 上，是框架區間的數對 $(a, b)$ ， $1 \leq a < b \leq 5$ ，

有 $(1, 2)$ 、 $(3, 4)$ 、 $(3, 5)$ 和 $(4, 5)$ ，共四個。

輸入說明

第一行有一整數 $T$ ，代表有 $T$ 組測試資料。

接下來每兩行用來描述一組基因序列，
第一行有一整數 $n$ ，第二行有 $n$ 個整數 $s_{1}, s_{2}, \dots, s_{n}$ (數字之間以一個空白隔開)，

代表基因序列 $S = (s_{1}, s_{2}, \dots, s_{n})$ ，任兩個數字都不相同且 $1 \leq s_{1}, s_{2}, \dots, s_{n} \leq n$ 。

輸出說明

針對所輸入的基因序列 $S$ ，輸出一個數字，代表有多少數對 $(a, b)$ ， $1 \leq a < b \leq n$ ，是一個框架區間?

範例輸入 #1

輸入範例 1:
3
4
3 1 4 2
4
3 2 1 4
5
2 1 5 4 3

輸入範例 2:
2
14
2 7 6 4 14 13 5 8 1 9 11 10 12 3
11
3 10 4 5 6 8 7 9 11 2 1

範例輸出 #1

輸出範例 1:
0
3
4

輸出範例 2:
4
9

測資資訊：

記憶體限制： 512 MB
公開測資點#0 (11%): 1.0s , <1M
公開測資點#1 (11%): 1.0s , <1M
公開測資點#2 (11%): 1.0s , <1M
公開測資點#3 (11%): 1.0s , <10M
公開測資點#4 (11%): 1.0s , <10M
公開測資點#5 (11%): 1.0s , <10M
公開測資點#6 (11%): 3.0s , >50M
公開測資點#7 (11%): 3.0s , >50M
公開測資點#8 (12%): 3.0s , >50M

提示：

原題 c424。請以 scanf 或其他優化方式取代 cin 進行輸入。

測資點 #00 ~ #02： $n \leq 5000, T \leq 10$

測資點 #03 ~ #05： $n \leq 100000, T \leq 10$

測資點 #06 ~ #08： $n \leq 1000000, T \leq 10$

標籤:

出處:

[管理者： icube (!@#$%^&*()_...) ]

編號	身分	題目	主題	人氣	發表日期
沒有發現任何「解題報告」