题解归档 - cf2227D

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

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

思路

cf2227D - Palindromex

pattern: palindrome center structure + Manacher.

claim: in a palindromic subarray, every value that appears twice in the chosen interval has its two positions symmetric around one common center, so those values have the same pos1 + pos2. At most one value can appear only once, and then it must be exactly at the center.

For prefix values 0..k-1, a palindrome containing all of them can therefore use only a candidate center sum S whose frequency among these pair sums is at least k-1. If exactly one prefix value has another sum, one of its two occurrences must be at S/2.

necessary / sufficient: after fixing S, the complete pairs from the prefix force a minimum symmetric interval. Manacher radii on the original array tell whether that whole interval is actually palindromic. Extra values inside are harmless because the question only asks for mex at least k.

check: random small permutations were compared with brute force over all palindromic subarrays.

代码

来源：problems/cf2227D/solution.cpp

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

static vector<int> manacher_odd(const vector<int>& a){
    int n=(int)a.size();
    vector<int> d(n);
    int l=0,r=-1;
    for(int i=0;i<n;i++){
        int k=(i>r)?1:min(d[l+r-i],r-i+1);
        while(i-k>=0&&i+k<n&&a[i-k]==a[i+k]) k++;
        d[i]=k;
        if(i+k-1>r){
            l=i-k+1;
            r=i+k-1;
        }
    }
    return d;
}

static vector<int> manacher_even(const vector<int>& a){
    int n=(int)a.size();
    vector<int> d(n);
    int l=0,r=-1;
    for(int i=0;i<n;i++){
        int k=(i>r)?0:min(d[l+r-i+1],r-i+1);
        while(i-k-1>=0&&i+k<n&&a[i-k-1]==a[i+k]) k++;
        d[i]=k;
        if(i+k-1>r){
            l=i-k;
            r=i+k-1;
        }
    }
    return d;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin>>t;
    while(t--){
        int n;
        cin>>n;
        int m=2*n;
        vector<int> a(m),L(n,0),R(n,0);
        for(int i=1;i<=m;i++){
            int x;
            cin>>x;
            a[i-1]=x;
            if(!L[x]) L[x]=i;
            else R[x]=i;
        }
        vector<int> sum(n);
        for(int i=0;i<n;i++) sum[i]=L[i]+R[i];
        vector<int> d1=manacher_odd(a),d2=manacher_even(a);
        int maxs=4*n+5,inf=1e9;
        vector<int> cnt(maxs,0),mn(maxs,inf),mx(maxs,-inf),xr(maxs,0);
        int pref_xor=0,top1=-1,top2=-1;
        auto rebuild_top=[&](int add){
            vector<int> cand;
            auto put=[&](int x){
                if(x<0) return;
                for(int y:cand) if(y==x) return;
                cand.push_back(x);
            };
            put(top1);
            put(top2);
            put(add);
            sort(cand.begin(),cand.end(),[&](int x,int y){
                if(cnt[x]!=cnt[y]) return cnt[x]>cnt[y];
                return x<y;
            });
            top1=cand.empty()?-1:cand[0];
            top2=(cand.size()<2)?-1:cand[1];
        };
        auto feasible=[&](int k,int S)->bool{
            if(S<0) return false;
            int c=cnt[S];
            if(c<k-1) return false;
            if(c==k-1){
                if(S&1) return false;
                int out=pref_xor^xr[S];
                int center=S/2;
                if(out<0||out>=n) return false;
                if(L[out]!=center&&R[out]!=center) return false;
            }else if(c!=k) return false;
            if(c==0) return true;
            int need_l=mn[S],need_r=mx[S];
            if(S%2==0){
                int center=S/2;
                if(center<1||center>m) return false;
                int rad=d1[center-1]-1;
                return need_l>=center-rad&&need_r<=center+rad;
            }else{
                int center_left=(S-1)/2;
                if(center_left<1||center_left>=m) return false;
                int rad=d2[center_left];
                return need_l>=center_left-rad+1&&need_r<=center_left+rad;
            }
        };
        int ans=0;
        for(int k=1;k<=n;k++){
            int v=k-1,S=sum[v];
            cnt[S]++;
            mn[S]=min(mn[S],L[v]);
            mx[S]=max(mx[S],R[v]);
            xr[S]^=v;
            pref_xor^=v;
            rebuild_top(S);
            bool ok=(k==1);
            if(!ok&&feasible(k,top1)) ok=true;
            if(!ok&&feasible(k,top2)) ok=true;
            if(ok) ans=k;
        }
        cout<<ans<<"\n";
    }
    return 0;
}