题解：P12568 [UOI 2023] An Array and Range Additions

· · 题解

思路分析

真紫吗？

我声称，一定存在一个最优解，满足所有被操作的区间存在一个顺序，使得左右端点都是严格单调递增的。

其证明是显然的：如果出现左端点或者右端点相同，那么较长的区间可以缩一下长度。如果出现包含，例如 l_1\le l_2\le r_2\le r_1，那么可以调整成 [l_1,r_2] 和 [l_2,r_1] 两个不包含的区间。

此时再看区间的权值。我们如果让第 i 个区间的权值为 2^i\times\inf，则任意两个位置 i,j，只要包含他们的区间的集合是不同的，那么他们最终就一定不同。

显然，由于所有的区间都是严格有序的，因此被某些区间同时包含的点一定是一个连续的区间。例外是没有被区间包含的部分。这一部分可能出现两段甚至多段。

对于这种包含关系区间，显然限制就是单个区间内的数字不重复。

紧接着，我们证明一个结论：没有被区间包含的部分只出现一个前缀和一个后缀仍然不劣。

证明也是简单的。对于一个非前后缀的不操作区间，我们将其前面的操作区间的右端点扩展到自己的右端点，将其后面的操作区间的左端点扩展到自己的左端点，则自己变为被操作区间，且限制变弱，不会从有解变成无解。

从而，我们将问题转化成了下面这个非常简单的题目：

选择一段区间 [l,r] 满足 [1,l-1]\cup[r+1,n] 中没有重复的数字，问至少需要将 [l,r] 拆分成多少个子区间才能保证任意一个区间内也没有重复的数字。

假设需要拆分成 a 个区间，那么由于两个区间可以交叉从而产生两个区间，故实际使用的个数为 \lfloor\frac{a}{2}\rfloor+1，特别的，a=0 的时候应该按照 0 计算。

假设我们枚举了 [l,r]，那么中间可以贪心：我从左端点开始，不停扩展，直到出现重复数字就开下一段，直到分完。这是 O(n^3) 的。

考虑把暴力分区间优化一下。显然可以使用倍增，记录 nxt_{p,i} 表示 p 向右分 2^i 个区间会分到哪里。这个东西是可以 O(n\log n) 预处理出来的。这样就优化到了 O(n^2\log n)。

最后考虑把枚举前后缀给优化掉。注意到前缀和后缀都相当于是进行一次“不操作”，因此我们直接断环为链，枚举从某一个位置开始先进行一次不操作之后，最少需要操作多少次才能够覆盖至少 n 个位置。于是时间复杂度为 O(n\log n)。

参考代码如下：

#include<bits/stdc++.h>
using namespace std;
// #define int long long
constexpr bool online=0;
int n,a[1000005],jmp[1000005][20],v[200005],vc,lap[200005],ans;
struct seg_tree{
    int v[1000005<<2];
    inline void ins(int cp,int cv,int l,int r,int p){
        int mid=l+r>>1; v[p]=min(v[p],cv);
        if(l==r) return;
        if(cp<=mid) ins(cp,cv,l,mid,p<<1);
        else ins(cp,cv,mid+1,r,p<<1|1);
    }
    inline int que(int ql,int qr,int l,int r,int p){
        if(ql<=l&&qr>=r) return v[p];
        int mid=l+r>>1,ret=1e9;
        if(ql<=mid) ret=min(ret,que(ql,qr,l,mid,p<<1));
        if(qr>mid) ret=min(ret,que(ql,qr,mid+1,r,p<<1|1));
        return ret;
    }
}sgt;
signed main(){
    if(online)
        freopen("modify.in","r",stdin),
        freopen("modify.out","w",stdout);
    ios::sync_with_stdio(0); cin>>n;
    /*
    一定存在最优操作序列满足左右端点序列均为严格递增序列，证明显然
    考虑让第 i 段的数值为 2^i*inf，则任意一个划分出来的区间之间一定不重复出现数字
    特别的，我可以留一段前缀或者后缀不进行任何操作

    每一段内都一定不能出现相同的数字，不操作前缀和后缀按照一段进行理解
    假设我们枚举有一段前后缀不进行操作，那么：
    中间剩余的部分必须划分区间
    需要划分的区间数如何计算：
    每一个点找到其后第一次出现数字重复的位置，即为区间右端点（开）
    于是对于每一个位置处理之后，使用 ST 可以快速跳转做到 O(\log)
    然而枚举前后缀的时间复杂度超了

    于是我们考虑“断环为链”。虽然并不是环，但是不操作前后缀被认为是等价的，所以可以认为是环
    于是枚举前后缀变成了枚举后缀起点，找最大前缀起点，然后倍增操作
    此时时间复杂度为 O(n\log n)，此题可解。

    注意一些细节，例如：如果我有 c 个区间，那么我实际上需要操作多少次：
    floor(c/2)+1，其证明是相对显然的：每一个区间最多将区间数+2,第一个区间只能做到+1

    wasec，怎么快速求出其后第一次出现重复的位置？
    对于左端点 p，我们找到这个数值下一次出现的位置 r
    那么这个位置的 ans 就是 min(r,ans[p+1,r-1])！
    证明显然，略去。
    */
    for(int i=0;i!=n;++i) cin>>a[i],v[i]=a[i];
    for(int i=0;i!=20;++i) jmp[n<<2][i]=n<<2;
    sort(v,v+n); vc=unique(v,v+n)-v; ans=n;
    for(int i=0;i!=n;++i) a[i]=lower_bound(v,v+vc,a[i])-v;
    for(int i=0;i!=n<<2;++i) a[i]=a[i%n];
    memset(sgt.v,0x0f,sizeof sgt.v);
    for(int i=0;i!=vc;++i) lap[i]=n<<2;
    for(int i=n*4-1;i>=0;i--){
        jmp[i][0]=min(lap[a[i]],sgt.que(i,lap[a[i]]-1,0,n<<2,1));
        lap[a[i]]=i; sgt.ins(i,jmp[i][0],0,n<<2,1);
        for(int j=1;j!=20;++j) jmp[i][j]=jmp[jmp[i][j-1]][j-1];
    }
    for(int i=0,rp,rc,j;i!=n;++i){
        for(rp=jmp[i][0],rc=0,j=19;j>=0;j--)
            if(jmp[rp][j]<i+n) rc|=1<<j,rp=jmp[rp][j];
        if(rp!=i+n) rc++;
        rc=rc/2+1; ans=min(ans,rc);
    }
    if(jmp[0][0]==n) ans=0;
    cout<<ans<<endl;
}
//0845 passed all samples exp 100pts.