【AtCoder Regular Contest 085 F】NRE

mrsrz 3月 13, 2020

数据结构优化 dp。

题目大意：

给定 01 串 $b$ 和全 0 串 $a$，再给定 $m$ 个区间 $[l_i,r_i]$，可以从中选择任意一些区间。

若第 $i$ 个区间被选择，则会将 $a_{l_i..r_i}$ 都变成 1。

求 $\sum\limits_{i=1}^n [a_i\neq b_i]$ 的最小值。

题解：

一个巧妙的思路。

$\begin{align} \sum_{i=1}^n [a_i\neq b_i]&=\sum_{i=1}^n [a_i=0][b_i=1]+\sum_{i=1}^n [a_i=1][b_i=0]\\ &=\sum_{i=1}^n[a_i=0][b_i=0]+\sum_{i=1}^n [a_i=0][b_i=1]+\sum_{i=1}^n [a_i=1][b_i=0]-\sum_{i=1}^n[a_i=0][b_i=0]\\ &=\sum_{i=1}^n[b_i=0]+\sum_{i=1}^n [a_i=0][b_i=1]-\sum_{i=1}^n[a_i=0][b_i=0] \end{align}$

其中 $\sum\limits_{i=1}^n[b_i=0]$ 是定值。因此我们只需要最小化 $\sum\limits_{i=1}^n[b_i=0]+\sum\limits_{i=1}^n [a_i=0][b_i=1]-\sum_{i=1}^n[a_i=0][b_i=0]$ 的值即可。

这样一来，我们将区间赋 $1$ 的操作对答案的贡献就是 $0$，就没有复杂的讨论了。

考虑令 $f_i$ 表示到目前为止，最后一个 $1$ 在位置 $i$ 时的最小值。

假设当前考虑到位置 $x$：

位置 $x$ 空着，那么对于 $i\in[0,x)$，$f_i=f_i+(2\cdot [b_i=1]-1)$。
有线段的开头是位置 $x$，设右端点为 $r$，则 $f_r=\min\{f_r,f_0,f_1,\ldots,f_{r-1}\}]$。从 $0\sim r-1$ 更新 $r$ 就解决了线段重合的问题。

这个 dp 可以用线段树维护。

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

Code：

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
const int N=2e5+5;
int n,b[N],m,sum;
vector<int>vec[N];
int d[N<<2],tag[N<<2];
void build(int l,int r,int o){
    if(l==r)d[o]=0x3fffffff;else{
        const int mid=l+r>>1;
        build(l,mid,o<<1),build(mid+1,r,o<<1|1);
        d[o]=0x3fffffff;
    }
}
void pushdown(int o){
    int&x=tag[o];
    tag[o<<1]+=x,tag[o<<1|1]+=x;
    d[o<<1]+=x,d[o<<1|1]+=x,x=0;
}
void modify(int l,int r,int o,const int&pos,const int&val){
    if(l==r)d[o]=min(d[o],val);else{
        if(tag[o])pushdown(o);
        const int mid=l+r>>1;
        if(pos<=mid)modify(l,mid,o<<1,pos,val);else modify(mid+1,r,o<<1|1,pos,val);
        d[o]=min(d[o<<1],d[o<<1|1]);
    }
}
void modify(int l,int r,int o,const int&L,const int&R,const int&val){
    if(L<=l&&r<=R){
        d[o]+=val,tag[o]+=val;
    }else{
        pushdown(o);
        const int mid=l+r>>1;
        if(L<=mid)modify(l,mid,o<<1,L,R,val);
        if(mid<R)modify(mid+1,r,o<<1|1,L,R,val);
        d[o]=min(d[o<<1],d[o<<1|1]);
    }
}
int query(int l,int r,int o,const int&L,const int&R){
    if(L<=l&&r<=R)return d[o];
    pushdown(o);
    const int mid=l+r>>1;
    if(L<=mid&&mid<R)return min(query(l,mid,o<<1,L,R),query(mid+1,r,o<<1|1,L,R));
    if(L<=mid)return query(l,mid,o<<1,L,R);
    return query(mid+1,r,o<<1|1,L,R);
}
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;++i)cin>>b[i],sum+=!b[i];
    for(cin>>m;m--;){
        int l,r;
        cin>>l>>r;
        vec[l].push_back(r);
    }
    build(0,n,1);
    modify(0,n,1,0,0);
    for(int i=1;i<=n;++i){
        for(int y:vec[i])modify(0,n,1,y,query(0,n,1,0,y));
        modify(0,n,1,0,i-1,b[i]?1:-1);
    }
    printf("%d\n",query(0,n,1,0,n)+sum);
    return 0;
}