CodeForces 1187D Subarray Sorting

Problem

You are given an array \(a_1\),\(a_2\),…,\(a_n\) and an array \(b_1\),\(b_2\),…,\(b_n\).

For one operation you can sort in non-decreasing order any subarray \(a[l…r]\) of the array \(a\).

For example, if \(a=[4,2,2,1,3,1]\) and you choose subbarray \(a[2…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\).

Input

The first line contains one integer \(t (1≤t≤3⋅10^5)\) — the number of queries.

The first line of each query contains one integer \(n (1≤n≤3⋅105)\).

The second line of each query contains \(n\) integers \(a_1,a_2,…,a_n (1≤a_i≤n)\).

The third line of each query contains n integers \(b_1,b_2,…,b_n (1≤b_i≤n)\).

It is guaranteed that \(\sum{n}≤3⋅10^5\) over all queries in a test.

Output

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.

Example

Input

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

Output

YES

YES

NO

NO

Note

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

感想

这题也过分，一定要发朋友圈博客。

OI带到这里的“坏”习惯——及时break。ACM里遍地都是多组数据，判断出一组答案，及时break之后，这一组还没读完读数据就被下一组读了，自然WA了。

这题调了一上午的原因就在于此——经验不足，以至于完全看不出我的代码及时break的问题。

另外，这是我的第一篇用markdown写的博客，markdown真好用。

解题思路

支持的操作是对子区间升序排序，这意味着，我们可以把一个区间内的最大值移动到该区间最右端，也可以把一个区间内的最小值移动到该区间最左端。

由于b是从左到右输入，对于每一个b，a也要将合适的数字左移，所以我们移动区间最小值到最左端。其实想一想不一定总是要到最左端，一个区间内的最小值可以左移到任意位置，还不会影响其他数字的顺序(每次排序最小值和最小值左边的第一个数，总共两个数)。

首先读入a数组，经过一堆后面会说的预处理(为了快速找到下文说的pos[b])，然后依次读入b。

对于每一个读入的b(假设是第i个)，寻找这个数字b在a中最早出现的位置（pos[b]）。

如果找到的位置为无穷，换句话说a里没有这个数，那么答案就是NO，就可以break了就可以把flag标记设置成false，然后读完剩下数据，输出NO。
如果找到了一个位置，那么我们的目标就是把这个b向前移动到位置i，由之前的思考可得，b需要是是a数组里下标i到pos[b]之间的最小值。
再进一步，能读入第i个b，说明前面i-1个位置已经匹配完成了，或前面或后面，已经有i-1个数被设置成了INF，一定大于b，不会影响我们。
考虑1到pos[b]这个区间，假设里面的情况这样 █ █ █ █ ▂ █ █b， █ 形象地代表大于等于b的数字，它们不会干扰我们左移b。 ▂ 形象地代表小于b的数字，当然还没被使用(使用了就被设置成INF了)，它会阻挡b左移，换句话说，b只能向左移动到 ▂ 的右边那段(或者不移动)。
- 如果现在i在 ▂ 左边，或者说i到pos[b]的最小值小于b，那答案也就是NO了。
- 如果现在i在 ▂ 右边，或者说i到pos[b]的最小值就是b，那么这次移动就可以完成。可是，完成这次以后，我们会发现， ▂ 还是在左边，没有被使用。由于a和b是同样长的，a、b含有不同数字的情况我们之前也排除了，所以在以后的时光里(雾)， ▂ 一定会被用到， ▂ 就需要被右移（把 ▂ 右边的左移），但是， ▂ 的右边至少有个b挡着啊，b比 ▂ 大， ▂ 不可能右移到目标位置的。
综上，1到pos[b]的区间内，如果最小值小于b，那答案无论如何都是NO。
类似的，我们也可以证明（其实是太晚了，想睡觉了），如果1到pos[b]内的最小值总是等于b，那么目标可以达成，答案是YES

然后完善一些小地方，区间最小值连上更新，就用线段树，挺方便。快速找pos[b]，思路类似莫队里经常出现的pos数组和nxt数组(SDOI2009 HH的项链)。另外，memset不要每组数组都全部清零，第18个测试点很变态（见代码59行）。

源代码

#include <stdio.h>

#include <string.h>

#include <algorithm>

int T;

int n;

int a[300010], nxt[300010], pos[300010];

struct Segtree

{

    int l, r;

    int min;

} s[1200010];

inline int lson(int x) { return x << 1; }

inline int rson(int x) { return x << 1 | 1; }

inline void pushup(int x) { s[x].min = std::min(s[lson(x)].min, s[rson(x)].min); }

void build(int x, int l, int r)

{

    s[x] = {l, r, 0};

    if (l == r)

    {

        s[x].min = a[l];

        return;

    }

    int mid = l + r >> 1;

    build(lson(x), l, mid);

    build(rson(x), mid + 1, r);

    pushup(x);

}

void update(int x, int position)

{

    if (position > s[x].r || position < s[x].l)

        return;

    if (s[x].l == s[x].r && s[x].l == position)

    {

        s[x].min = 0x7fffffff;

        return;

    }

    update(lson(x), position);

    update(rson(x), position);

    pushup(x);

}

int que(int x, int l, int r)

{

    if (r < s[x].l || l > s[x].r)

        return 0x7fffffff;

    if (l <= s[x].l && s[x].r <= r)

        return s[x].min;

    return std::min(que(lson(x), l, r), que(rson(x), l, r));

}

int main()

{

    //freopen("test.in","r",stdin);

    scanf("%d", &T);

    while (T--)

    {

        scanf("%d", &n);

        for (int i = 1; i <= n; i++)

            scanf("%d", a + i);

        memset(nxt, 0x7f, sizeof(int)*(n+2));//第18个测试点十分丧病，T是几十万，每组n是1

        memset(pos, 0x7f, sizeof(int)*(n+2));

        for (int i = n; i >= 1; i--)

        {

            nxt[i] = pos[a[i]];

            pos[a[i]] = i;

        }

        build(1, 1, n);

        bool ok = 1;

        for (int i = 1, b; i <= n; i++)

        {

            scanf("%d", &b);

            if(!ok) continue;//不要break，数据要读完

            if (pos[b] == 0x7f7f7f7f)

                ok = 0;

            if (que(1, 1, pos[b]) == b)

            {

                update(1, pos[b]);

                pos[b] = nxt[b];

            }

            else

                ok = 0;

        }

        puts(ok ? "YES" : "NO");

    }

    return 0;

}

巴特西

CodeForces 1187D Subarray Sorting

Problem

Input

Output

Example

Input

Output

Note

感想

解题思路

源代码

最新文章

热门文章