CF2226D Reserved Reversals Solution

Ptll · 2026-04-29 10:34:23 · 题解

题目

思路正确为何没过？mx \to mxl，掉大分。

题解

我们发现，对于序列 a 是容易把序列划分为前半段的值为偶数，后半段的值为奇数的（显然）。

所以这里只需要考虑对于奇、偶序列内部是升序的即可。

我们假设对于偶数序列中前 i-1 个值的顺序已经排好了，考虑第 i 个值所处位置，若 a_i \ge a_{i-1} 那不用排了，这就是对的，如果不是，则需要考虑找到一个奇数 x 使 x < a_i \vee x > a_{i-1} 即可。

我们只需考虑是否存在这样的 x 即可，这用前缀最大值即可实现。

Code

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <cstring>
#include <set>
#ifdef _WIN32
#define getchar _getchar_nolock
#define putchar _putchar_nolock
#else
#define getchar getchar_unlocked
#define putchar putchar_unlocked
#endif
#define pll pair<ll,ll>
#define pld pair<ld,ld>
typedef long long ll;
typedef long double ld;
typedef __int128 i128;
namespace io {
    using namespace std;
    template<typename T> void debug (T x) {
        cerr<<x<<'\n';
    }
    template<typename T> void debuglen (T x) {
        cerr<<x<<' ';
    }
    template<typename T,typename...Args> void debug (T x,Args...args) {
        cerr<<x<<' ';
        debug(args...);
    }
    template<typename T> void debug (T *lt,T *rt) {
        ll len=rt-lt;
        for (ll i=0;i<len;i++) {
            debuglen(*(lt+i));
        }
        cerr<<'\n';
    }
    inline ll read () {
        char x=getchar();
        ll ans=0,f=1;
        while (x<'0'||x>'9') {
            if (x=='-') {
                f=-1;
            }
            x=getchar();
        }
        while (x>='0'&&x<='9') {
            ans=(ans<<1)+(ans<<3);
            ans+=(x^'0');
            x=getchar();
        }
        return ans*f;
    }
    void print (ll x) {
        if (x<0) {
            x=-x;
            putchar('-');
        }
        if (x>=10) {
            print(x/10);
        }
        putchar(x%10+'0');
    }
}
using namespace io;
const ll N=1e6+5,mod=1e9+7,inf=2e18;
const ld eps=1e-6;
ll n,a[N];
inline void solve () {
    n=read();
    ll mx=-inf,mn=inf,mxl=-inf,mnl=inf,cnt=-inf;
    for (ll i=1;i<=n;i++) {
        a[i]=read();
        if (a[i]&1) {
            mx=max(mx,a[i]);
            mn=min(mn,a[i]);
        }
        else {
            mxl=max(mxl,a[i]);
            mnl=min(mnl,a[i]);
        }
    }
    for (ll i=1;i<=n;i++) {
        ll x=a[i];
        if (x&1) {
            if (x<=mnl&&cnt>x) {
                puts("NO");
                return ;
            }
            if (x>=mxl) {
                cnt=max(cnt,x);
            }
        }
    }
    cnt=-inf;
    for (ll i=1;i<=n;i++) {
        ll x=a[i];
        if (x&1) {
            continue;
        }
        if (x<=mn&&cnt>x) {
            puts("NO");
            return ;
        }
        if (x>=mx) {
            cnt=max(cnt,x);
        }
    }
    puts("YES");
}
int main () {
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);
    ll T=1;
    T=read();
    while (T--) {
        solve();
    }
    return 0;
}
/*
(1, 1, 2, 3) 1 1
(2, 1, 3) 1 1
(5, 4, 3, 2, 1) 0 0
(4, 1, 2, 3, 3, 6) 1 0
(4, 2, 4, 2, 4) 0 0
(3, 3, 1, 5, 5, 2) 0 0
*/