P16902

Magus · 2026-07-18 14:42:08 · 题解

前言

双倍经验：CF2234E

分完治一定要 return 啊！！！

题解

观察这个数组 B 有什么性质，手玩几组样例：

• 1 4 1：此时 A_2 作为最小值覆盖的区间为 4，容易发现它一定是 A 整个序列中的最小值。
• 1 6 1 2 此时 A_2 作为最小值覆盖的区间为 6，容易发现它一定是 A 整个序列中的最小值。
• 3 3 3 此时 \sum B_i 为 9，而长度为 3 的序列的区间总数为 \frac{3(3+1)}{2}=10，此时一定无解。

所以我们就得到了本题的一些基本性质：

• 当 \sum B_i \neq \frac{n(n+1)}{2} 时无解。
• 当 B_i=i(n-i+1) 时，A_i 为 A 整个序列中的最小值。这个很好证明，因为当 A_i 为 A 整个序列中的最小值时，包含它的所有区间的最小值一定都是它，而区间总数即前面选 i 个起点，后面选 n-i+1 个终点，即 i(n-i+1)。并且，这个结论可以推广到任意一个区间 [l,r]，当 a_q=(q-l+1)(r-q+1) 时，它是 [l,r] 的最小值。

那我们知道了这个最小值 A_i 之后就好办了。我们发现这个最小值左边和右边的答案相互是独立的，因为如果有一段区间横跨中间，那么这个区间的最小值一定为 A_i，这个结论可以推广到任何一个区间，于是我们便能进行最值分治了。

与 CF2234E 不同的是这题可以不为排列，而且保证有解。

那我们怎么填数呢？我们知道，这道题中最值分治是从小的逐渐搜到大的，且 A_i 只确定相对大小，所以我们就只根据这个来填数，每层给最小值赋一个值，依次递增即可。

当 [l,r] 中出现了多个合法的 B_i 时，在判这个的时候我们可以任取一个合法的 B_i 直接进行分治，为什么呢？因为分治的区间肯定是越来越短的，如果存在另外一个合法的 B_i，那么他肯定会在之后的分治中被查到，那么便会触发条件 B_i>(i-l+1)(r-i+1)，此时它一定是上一层的最小值，那么给他赋上一层最小值赋的值，从他继续往下分即可。

那么我们就剩下了最后一个问题：如何快速地找到这个最小值呢？请注意：最值分治并没有保证分治出的两个区间长度相等，也就是说，会有可能出现最小值永远偏向一边的情况，如果你遍历区间 [l,r] 来找的话，你会被卡到 \Theta(n^2)。

所以我们使用一个双指针来搜：

这个东西均摊下来复杂度是 \mathcal{O}(n \log n)，可以感性理解一下，相当于把 n 次遍历变成了 \min(i,n-i) 次，且其遍历次数最多时恰好是最小值在中间的情况，也就是近似 \log。真的不是我不会严谨证明

所以我们就做完了这个题，我是不会告诉你我分治完没 return 的。

::::success[Code]

//风が私を呼んでいる
#include<bits/stdc++.h>
#define FastIO ios::sync_with_stdio(0);cin.tie(0);cout.tie(0) 
#define int long long
#define I using
#define AK namespace
#define CSPS2026 std
I AK CSPS2026;
const int maxn=1e6+10,maxm=1e3+10,mod=1e9+7;
int t,n,m,x,y,z,u,v,w,arr[maxn],res[maxn];
void split(int l,int r,int cur)
{
    if(l>r)return;
    if(l==r)
    {
        if(arr[l]>1)res[l]=cur-1;
        else res[l]=cur;
    }
    int i=l,j=r;
    for(int tot=l;tot<=r;tot++)
    {
        if(tot&1)
        {
            if(arr[i]==(i-l+1)*(r-i+1))
            {
                res[i]=cur;
                split(l,i-1,cur+1);
                split(i+1,r,cur+1);
                return;
            }
            if(arr[i]>(i-l+1)*(r-i+1))
            {
                res[i]=cur-1;
                split(l,i-1,cur);
                split(i+1,r,cur);
                return;
            }
            i++;
        }
        else
        {
            if(arr[j]==(j-l+1)*(r-j+1))
            {
                res[j]=cur;
                split(l,j-1,cur+1);
                split(j+1,r,cur+1);
                return;
            }
            if(arr[j]>(j-l+1)*(r-j+1))
            {
                res[j]=cur-1;
                split(l,j-1,cur);
                split(j+1,r,cur);
                return;
            }
            j--;        
        }
    } 
    return;
}
signed main()
{
//  freopen(".in","r",stdin);
//  freopen(".out","w",stdout); 
    FastIO;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>arr[i];
        u+=arr[i];
    }
//  if(u!=((n*(n+1))>>1))
    split(1,n,1);
    for(int i=1;i<=n;i++)cout<<res[i]<<" ";
    return 0;
}
/*
出好的题！
覆知盖点广识，题着切有目实合的际景背，解较比然自法。
出给题赞点人！
更的要据重是数正本基确，符一合好道的本题标准基！
*/ 

::::