U232148 [sxyz NOIP 模拟赛] 4 排列（perm）

[sxyz NOIP 模拟赛]4 排列（perm）T4 ------------ 3s 512MB

给定两个长度为 n 的排列 p, q，两个排列下标及元素均在 1 − n 之间 你会依次将排列中下标为 q1, q2, ..., qn−1 的位置依次打上标记，在每次打上标记后，你都会重新求出排列 p 的特征值。 其中一个排列的特征值为：按照从小到大的顺序扫描排列的每个元素，同时维护一个初始情况下为空的集合，每次将当前的元素插入到集合中，如果插入的元素有标记，则将集合中最大的元素弹出。如果至少存在一个位置没有被标记，则最后集合一定非空。最终集合的最大值就是这个序列的特征值。 你需要求出，对于所有 0 ≤ i < n，将 q1, q2, ..., qi 打上标记后这个排列的特征值是多少。

第一行一个整数 n 第二行 n 个整数 pi 第三行 n 个整数 qi

一行 n 个整数，第 i + 1 个整数表示将 q1, q2, ..., qi 打上标记后这个排列的特征值

4.4 数据范围与提示 对于 30% 的数据，n ≤ 1000 对于 50% 的数据，n ≤ 10000 对于另 20% 的数据，qi = n − i + 1 对于所有数据，n ≤ 300000 ------------ [原题链接](https://www.luogu.com.cn/problem/CF1326E)。