Subarray Sorting （线段树）

缺乏、安全感 2021-11-16 09:20 203阅读 0赞

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

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

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

/// 试公式的 勿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 + 5;
    vector<int>G[N];
    int a[N], b, du[N]; ///du 代表这个元素出现的 第几次
    int rr[N << 2];
    void pushdown(int root) {
        rr[root] = min(rr[root<<1], rr[root<<1|1]);
        return ;
    }
    void built(int l, int r, int root) {
        if(l == r) {
            rr[root] = a[l]; return ;
        }
        int mid = (l + r) >> 1;
        built(l, mid, root << 1);
        built(mid + 1, r, root << 1 | 1);
        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) >> 1;
        if(x <= mid) updat(l, mid, x, val, root << 1);
        else updat(mid + 1, r, x, val, root << 1 | 1);
        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) >> 1;
        int ans = INF;
        if(x <= mid) ans = min(ans, query(l, mid, x, y, root << 1));
        if(y > mid) ans = min(ans, query(mid + 1, r, x, y, root << 1 | 1));
        return ans ;
    }
    int main() {
        int t, n;
        scanf("%d", &t);
        while(t--) {
            scanf("%d", &n);
            rep(i, 1, n) G[i].clear(), du[i] = 0; 
            rep(i, 1, n) { scanf("%d", &a[i]); G[a[i]].pb(i); }
            built(1, n, 1);
            //cout << query(1, n, 2, 4, 1) << endl;
            int flag = 0;
            rep(i, 1, n) {
                scanf("%d", &b);
                //if(flag) { cout << i - 1 << endl; continue; }
                if(du[b] == (int)G[b].size()) { flag = 1; continue; } ///b中这个元素的个数比a中的多，那肯定不满足啦，元素都不完全一样。
                int pos = G[b][du[b]];
                if(pos == 0) flag = 1;
                //if(pos <= i) continue;
                int p = query(1, n, 1, pos, 1);
                if(p != b) flag = 1;
                updat(1, n, G[b][du[b]++], INF, 1);
            }
            if(flag) puts("NO");
            else puts("YES");
        }
        return 0;
    }

转载于:https://www.cnblogs.com/Willems/p/11157852.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211116/b3225d44f18c4190a257748e87df34b3.png