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

min_inf · 2025-06-09 19:22:35 · 题解

为什么是倍增？

首先我们显然可以加一个随机的巨大数字，这样只要让相同的数不能被相同的区间覆盖到即可。然后考虑 l 和 r+1 构成的可重集，如果我们将前一半和后一半依次配对，这样对于每个数只要相邻两次出现之间有至少一个端点且第一次出现前和最后一次出现后至少有一个端点就满足了要求，显然这样是最优的。

现在问题就变成了，求出一个最小的集合 S 满足一些条件，答案是 \lceil\frac{|S|}2\rceil：

如果只有第一种条件，显然可以按 b 从小到大贪心，然后加入第二种条件最多让答案 +1。我们二分一个最小的 \min S 使得答案不会改变，然后对于 c<\min S 的第二类限制加入第一类限制 (d,n+1) 再跑一遍贪心即可，如果答案还是会增加那显然就无力回天了。

时间复杂度 O(n\log n)。

cin>>n;rep(i,1,n)cin>>a[i];
map<int,vector<int>> occ;rep(i,1,n)occ[a[i]].push_back(i);
vector<pair<int,int>> rg;
for(auto [x,v]:occ)repn(i,v.size()-1)rg.emplace_back(v[i]+1,v[i+1]);
sort(allc(rg),[&](auto x,auto y){return x.sec<y.sec;});
if(rg.empty()){cout<<"0\n";return 0;}
auto solve=[&](int s){
    int ans=0;
    for(auto [l,r]:rg)if(l>s)s=r,++ans;
    return ans;
};
int t=solve(0);
int l=1,r=rg[0].sec;
while(l<r){
    int mid=l+r>>1;
    if(solve(mid)>=t)l=mid+1;else r=mid;
}
int p=1;
for(auto [x,v]:occ)if(v.size()>1&&v[0]<l)p=max(p,v.back());
rg.emplace_back(p+1,n+1);cout<<(solve(0)+1)/2<<'\n';