题解归档 - cf2226E

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

• 本地编号：cf2226E
• 本地来源：problems/cf2226E/idea.md
• 题目链接：https://codeforces.com/contest/2226/problem/E
• 原始标题：cf2226E - Mental Monumental (Hard Version)

思路

cf2226E - Mental Monumental (Hard Version)

Pattern: prefix dynamic Hall conditions for nested intervals.

Reachability:

• An element x can become target residue r iff x == r or x >= 2r + 1.
• For mex k, reserve one exact copy for every present value r < k.
• Missing targets must be covered by spare elements. A spare x can cover exactly targets r <= (x - 1) / 2.

Hall condition:

• For every suffix of targets [t, k - 1],
  missing(t..k-1) <= spare elements with cap >= t.
• Let C_ge(2t+1) be the total number of inserted values at least 2t+1.
• Let D[l..r] be the number of distinct inserted values in that value interval.
• The condition becomes:
  k - t <= C_ge(2t+1) + D[t..min(k-1, 2t)].

Split by whether 2t < k - 1.

• Low half:
  h[t] = t + C_ge(2t+1) + D[t..2t], need h[t] >= k.
• High half:
  D[t..k-1] = prefD[k-1] - prefD[t-1].
  g[t] = t + C_ge(2t+1) - prefD[t-1], need
  g[t] >= k - prefD[k-1].

Online updates for inserted value x:

• It increases C_ge(2t+1) for all t <= (x - 1) / 2.
• If it is the first occurrence of x, it increases D[t..2t] for ceil(x/2) <= t <= x.
• If it is the first occurrence of x, it increases prefD[t-1] for t >= x+1, so g[t] gets -1 on [x+1, n].

Data structures:

• Two lazy segment trees over t = 0..n store range minimums of h and g.
• Fenwick over values 0..n stores distinct counts for prefD.
• The answer for a prefix only increases; after each insertion, while can(ans+1) holds, increment.

Check:

• Brute force bipartite matching for each prefix.
• Stress random arrays with duplicates and values larger than n.

代码

来源：problems/cf2226E/solution.cpp

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

struct SegTree{
    int n;
    vector<int> mn,lazy;
    SegTree(){}
    SegTree(int n_){init(n_);}
    void init(int n_){
        n=1;
        while(n<n_) n<<=1;
        mn.assign(n<<1,1000000000);
        lazy.assign(n<<1,0);
        for(int i=0;i<n_;i++) mn[n+i]=i;
        for(int i=n-1;i;i--) mn[i]=min(mn[i<<1],mn[i<<1|1]);
    }
    void apply(int p,int v){
        mn[p]+=v;
        lazy[p]+=v;
    }
    void range_add(int l,int r,int v,int p,int nl,int nr){
        if(l>nr||r<nl) return;
        if(l<=nl&&nr<=r){
            apply(p,v);
            return;
        }
        int mid=(nl+nr)>>1;
        range_add(l,r,v,p<<1,nl,mid);
        range_add(l,r,v,p<<1|1,mid+1,nr);
        mn[p]=lazy[p]+min(mn[p<<1],mn[p<<1|1]);
    }
    void add(int l,int r,int v){
        if(l>r) return;
        range_add(l,r,v,1,0,n-1);
    }
    int range_min(int l,int r,int p,int nl,int nr) const{
        if(l>nr||r<nl) return 1000000000;
        if(l<=nl&&nr<=r) return mn[p];
        int mid=(nl+nr)>>1;
        return lazy[p]+min(range_min(l,r,p<<1,nl,mid),range_min(l,r,p<<1|1,mid+1,nr));
    }
    int query(int l,int r) const{
        if(l>r) return 1000000000;
        return range_min(l,r,1,0,n-1);
    }
};

struct Fenwick{
    int n;
    vector<int> bit;
    void init(int n_){
        n=n_;
        bit.assign(n+1,0);
    }
    void add(int idx,int val){
        for(idx++;idx<=n;idx+=idx&-idx) bit[idx]+=val;
    }
    int sum(int idx) const{
        if(idx<0) return 0;
        if(idx>=n) idx=n-1;
        int res=0;
        for(idx++;idx>0;idx-=idx&-idx) res+=bit[idx];
        return res;
    }
};

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin>>T;
    while(T--){
        int n,max_a=0;
        cin>>n;
        vector<int>a(n);
        for(int &x:a){
            cin>>x;
            max_a=max(max_a,x);
        }
        SegTree low(n+1),high(n+1);
        Fenwick present;
        present.init(n+1);
        vector<char>seen(max(max_a,n)+2,false);
        int ans=0;
        for(int i=0;i<n;i++){
            int x=a[i];
            int cap=(x-1)/2;
            if(cap>=0){
                int r=min(cap,n);
                low.add(0,r,1);
                high.add(0,r,1);
            }
            if(!seen[x]){
                seen[x]=true;
                int l=(x+1)/2;
                int r=min(x,n);
                if(l<=r) low.add(l,r,1);
                if(x+1<=n) high.add(x+1,n,-1);
                if(x<=n) present.add(x,1);
            }
            auto can=[&](int k)->bool{
                if(k>=2){
                    int low_r=(k-2)/2;
                    if(low.query(0,low_r)<k) return false;
                }
                int need=k-present.sum(k-1);
                return high.query(k/2,k-1)>=need;
            };
            while(ans<n&&can(ans+1)) ans++;
            if(i) cout<<" ";
            cout<<ans;
        }
        cout<<"\n";
    }
    return 0;
}