Subarray Sorting （线段树）

题意：给你两个长度为 n 的序列 a 和 b ，可以对 a 进行操作：选择一段区间[ l, r ] ，使得序列a 在这段区间里按升序排序。可以对a 进行任意多次操作，问 a是否有可能变成b序列。

解：首先，枚举b序列，然后在a中，找这个元素在a出现的位置（如果是第一次出现的，就找第一次出现的那个位置，第二次出现就找第二次出现的） pos ，然后查询 0 ~ pos 的最小值（线段树），若最小值是 b对应的那个元素，就满足，否则，就不满足。然后若满足，需要更新线段树，把查询的元素更新为INF，不然会影响后面查询。

/// 试公式的 勿cheat

#include <iostream>

#include <cstdio>

#include <fstream>

#include <algorithm>

#include <cmath>

#include <deque>

#include <vector>

#include <queue>

#include <string>

#include <cstring>

#include <map>

#include <stack>

#include <set>

#define LL long long

#define ULL unsigned long long

#define re register

#define rep(i,j,k) for(re int i=j;i<=k;i++)

#define dep(i,j,k) for(re int i=k;i>=j;i--)

#define INF 0x3f3f3f3f

#define mem(i,j) memset(i,j,sizeof(i))

#define make(i,j) make_pair(i,j)

#define pb push_back

using namespace std;

const int N = 3e5 + ;

vector<int>G[N];

int a[N], b, du[N]; ///du 代表这个元素出现的 第几次

int rr[N << ];

void pushdown(int root) {

    rr[root] = min(rr[root<<], rr[root<<|]);

    return ;

}

void built(int l, int r, int root) {

    if(l == r) {

        rr[root] = a[l]; return ;

    }

    int mid = (l + r) >> ;

    built(l, mid, root << );

    built(mid + , r, root <<  | );

    pushdown(root);

}

void updat(int l, int r, int x, int val, int root) {

    if(l == r) {

        rr[root] = val; return ;

    }

    int mid = (l + r) >> ;

    if(x <= mid) updat(l, mid, x, val, root << );

    else updat(mid + , r, x, val, root <<  | );

    pushdown(root);

}

int query(int l, int r, int x, int y,int root) {

    if(x <= l && r <= y) return rr[root];

    int mid = (l + r) >> ;

    int ans = INF;

    if(x <= mid) ans = min(ans, query(l, mid, x, y, root << ));

    if(y > mid) ans = min(ans, query(mid + , r, x, y, root <<  | ));

    return ans ;

}

int main() {

    int t, n;

    scanf("%d", &t);

    while(t--) {

        scanf("%d", &n);

        rep(i, , n) G[i].clear(), du[i] = ;

        rep(i, , n) { scanf("%d", &a[i]); G[a[i]].pb(i); }

        built(, n, );

        //cout << query(1, n, 2, 4, 1) << endl;

        int flag = ;

        rep(i, , n) {

            scanf("%d", &b);

            //if(flag) { cout << i - 1 << endl; continue; }

            if(du[b] == (int)G[b].size()) { flag = ; continue; } ///b中这个元素的个数比a中的多，那肯定不满足啦，元素都不完全一样。

            int pos = G[b][du[b]];

            if(pos == ) flag = ;

            //if(pos <= i) continue;

            int p = query(, n, , pos, );

            if(p != b) flag = ;

            updat(, n, G[b][du[b]++], INF, );

        }

        if(flag) puts("NO");

        else puts("YES");

    }

    return ;

}

巴特西

Subarray Sorting （线段树）

最新文章

热门文章