CF1187D题解

· · 题解

更新

2024/8/19 删去了不严谨的异或判重,感谢 @Ether13 大佬的提醒详见此帖

题目大意：

给定长为 n 的序列 a，b。可以进行操作选择 a 的一个区间并将其升序排序，问若干次操作后能否将 a 变为 b。

感性理解：

首先序列 a 与 b 进行排序后一定要相等（可重集相同）。

其次排序的过程，考虑冒泡排序，对每个无序的长度为 2 的区间进行排序，相当于交换相邻的两个逆序对。

从前往后考虑依次将 a 的每一位变成 b，若 a 的第 i 位与 b 的第 j 位相对应，就把它移到位置 j。

此时我们考虑排序过程是相邻逆序对交换，若出现在 a 的第 j 位到第 i 位中有比 a 的第 i 位小的数，那么就无法交换至第 j 位，那么就无法完成排序。

简化为 3 步：

  1. 判重（异或判重，也可用随机值判重）
  2. 找 j 到 i 中的最小值
  3. 标记已排好序的数

暴力 70pts 代码：

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int t,n,ah,bh;
int a[N],b[N],vis[N];
bool pan(){
    if(ah!=bh)  return 0;//异或判重(不严谨,建议不要使用)
    int ma=n;
    for(int i=1;i<=n;i++){
        int cnt=1;
        for(int j=1;j<=n;j++){//暴力搜索最小值
            if(vis[j])  continue;
            if(a[j]==b[i]&&cnt){
                vis[j]=1;//标记排好序的数
                break;
            } 
            if(a[j]<b[i])  return 0;
        }
    }
    return 1;
}
int main(){
    scanf("%d",&t);
    while(t--){
        ah=bh=0;
        scanf("%d",&n);
        for(int i=1;i<=n;i++)  vis[i]=0;
        for(int i=1;i<=n;i++){
            scanf("%d",&a[i]);
            ah^=a[i];
        }
        for(int i=1;i<=n;i++){
            scanf("%d",&b[i]);
            bh^=b[i];
        }
        if(pan())  printf("YES\n");
        else  printf("NO\n");
    }
}

优化

我们考虑打标记对取最小值的影响，可以将已排好序的数赋值为 \inf，这样在取最小值时肯定不会受影响。

现在问题简化成单点修改，前缀查询最小值，我们发现一个事情——这很线段树。

用线段树进行优化。

AC 代码


#include<bits/stdc++.h>
using namespace std;
const int N=3e5+5,inf=1e9+5;
int q,n,ha,hb,suma,sumb;
int a[N],b[N],v[N],t[4*N],c[N],tota[N],totb[N];
map<int,map<int,int> >s;
void build(int k,int l,int r){
    if(l==r){
        t[k]=a[l];
        return;
    }
    int mid=(l+r)>>1;
    build(2*k,l,mid);
    build(2*k+1,mid+1,r);
    t[k]=min(t[2*k],t[2*k+1]);
    return;
}
void dotchange(int k,int l,int r,int x){
    if(l==r&&l==x){
        t[k]=inf;
        return;
    }
    int mid=(l+r)>>1;
    if(x<=mid)  dotchange(2*k,l,mid,x);
    if(x>mid)  dotchange(2*k+1,mid+1,r,x);
    t[k]=min(t[2*k],t[2*k+1]);
}
int longquery(int k,int l,int r,int x,int y){
    if(x<=l&&r<=y){
        return t[k];
    }
    int res=inf;
    int mid=(l+r)>>1;
    if(x<=mid)  res=min(longquery(2*k,l,mid,x,y),res);
    if(y>mid)  res=min(longquery(2*k+1,mid+1,r,x,y),res);
    return res;
}
bool pan(){
    for(int i=1;i<=n;i++)  if(tota[i])  return 0;
//  if(ha!=hb||suma!=sumb)  return 0;再次强调,异或判重和前缀和判重都不严谨
    for(int i=1;i<=4*n+1;i++)  t[i]=inf;//注意多测
    build(1,1,n);
    for(int i=1;i<=n;i++){
        ++v[b[i]];
        int z=longquery(1,1,n,1,max(s[b[i]][v[b[i]]]-1,1));//前缀查询最小值
        if(z<b[i])  return 0;
        dotchange(1,1,n,max(s[b[i]][v[b[i]]],1));//单点修改 inf

    }
    return 1;
}
int main(){
    scanf("%d",&q);
    while(q--){
//      ha=0,hb=0,suma=0,sumb=0;
        scanf("%d",&n);
        for(int i=1;i<=n;i++)  v[i]=0,c[i]=0,tota[i]=0;
        s.clear();
        for(int i=1;i<=n;i++){
            scanf("%d",&a[i]);
            s[a[i]][++c[a[i]]]=i;//依次记录每个 a[i] 出现的位置
//          ha^=a[i];
//          suma+=a[i];
            tota[a[i]]++;
        }
        for(int i=1;i<=n;i++){
            scanf("%d",&b[i]);
//          hb^=b[i];
//          sumb+=b[i];
            tota[b[i]]--;
        }
        if(pan())  printf("YES\n");
        else  printf("NO\n");
    }
}