自动搬运

查看原文

来自洛谷，原作者为

	UniGravity 好菜阿。

搬运于2025-08-24 23:12:04，当前版本为作者最后更新于2025-03-31 07:53:47，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

鲜花：Milthm 真的很好玩！111

感谢 @良心WA题人 指出了题解复杂度分析的错误。重写了复杂度分析。

首先有一种 $O(n^2\log n)$ 的做法：对于每个基准 $x$ 都二分出最大的 $m$。发现 check 时每次贪心找最前面的某个值配对，这样单次 check 是 $O(n)$ 的。

考虑优化单次 check 的复杂度，一次快速跳一整个长度为 $m$ 的段。发现我们可以预处理某个数 $x$ 后第一个 $x+1$ 的位置，通过倍增即可找出某个数后最小合法的 $x+m-1$ 的位置。同时再通过倍增找出 $x+m-1$ 后下一个 $x$ 的位置。这样 check 就是 $O(c\log n)$ 的（$c$ 是本次 check 合法的段数，因此实现时如果碰到不合法的就立即跳出）。

然后观察 $c$ 和什么有关，发现 $c$ 为 $\min(\min_{i=x}^{x+m-1}cnt_i,k)$，其中 $cnt_i$ 代表值 $i$ 的出现次数。

考虑双指针加上 check 判断。假设当前的区间为 $[x,x+m-1]$，则发现每次 check 后左右端点至少会有一个向右移动：

• 如果 check 失败，则已经找到了 $x$ 的答案，接下来 $x\gets x+1,m\gets m-1$。发现左端点右移，右端点不变。
• 如果 check 成功，则变成 $m\gets m+1$，右端点向右。

若每次 check 复杂度只和上次区间移动时变化的端点的出现次数（即 $cnt_l$ 或 $cnt_r$）有关（这样显然比 $\min(\min_{i=x}^{x+m-1}cnt_i,k)$ 的限制松），因为 $\sum_{i=1}^ncnt_i=n$，且 $cnt_i$ 最多只会在 $l,r$ 移动到的时候扫两遍，因此所有的 check 的 $c$ 之和的上界为 $O(n)$。

于是做完了。时间复杂度 $O(n\log n)$。

const int N=2000005;
int n,k,V,a[N],nxt[22][N],nv[22][N],pre[N];

il bool check(int bs,int m){
    int p=pre[bs],c,p1,p2;if(!p)return 0;
    // cerr<<"check "<<bs<<' '<<m<<'\n';
    forto(i,1,k){
        c=m-1,p1=p;
        forbk(t,21,0)if((1<<t)<=c)c-=1<<t,p1=nxt[t][p1];//,cerr<<t<<','<<p1<<' ';cerr<<'\n';
        // cerr<<p<<' '<<m<<' '<<p1<<'\n';
        if(!p1)return 0;
        if(i==k)return 1;
        p2=p;
        forbk(t,21,0)if(nv[t][p2]&&nv[t][p2]<=p1)p2=nv[t][p2];
        p2=nv[0][p2];if(!p2)return 0;
        p=p2;
    }
    return 1;
}

signed main(){
    n=read(),k=read(),V=read();
    forto(i,1,n)a[i]=read();
    forbk(i,n,1)nv[0][i]=pre[a[i]],nxt[0][i]=pre[a[i]+1],pre[a[i]]=i;
    // forto(i,1,n)cerr<<nxt[0][i]<<' ';cerr<<'\n';
    forto(t,1,21)forto(i,1,n)nxt[t][i]=nxt[t-1][nxt[t-1][i]],nv[t][i]=nv[t-1][nv[t-1][i]];
    int ans=0;
    forto(i,1,V){
        while(check(i,ans+1))ans++;
        printf("%d ",ans);
        if(ans)ans--;
    }
    puts("");
    return 0;
}