题解归档 - cf2233D

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

• 本地编号：cf2233D
• 本地来源：problems/cf2233D/idea.md
• 题目链接：https://codeforces.com/contest/2233/problem/D
• 原始标题：cf2233D - Goods on the Shelf

思路

cf2233D - Goods on the Shelf

pattern:
one-swap repair / contiguous occurrence window

observations:
A value is already correct iff last[value] - first[value] + 1 == count[value].
Swapping two positions only changes the occurrence sets of the two swapped
values. Therefore, if more than two values are currently non-contiguous, the
answer is impossible.

candidate generation:
For a bad value x with count c, its final block must be some length-c
window. Since one swap moves exactly one x into the block and one x out of
it, this window must contain exactly c-1 current occurrences of x.

Sliding all length-c windows gives candidates:

• add: the unique non-x position inside the window.
• rem: the unique x position outside the window.

Swapping rem and add makes x contiguous. Then only the value currently at
add can be affected, so check in O(1) whether its positions remain contiguous
after removing add and adding rem.

check:
brute.cpp enumerates no swap and all swaps for small arrays and checks the
definition directly.

代码

来源：problems/cf2233D/solution.cpp

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n;
vector<int>a;
vector<vector<int>>pos;
bool goodValue(int id){
    const auto &v=pos[id];
    return v.back()-v.front()+1==(int)v.size();
}
bool goodAfter(int id,int rem,int add){
    const auto &v=pos[id];
    int c=(int)v.size();
    if(c==1) return true;
    int at=(int)(lower_bound(v.begin(),v.end(),rem)-v.begin());
    int mn=(at==0?v[1]:v[0]);
    int mx=(at==c-1?v[c-2]:v[c-1]);
    mn=min(mn,add);
    mx=max(mx,add);
    return mx-mn+1==c;
}
vector<pair<int,int>> candidates(int id){
    int c=(int)pos[id].size();
    ll total=0;
    for(int p:pos[id]) total+=p;
    vector<char> is(n+1,0);
    for(int p:pos[id]) is[p]=1;
    vector<pair<int,int>> out;
    int inCnt=0;
    ll inSum=0,nonSum=0;
    for(int i=1;i<=c;i++){
        if(is[i]){
            inCnt++;
            inSum+=i;
        }else nonSum+=i;
    }
    for(int L=1,R=c;R<=n;L++,R++){
        if(inCnt==c-1){
            int add=(int)nonSum;
            int rem=(int)(total-inSum);
            out.push_back({rem,add});
        }
        if(R==n) break;
        if(is[L]){
            inCnt--;
            inSum-=L;
        }else nonSum-=L;
        if(is[R+1]){
            inCnt++;
            inSum+=R+1;
        }else nonSum+=R+1;
    }
    return out;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin>>T;
    while(T--){
        cin>>n;
        vector<ll> raw(n+1);
        vector<ll> vals;
        for(int i=1;i<=n;i++){
            cin>>raw[i];
            vals.push_back(raw[i]);
        }
        sort(vals.begin(),vals.end());
        vals.erase(unique(vals.begin(),vals.end()),vals.end());
        a.assign(n+1,0);
        pos.assign(vals.size(),{});
        for(int i=1;i<=n;i++){
            int id=(int)(lower_bound(vals.begin(),vals.end(),raw[i])-vals.begin());
            a[i]=id;
            pos[id].push_back(i);
        }
        vector<int> bad;
        for(int id=0;id<(int)pos.size();id++){
            if(!goodValue(id)) bad.push_back(id);
        }
        if(bad.empty()){
            cout<<"YES\n";
            continue;
        }
        if((int)bad.size()>2){
            cout<<"NO\n";
            continue;
        }
        bool ok=false;
        int x=bad[0];
        for(auto [rem,add]:candidates(x)){
            int y=a[add];
            if((int)bad.size()==2 and y!=bad[1]) continue;
            if(y==x) continue;
            if(goodAfter(y,add,rem)){
                ok=true;
                break;
            }
        }
        cout<<(ok?"YES":"NO")<<"\n";
    }
    return 0;
}