f999: SCP - A 特訓班
Tags : DSU 分治 線段樹
Accepted rate : 2人/2人 ( 100% ) [非即時]
評分方式:
Tolerant

最近更新 : 2022-05-11 16:54

Content

這個世界上有很多異常的物體,統稱 $\text{SCP}$ (原因是有一個會收容異常的基金會叫 $\text{SCP}$ 基金會),但是想要成為一個 $\text{SCP}$ 沒有這麼容易,需要好好學習一個異常需要會的知識和技能,最後還要在 $\text{SCP}$ 大學考試考到 $\text{A}$ 級的成績才能錄取。

考到 $\text{SCP}$ 大學是每個青少年異常的夢想,只是有些異常不知該如何學習異常知識,這時就有業者來開班了,「$\text{SCP - A}$ 特訓班,讓你在眾多異常裡脫穎而出,保證考 $\text{A}$ 級,現在報名即可享 $888$ 折優惠!」

不只這樣,還有附歷屆學員的心得:「自從報名了這個班,別人看到我都會嚇得眼睛都不敢眨呢!」學號為 $173$ 的學員說道,「上了這個班以後,我連強酸都不怕了!」學號為 $682$ 的學員說道。

$\text{Hehe}$ 怪在看到 $\text{SCP - A}$ 特訓班後,就跑去報名了。第一堂課的老師是 【▅﹌€$﹌,他自稱在業界多年,懂很多大家不知道的知識。首先,他給大家講解了一個異常例題:在第一天有 $a$ 個異常,在第二天有 $b$ 個異常,之後每一天的異常數量會是前兩天異常數量的加總,那在第 $k$ 天有幾個異常呢 ($k ≤ 10 ^{18}$)?有同學說可以矩陣快速冪,老師說其實只要存 $k≤12$ 的答案就好了,因為在他的經驗中,$k$ 根本不會到 $10^{18}$ 那麼大。$\text{Hehe}$ 怪覺得很崇拜,老師竟然懂這麼多東西,結果這時有同學說:「老師我在 $\text{SCP}$ 列表裡沒有看到你,你是不是根本沒通過 $\text{SCP}$ 考試!」老師回答:「我的經驗比你豐富多了,我才不屑教你這種 $\frac{1}{2}$ 瓶 $H_{2\ }O$ 的 Macaca cyclopis!你們一小時只要付我 $\frac{sin(1.56979633)}{cos(1.56979633)}$ 元,雖然我不是數學家,但這聽起來還不錯對吧!」

之後老師講解到了一個例題,有一個 $1\sim n$ 的排列 $a_1\sim a_n$,一個 $1\sim n$ 的環狀排列 $c_1\sim c_n$ ($1\sim n$ 的排列的定義是將 $1\sim n$ 的元素經過任意次交換得到的序列,環狀則是將其頭尾相連,可參考圖片),$a$ 和 $c$ 在相同的數字間有感應器,比方說如果 $a_i = c_j = x$,那在按下 $a_i$ 後,$c_j$ 就會亮起來。我們定義一個連續亮燈序列為:在環狀排列 $c$ 上,任何一個亮起來的元素都可以通過若干個亮起來的元素,到達任意一個亮起來的元素。

以下為 $n=6$,$c_1\sim c_n = \{2,5,6,3,1,4\}$ 的序列,圖一、二、三為連續亮燈序列,圖四卻不是 (黃色的格子為有亮燈的格子):

題目要問的是有多少組 $(l,r)$ 數對 ($1≤l≤r≤n$),在把 $a_l\sim a_r$ 都按下去後,在 $c$ 上會形成一個連續亮燈序列。

這題的 $n≤10^5$,老師說可以枚舉 $l,r$,再看看形成的序列合不合法,$O(n^3)$ 搞定。有同學跟老師說這樣太慢了,老師說他自己測範例測資一下子就算出答案了,要大家不准質疑他。

現在是輪到 $\text{Hehe}$ 怪的實作時間,請異常聰明你幫他邁向 $\text{A}$ 級之路吧!如果能把 $O(n^3)$ 變得更小,那他會很感謝你的!

Input

第一行有一個正整數 $n$,代表 $a$ 與 $c$ 的長度。

第二行輸入一個 $1\sim n$ 的排列 $a_1\sim a_n$。

第三行輸入一個 $1\sim n$ 的環狀排列 $c_1\sim c_n$。

  • $1≤n≤10^5$
  • $1≤a_i, c_i≤n$,且每個 $a_i, c_i$ 所代表的數字在 $a, c$ 裡只會出現一次。
Output

輸出一個整數,代表有多少組數對 $(l,r)$ ($1≤l≤r≤n$),滿足將 $a_l\sim a_r$ 按下去後,在 $c$ 會形成連續亮燈序列。

Sample Input #1
4
1 2 3 4
1 2 3 4
Sample Output #1
10
Sample Input #2
4
3 1 4 2
2 4 3 1
Sample Output #2
9
Sample Input #3
20
19 10 9 17 4 13 18 14 7 2 3 11 1 8 6 12 15 20 16 5
12 7 10 18 16 9 2 15 17 20 14 6 4 13 11 19 8 3 5 1
Sample Output #3
24
測資資訊:
記憶體限制: 64 MB
不公開 測資點#0 (4%): 2.0s , <1K
不公開 測資點#1 (4%): 2.0s , <1K
不公開 測資點#2 (4%): 2.0s , <1K
不公開 測資點#3 (4%): 2.0s , <1K
不公開 測資點#4 (4%): 2.0s , <1K
不公開 測資點#5 (5%): 2.0s , <1M
不公開 測資點#6 (5%): 2.0s , <1M
不公開 測資點#7 (5%): 2.0s , <1M
不公開 測資點#8 (5%): 2.0s , <1M
不公開 測資點#9 (5%): 2.0s , <1M
不公開 測資點#10 (5%): 2.0s , <1M
不公開 測資點#11 (5%): 2.0s , <1M
不公開 測資點#12 (5%): 2.0s , <10M
不公開 測資點#13 (5%): 2.0s , <10M
不公開 測資點#14 (5%): 2.0s , <10M
不公開 測資點#15 (6%): 2.0s , <10M
不公開 測資點#16 (6%): 2.0s , <10M
不公開 測資點#17 (6%): 2.0s , <10M
不公開 測資點#18 (6%): 2.0s , <1M
不公開 測資點#19 (6%): 2.0s , <10M
Hint :

在範例一,任何一個 $(l,r)$ 都可以使 $c$ 成為連續亮燈序列,如下:

在範例二,如果 $(l,r) = (2,3)$,那就會不滿足任何一個亮起來的元素都可以通過若干個亮起來的元素,到達任意一個亮起來的元素,但如果 $(l,r) = (2,4)$,就會滿足:

--------------------------------------------------------------------------------------------------------------------------------

$\color{black}{25\%:n≤200}\ $

$\color{black}{25\%:n≤3000}\ $

$\color{black}{50\%:無特別限制}\ $

Tags:
DSU 分治 線段樹
出處:
Caido [管理者:
becaido (Caido)
]


ID User Problem Subject Hit Post Date
30262
r1cky (木叢欉木叢)
f999
29 2022-05-13 20:35