题解归档 - cf2226D

本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。

• 本地编号：cf2226D
• 本地来源：problems/cf2226D/idea.md
• 题目链接：https://codeforces.com/contest/2226/problem/D
• 原始标题：cf2226D - Reserved Reversals

思路

cf2226D - Reserved Reversals

Pattern: invariant by value parity extremes.

Operation:

• A segment can be reversed iff its minimum and maximum have opposite parity.
• Therefore two values x < y with the same parity cannot swap relative order if every opposite-parity value lies inside [x, y] or is absent: any segment containing both has same-parity extrema.

Necessary:

• For parity p, let the opposite parity values have minimum lo and maximum hi.
• A same-parity pair is locked only when the smaller value is < lo and the larger value is > hi.
• Thus every p value below all opposite values must appear before every p value above all opposite values.
• If the whole array has one parity only, no non-trivial operation exists, so the array must already be non-decreasing.

Sufficient:

• Any inversion not of the locked form has an opposite-parity value outside its value interval. That value can serve as an endpoint witness for a legal reversal, so the unlocked values can be rearranged around the fixed low/high order.
• Hence the only obstruction is first(high_p) < last(low_p) for either parity.

Algorithm:

• Collect mn[2], mx[2].
• If only one parity exists, check sorted.

• Otherwise, for each parity p:

  • low_p: values < mn[p^1];
  • high_p: values > mx[p^1];
  • reject if a high appears before a later low.

Check:

• BFS brute for n <= 8.
• Stress random arrays with duplicates against the brute.

代码

来源：problems/cf2226D/solution.cpp

/* Author: likely
 * Time: 2026-06-27
**/
#include<bits/stdc++.h>
using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin>>T;
    while(T--){
        int n;
        cin>>n;
        vector<int>a(n);
        bool has[2]={false,false};
        int mn[2]={INT_MAX,INT_MAX};
        int mx[2]={INT_MIN,INT_MIN};
        for(int i=0;i<n;i++){
            cin>>a[i];
            int p=a[i]&1;
            has[p]=true;
            mn[p]=min(mn[p],a[i]);
            mx[p]=max(mx[p],a[i]);
        }
        bool ok=true;
        if(!(has[0]&&has[1])){
            for(int i=1;i<n;i++) if(a[i-1]>a[i]) ok=false;
        }else{
            for(int p=0;p<2;p++){
                int q=p^1;
                int first_high=n,last_low=-1;
                for(int i=0;i<n;i++){
                    if((a[i]&1)!=p) continue;
                    if(a[i]<mn[q]) last_low=i;
                    if(a[i]>mx[q]&&first_high==n) first_high=i;
                }
                if(first_high<last_low) ok=false;
            }
        }
        cout<<(ok?"YES":"NO")<<"\n";
    }
    return 0;
}