AlgoMooc
← 返回题库

P5102. 火车迷

简单通过率 74% · 提交 34 · 通过 25
模拟贪心

小慕最近迷上了火车调度。他在观察家附近的一个火车站时,发现火车驶入和驶出的顺序并不总是一致的。 经过小慕调查,原来这个火车站里有一个类似于的结构,如下图所示: 例如,可能1号火车先驶入了火车站中的休息区s,在它驶出之前,2号火车又驶入了。 在这种情况下,1号火车必须等待2号火车先倒车出去后才能离开(因为被后面驶入的2号火车挡住了,而这个休息区s只有一个出入口)。 出于好奇,小慕统计了近些天的火车驶入驶出情况,开始统计和结束统计时,休息区s中都是空的。 由于中途疏忽,小慕觉得自己可能弄错了几个驶入驶出的顺序,想请你帮他验证一下。 值得注意的是,小慕虽然可能弄错了顺序,但对火车的记录是的。 形式化地描述休息区s,我们将其视为一个容量无限大的空间。假设两列火车 i 和 j 同时处于休息区s中,驶入时刻Tin满足Tin(i) Tout(j),即先进后出。

提示:带虚线的词点一下有通俗解释。

输入描述

第一行输入一个整数T表示数据组数。 对每组测试而言: 第一行输入一个整数n,表示观察到的火车数量。 第二行输入n个整数x1,x2,...,xn,表示小美记录的火车驶入休息区s的顺序。 第三行输入n个整数y1,y2,...,yn,表示小美记录的火车驶出休息区s的顺序。 1 ≤ T ≤ 10,1 ≤ n ≤ 50000,1 ≤ xi, yi ≤n, 且{xn} 、{yn} 均为{1,2,3,...,n}的一个排列,即1~n这n个数在其中不重不漏恰好出现一次。

输出描述

对每组数据输出一行:如果小美记录的驶入和驶出顺序无法被满足则输出No,否则输出Yes。

示例

示例 1

输入

3
3
1 2 3
1 2 3
3
1 2 3
3 2 1
3
1 2 3
3 1 2

输出

Yes
Yes
No

时间限制 1000 ms · 内存限制 128 MB

看不懂题目?点开图解(训练营专属)

登录后查看题目图解

题目图解为训练营学员专属内容,请先登录。

微信扫码登录还不是训练营学员?了解训练营 →
写完代码点「提交」,将对全部测试用例判题。