题解归档 - cf2224F

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

• 本地编号：cf2224F
• 本地来源：problems/cf2224F/idea.md
• 题目链接：https://codeforces.com/contest/2224/problem/F
• 原始标题：cf2224F - Zhily and Cycle

思路

cf2224F - Zhily and Cycle

Pattern

A Hamiltonian cycle is a cyclic permutation p such that:

a[p_i] <= p_{i+1}.

Equivalently, every vertex i chooses a successor succ[i] >= a[i], all
successors are distinct, and the resulting permutation consists of one cycle.

Claim

First build any legal successor permutation by assigning target labels
1..n in increasing order to available vertices with a[i] <= target.

This gives a cycle cover. For a chosen edge x -> succ[x], define its interval:

[a[x], succ[x]].

Two cycles can be merged if they contain vertices x,y whose intervals
intersect. Swapping succ[x] and succ[y] keeps both inequalities true and
merges the two permutation cycles.

Algorithm

Use one initial cycle as the current main cycle. Store all still-outside edge
intervals in a segment tree keyed by left endpoint a[i], where each leaf keeps
the outside vertex with maximum current succ[i].

For each vertex x in the main cycle, query whether any outside interval
intersects [a[x], succ[x]]. If yes, swap successors and absorb that whole
outside cycle into the main cycle. Continue until no outside cycle remains.

If some cycle cannot be reached by interval intersections, output No.

Checks

• python tools/run_exe.py cf2224F - sample OK / valid construction.
• python tools/stress2.py cf2224F -n 1000 --keep-fail - OK with
  check.cpp against exhaustive permutation brute for small n.

代码

来源：problems/cf2224F/solution.cpp

#include<bits/stdc++.h>
#define ll long long
using namespace std;

struct segtree{
    int n,sz;
    vector<pair<int,int> > tr;
    vector<priority_queue<pair<int,int> > > *q;
    vector<int> *a,*nxt;
    vector<char> *in;
    void init(int _n,vector<priority_queue<pair<int,int> > > *_q,vector<int> *_a,vector<int> *_nxt,vector<char> *_in){
        n=_n,q=_q,a=_a,nxt=_nxt,in=_in;
        sz=1;
        while(sz<n) sz<<=1;
        tr.assign(sz<<1,{0,0});
        for(int i=1;i<=n;i++) pull_leaf(i);
        for(int i=sz-1;i;i--) tr[i]=max(tr[i<<1],tr[i<<1|1]);
    }
    void pull_leaf(int p){
        auto &h=(*q)[p];
        while(!h.empty()){
            int id=h.top().second,r=h.top().first;
            if(!(*in)[id]&&(*nxt)[id]==r) break;
            h.pop();
        }
        int x=p+sz-1;
        tr[x]=h.empty()?make_pair(0,0):h.top();
        x>>=1;
        while(x){
            tr[x]=max(tr[x<<1],tr[x<<1|1]);
            x>>=1;
        }
    }
    pair<int,int> qry_raw(int l,int r){
        pair<int,int> ans={0,0};
        l+=sz-1,r+=sz-1;
        while(l<=r){
            if(l&1) ans=max(ans,tr[l++]);
            if(!(r&1)) ans=max(ans,tr[r--]);
            l>>=1,r>>=1;
        }
        return ans;
    }
    int qry(int l,int r){
        while(true){
            auto p=qry_raw(1,r);
            if(p.first<l) return 0;
            int id=p.second;
            int pos=(*a)[id];
            pull_leaf(pos);
            auto z=qry_raw(pos,pos);
            if(z.second==id&&z.first==p.first&&!(*in)[id]&&(*nxt)[id]==p.first) return id;
        }
    }
};

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin>>T;
    while(T--){
        int n;
        cin>>n;
        vector<int>a(n+1),nxt(n+1);
        for(int i=1;i<=n;i++) cin>>a[i];
        vector<pair<int,int> > v;
        for(int i=1;i<=n;i++) v.push_back({a[i],i});
        sort(v.begin(),v.end());
        priority_queue<int> pq;
        int p=0;
        bool ok=true;
        for(int x=1;x<=n;x++){
            while(p<n&&v[p].first<=x) pq.push(v[p++].second);
            if(pq.empty()){
                ok=false;
                break;
            }
            int u=pq.top();
            pq.pop();
            nxt[u]=x;
        }
        if(!ok){
            cout<<"No\n";
            continue;
        }
        vector<int> cid(n+1,-1);
        vector<vector<int> > cyc;
        for(int i=1;i<=n;i++){
            if(cid[i]!=-1) continue;
            int id=cyc.size(),u=i;
            cyc.push_back({});
            while(cid[u]==-1){
                cid[u]=id;
                cyc.back().push_back(u);
                u=nxt[u];
            }
        }
        if((int)cyc.size()>1){
            vector<char> in(n+1,0),dead(cyc.size(),0);
            dead[0]=1;
            for(int x:cyc[0]) in[x]=1;
            vector<priority_queue<pair<int,int> > > hs(n+1);
            for(int i=1;i<=n;i++) if(!in[i]) hs[a[i]].push({nxt[i],i});
            segtree st;
            st.init(n,&hs,&a,&nxt,&in);
            deque<int> q;
            for(int x:cyc[0]) q.push_back(x);
            int rem=(int)cyc.size()-1;
            while(!q.empty()&&rem){
                int x=q.front();
                q.pop_front();
                while(rem){
                    int y=st.qry(a[x],nxt[x]);
                    if(!y) break;
                    int c=cid[y];
                    if(dead[c]){
                        st.pull_leaf(a[y]);
                        continue;
                    }
                    swap(nxt[x],nxt[y]);
                    dead[c]=1;
                    rem--;
                    for(int z:cyc[c]){
                        if(!in[z]){
                            in[z]=1;
                            q.push_back(z);
                            st.pull_leaf(a[z]);
                        }
                    }
                }
            }
            if(rem){
                cout<<"No\n";
                continue;
            }
        }
        vector<int> ans;
        vector<char> vis(n+1,0);
        int u=1;
        for(int i=1;i<=n;i++){
            if(vis[u]) break;
            vis[u]=1;
            ans.push_back(u);
            u=nxt[u];
        }
        if((int)ans.size()!=n||u!=1){
            cout<<"No\n";
            continue;
        }
        cout<<"Yes\n";
        for(int i=0;i<n;i++){
            if(i) cout<<" ";
            cout<<ans[i];
        }
        cout<<"\n";
    }
    return 0;
}