Solution P12008 【MX-X10-T4】[LSOT-4] Fragment of Memories

· · 题解

鲜花：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 复杂度只和上次区间移动时变化的端点的出现次数（即 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;
}