h873. 排序問題 - 高中生程式解題系統

內容

排序有很多種，像是經典的bubble sort，或是快的merge sort，有的時候會被卡的quick sort，甚至是很神奇的bogo sort，以及很難實現的gravity sort……，總之排序是個有趣的東西，所以現在給你個A陣列以及B陣列，他們長度為N，想要問你一題和排序有關的問題。

你現在可以對A陣列進行任意次的sort操作，你每次的操作可以選擇一個連續區間[L,R]，把此區間裡的數依照大小地從小到大排序，小的放前面大的放後面。

你的目標是判斷A陣列有沒有機會在透過一系列的操作後變得跟B陣列一樣。

範圍限制:

1 ≤ N ≤ 10⁵
1 ≤ Ai, Bi ≤ N

輸入說明

首先第一行有一個數N，代表A、B陣列的長度。
再來兩行各N個數代表陣列內容。

輸出說明

輸出答案yes或no，代表可不可能透過一系列sort操作來把A陣列轉成B。

範例輸入 #1

7
3 2 1 4 3 1 1 
3 1 2 4 1 1 3

範例輸出 #1

yes

範例輸入 #2

4
1 2 4 3
3 4 1 2

範例輸出 #2

no

範例輸入 #3

3
1 2 3
2 3 4

範例輸出 #3

no

測資資訊：

記憶體限制： 256 MB

提示：

範例參考：

#1 您可以先sort區間[2,3]接著sort區間[5,7]

#2 沒有任何方法可以把A變成B

#3 請注意A陣列和B陣列內容可能不一樣

標籤:

sort 線段樹

出處:

Chi's Coding Problem [管理者： Ststone1687 (Ststone) ]

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