Codeforces 1187D - Subarray Sorting 题解

题解 #

我们可以做的最小的操作就是只排序相邻的两个元素，也就是说交换 $a_i$ 和 $a_{i+1}$ 如果 $a_i>a_{i+1}$ 。通过这种操作，我们可以把 $a_i$ 挪到位置 $j,j< i$ ，如果所有 $i$ 到 $j-1$ 的数都比 $a_i$ 小的话。

明白了操作的本质之后我们就可以尝试从用 a 数组的数左往右构造 b 数组了。设当前的位置为 $i$ :

首先找到最左的位置 $j$ 使得 $a_j=b_i$ ，如果找不到那么答案是 no。我们可以用 set 或者很多个 vector 维护位置。
判断 $[1,j)$ （最初的下标）中的最小值是否比 $a_j$ 小，我们可以用线段树实现这一操作。
将 $a_j$ 设为无穷大。

Code #

#include <bits/stdc++.h>
 
#define forn(i, n) for (int i = 0; i < int(n); ++i)
#define for1(i, n) for (int i = 1; i <= int(n); ++i)
#define ms(a, x) memset(a, x, sizeof(a))
#define F first
#define S second
#define all(x) (x).begin(),(x).end()
 
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int INF = 0x3f3f3f3f;
mt19937 gen(random_device{}());
template<typename... Args> void write(Args... args) { ((cout << args << " "), ...); cout<<endl;}
 
struct SegTree{
    int n;
    vector<int> t;
    SegTree(int n_):n(n_){
        t=vector<int>(2*n);
    }
    SegTree(vector<int> a){
        n=a.size();
        t=vector<int>(2*n);
        for (int i=0;i<n;i++) t[n+i]=a[i];
        for (int i = n - 1; i > 0; --i) t[i] = min(t[i<<1], t[i<<1|1]);
    }
 
    void update(int p, int value) {  // set value at position p
        t[p += n] = value;
        for (; p > 1; p >>= 1) t[p>>1] =min(t[p], t[p^1]);
    }
 
    int query(int l, int r) {  // sum on interval [l, r)
        int res = 1e9;
        for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
            if (l&1) res =min(res, t[l++]);
            if (r&1) res =min(res, t[--r]);
        }
        return res;
    }
};
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int tt;
    cin>>tt;
    while(tt--){
        int n;
        cin>>n;
        vector<int> a(n),b(n);
        set<pii> s;
        forn(i,n){
            cin>>a[i];
            s.insert({a[i],i});
        }
        for(auto& it:b) cin>>it;
        SegTree tr(a);
        forn(i,n){
            auto it=s.lower_bound({b[i],0});
            if(it==s.end()||it->F!=b[i]||tr.query(0,it->S+1)<b[i]){
                cout<<"NO\n";
                goto next;
            }
            tr.update(it->S,1e9);
            s.erase(it);
        }
        cout<<"YES\n";
next:;
    }
    return 0;
}