CF1187D Subarray Sorting（神奇思路，线段树）

说实话，$2200$ 的题做不出来也有点丢脸了……

当然要先判所有数出现次数相同。

首先区间排序就相当于交换相邻两个数，前面的数要大于后面的数才能交换。

然后就不会了……

我们考虑 $b_1$ 到 $b_{i-1}$ 都已经归位了，现在要把 $b_i$ 归位。

找到其在 $a$ 中下一次出现的位置（设为 $p$）。发现只有当 $a_p$ 是 $a_i$ 到 $a_p$ 的最小值时，才能归到。

具体代码实现时不会改变 $a$ 的位置，那怎么判断最小值呢？发现已经归位的数对最小值没有贡献，可以归位后就变成 INF。然后询问 $1$ 到 $p$ 的最小值即可。

时间复杂度 $O(n\log n)$。

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int maxn=;

#define lson o<<1,l,mid

#define rson o<<1|1,mid+1,r

#define FOR(i,a,b) for(int i=(a);i<=(b);i++)

#define ROF(i,a,b) for(int i=(a);i>=(b);i--)

#define MEM(x,v) memset(x,v,sizeof(x))

inline int read(){

    int x=,f=;char ch=getchar();

    while(ch<'' || ch>'') f|=ch=='-',ch=getchar();

    while(ch>='' && ch<='') x=x*+ch-'',ch=getchar();

    return f?-x:x;

}

int t,n,a[maxn],b[maxn],ta[maxn],tb[maxn],mn[maxn*],len[maxn];

vector<int> at[maxn];

inline void pushup(int o){

    mn[o]=min(mn[o<<],mn[o<<|]);

}

void build(int o,int l,int r){

    if(l==r) return void(mn[o]=a[l]);

    int mid=(l+r)>>;

    build(lson);build(rson);

    pushup(o);

}

void update(int o,int l,int r,int p,int v){

    if(l==r) return void(mn[o]=v);

    int mid=(l+r)>>;

    if(mid>=p) update(lson,p,v);

    else update(rson,p,v);

    pushup(o);

}

int query(int o,int l,int r,int ql,int qr){

    if(l>=ql && r<=qr) return mn[o];

    int mid=(l+r)>>,ans=2e9;

    if(mid>=ql) ans=min(ans,query(lson,ql,qr));

    if(mid<qr) ans=min(ans,query(rson,ql,qr));

    return ans;

}

int main(){

    t=read();

    while(t--){

        bool flag=true;

        n=read();

        FOR(i,,n) ta[i]=a[i]=read(),at[a[i]].push_back(i);

        FOR(i,,n) tb[i]=b[i]=read();

        sort(ta+,ta+n+);sort(tb+,tb+n+);

        FOR(i,,n) if(ta[i]!=tb[i]){puts("NO");flag=false;break;}

        if(!flag){

            FOR(i,,n) at[i].clear(),len[i]=;

            continue;

        }

        build(,,n);

        FOR(i,,n){

            int p=at[b[i]][len[b[i]]++];

            if(query(,,n,,p)!=b[i]){puts("NO");flag=false;break;}

            update(,,n,p,2e9);

        }

        if(flag) puts("YES");

        FOR(i,,n) at[i].clear(),len[i]=;

    }

}

巴特西

CF1187D Subarray Sorting（神奇思路，线段树）

最新文章

热门文章