[CF1187D] Subarray Sorting - 线段树

[CF1187D] Subarray Sorting - 线段树

Description

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

Solution

从左到右扫描每个 \(b_i\)，在 \(a\) 中找到未被使用的最靠左的，如果它左边未被使用的数中没有比它小的，就用它，否则就无解

#include <bits/stdc++.h>
using namespace std;

#define int long long

int n;
const int N = 1e6 + 5;
int a[N], b[N];

struct SegmentTree
{
    vector<int> a;

    SegmentTree(int n)
    {
        a.resize(4 * n + 4);
    }

    void pushup(int p)
    {
        a[p] = min(a[p * 2], a[p * 2 + 1]);
    }

    void build(int p, int l, int r, int *src)
    {
        if (l == r)
            a[p] = src[l];
        else
            build(p * 2, l, (l + r) / 2, src), build(p * 2 + 1, (l + r) / 2 + 1, r, src), pushup(p);
    }

    void modify(int p, int l, int r, int pos, int val)
    {
        if (l == r)
            a[p] = val;
        else
        {
            if (pos <= (l + r) / 2)
                modify(p * 2, l, (l + r) / 2, pos, val);
            else
                modify(p * 2 + 1, (l + r) / 2 + 1, r, pos, val);
            pushup(p);
        }
    }

    int query(int p, int l, int r, int ql, int qr)
    {
        if (l > qr || r < ql)
            return 1e9;
        if (l >= ql && r <= qr)
            return a[p];
        return min(query(p * 2, l, (l + r) / 2, ql, qr), query(p * 2 + 1, (l + r) / 2 + 1, r, ql, qr));
    }
};

void solve()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int i = 1; i <= n; i++)
        cin >> b[i];
    SegmentTree seg(n);
    seg.build(1, 1, n, a);
    vector<vector<int>> occur(n + 2);
    for (int i = n; i >= 1; i--)
        occur[a[i]].push_back(i);
    for (int i = 1; i <= n; i++)
    {
        int x = b[i];
        if (occur[x].size() == 0)
        {
            cout << "NO" << endl;
            return;
        }
        int p = occur[x].back();
        occur[x].pop_back();
        int qu = seg.query(1, 1, n, 1, p);
        if (qu != x)
        {
            cout << "NO" << endl;
            return;
        }
        seg.modify(1, 1, n, p, 1e9);
    }
    cout << "YES" << endl;
}

signed main()
{
    ios::sync_with_stdio(false);

    int t;
    cin >> t;
    while (t--)
        solve();
}

[CF1187D] Subarray Sorting - 线段树

原文：https://www.cnblogs.com/mollnn/p/14654447.html