题解：CF2031D Penchick and Desert Rabbit

D

赛时的清奇想法。

首先发现能跳跃的两个位置是逆序对，因此考虑用并查集维护，并记录集合内最大值与最小值。

再考虑这样一种做法，先遍历一遍数组，目前遇到的最大值为

x

，下标为

id

，加入一个数

a_i

。

若 $a_i>=x$ 更新 $x$ 和 $id$ 。
若 $a_i<x$ 那么就合并 $i$ 和 $id$ 。

以最后一组样例为例：

用

mx_i

表示集合

i

中最大的

a_i

，

mi_i

表示最小值。

然后考虑合并不同集合，从后往前，如果出现两个不同集合

i,j

且

i<j

。由前面的过程易知

mx_i \le mx_j

，如果

mx_i>mi_j

，就说明这两个集合可以合并。
那有没有可能出现不是相邻的集合合并呢？答案是否定的，考虑

k,i,j

三个集合，

mx_k \le mx_i \le mx_j

，如果

i

与

j

不能合并，则

mx_i \le mi_j

，就会有

mx_k \le mx_i \le mi_j

，显然

k

与

j

不能合并。因此每个集合都只能和相邻的集合合并。

CPP

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
#include <queue>
#include <map>

using namespace std;
typedef long long ll;
const int N=5e5+5;
int n;
int a[N],ans[N];
int fa[N],mi[N],mx[N];
int find(int x)
{
    if(x==fa[x]) return x;
    return fa[x]=find(fa[x]);
}
void merge(int x,int y)
{
    x=fa[x],y=fa[y];
    fa[y]=x;
    mi[x]=min(mi[x],mi[y]);
    mx[x]=max(mx[x],mx[y]);
}
void solve()
{
    cin>>n;
    for(int i=1;i<=n;i++) 
    {
        cin>>a[i];
        fa[i]=i;
        mi[i]=mx[i]=a[i];
    }
    int x=a[1],id=1;
    for(int i=2;i<=n;i++) 
    {
        if(a[i]<x) merge(id,i);
        else x=a[i],id=i;
    }
    
    for(int i=n-1;i>=1;i--)
        if(find(i)!=find(i+1)&&mi[find(i+1)]<mx[find(i)])
            merge(i,i+1);
    for(int i=1;i<=n;i++) cout<<mx[find(i)]<<' ';
    cout<<'\n';
}
int main ()
{
    #ifndef ONLINE_JUDGE
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
    #endif 
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int T;
    cin>>T;
    while(T--) solve();
    return 0;
}

题解：CF2031D Penchick and Desert Rabbit

文章操作

D

相关推荐

评论

题解：CF2031D Penchick and Desert Rabbit