h873: 排序問題
Tags : sort 線段樹
Accepted rate : 6人/7人 ( 86% ) [非即時]
評分方式:
Tolerant

最近更新 : 2022-04-15 10:42

Content

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

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

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

範圍限制:

1 ≤ N ≤ 105
1 ≤
Ai, Bi ≤ N

Input

首先第一行有一個數N,代表AB陣列的長度。
再來兩行各N個數代表陣列內容。

Output

輸出答案yesno,代表可不可能透過一系列sort操作來把A陣列轉成B

Sample Input #1
7
3 2 1 4 3 1 1 
3 1 2 4 1 1 3
Sample Output #1
yes
Sample Input #2
4
1 2 4 3
3 4 1 2
Sample Output #2
no
Sample Input #3
3
1 2 3
2 3 4
Sample Output #3
no
測資資訊:
記憶體限制: 256 MB
不公開 測資點#0 (10%): 1.0s , <1K
不公開 測資點#1 (10%): 1.0s , <1K
不公開 測資點#2 (10%): 1.0s , <1K
不公開 測資點#3 (10%): 1.0s , <10M
不公開 測資點#4 (10%): 1.0s , <1M
不公開 測資點#5 (10%): 1.0s , <1M
不公開 測資點#6 (10%): 1.0s , <1M
不公開 測資點#7 (10%): 1.0s , <10M
不公開 測資點#8 (10%): 1.0s , <10M
不公開 測資點#9 (10%): 1.0s , <10M
Hint :

範例參考:

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

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

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

Tags:
sort 線段樹
出處:
Chi's Coding Problem [管理者:
Ststone1687 (使用C++的都邪教)
]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」