306381: CF1187D. Subarray Sorting

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Subarray Sorting

题意翻译

给定长度为 $n$ 的数组 $a$ 和 $b$。你每次可以选择一段区间 $[l,r]$,令 $a_l\sim a_r$ 的元素从小到大排序。你可以进行任意次操作。问能否使 $a$ 与 $b$ 完全相等(对应位置上的元素相等)。

题目描述

You are given an array $ a_1, a_2, \dots, a_n $ and an array $ b_1, b_2, \dots, b_n $ . For one operation you can sort in non-decreasing order any subarray $ a[l \dots r] $ of the array $ a $ . For example, if $ a = [4, 2, 2, 1, 3, 1] $ and you choose subbarray $ a[2 \dots 5] $ , then the array turns into $ [4, 1, 2, 2, 3, 1] $ . You are asked to determine whether it is possible to obtain the array $ b $ by applying this operation any number of times (possibly zero) to the array $ a $ .

输入输出格式

输入格式


The first line contains one integer $ t $ ( $ 1 \le t \le 3 \cdot 10^5 $ ) — the number of queries. The first line of each query contains one integer $ n $ ( $ 1 \le n \le 3 \cdot 10^5 $ ). The second line of each query contains $ n $ integers $ a_1, a_2, \dots, a_n $ ( $ 1 \le a_i \le n $ ). The third line of each query contains $ n $ integers $ b_1, b_2, \dots, b_n $ ( $ 1 \le b_i \le n $ ). It is guaranteed that $ \sum n \le 3 \cdot 10^5 $ over all queries in a test.

输出格式


For each query print YES (in any letter case) if it is possible to obtain an array $ b $ and NO (in any letter case) otherwise.

输入输出样例

输入样例 #1

4
7
1 7 1 4 4 5 6
1 1 4 4 5 7 6
5
1 1 3 3 5
1 1 3 3 5
2
1 1
1 2
3
1 2 3
3 2 1

输出样例 #1

YES
YES
NO
NO

说明

In first test case the can sort subarray $ a_1 \dots a_5 $ , then $ a $ will turn into $ [1, 1, 4, 4, 7, 5, 6] $ , and then sort subarray $ a_5 \dots a_6 $ .

Input

题意翻译

给定长度为 $n$ 的数组 $a$ 和 $b$。你每次可以选择一段区间 $[l,r]$,令 $a_l\sim a_r$ 的元素从小到大排序。你可以进行任意次操作。问能否使 $a$ 与 $b$ 完全相等(对应位置上的元素相等)。

加入题单

上一题 下一题 算法标签: