[DP记录]AT3673 [ARC085D] NRE
command_block
2021-05-02 13:52:12
**题意** ：给定长为 $n$ 的 $01$ 数组 $b$ 。
有一个长度同为 $n$ 的数组 $A$ ，初始时为全 $0$。
给定 $m$ 个区间，可以选择若干区间，将 $a$ 中区间内的元素置为 $1$。
最小化 $\sum\limits_{i=1}^n[A_i\neq B_i]$ 的值。
$n\leq 2\times 10^5$ ，时限 $\texttt{3s}$。
------------
注意到 $A,B$ 均为 $01$ 数组，则
$$
\begin{aligned}
&[A_i\neq B_i]\\
=&[A_i=0][B_i=1]+[A_i=1][B_i=0]\\
=&[A_i=0][B_i=1]+[B_i=0]-[A_i=0][B_i=0]\\
\end{aligned}
$$
此时不需要考虑 $A_i=1$ 的贡献。
> 只有 $01\ \rightarrow$ 正难则反
其中 $[B_i=0]$ 是定值，于是我们只需最小化 ：
$$\sum\limits_{i=1}^n[A_i=0][B_i=1]-[A_i=0][B_i=0]$$
考虑 $\rm DP$ ，记 $f[i][j]$ 表示考虑了所有 $l\leq i$ 的区间，最右覆盖到 $j$ ， $[1,i]$ 的贡献最小值。
特殊地，若没有向右覆盖，则 $j$ 记为 $i$ 。
从 $f[i-1][\_]$ 转移至 $f[i][\_]$ 时 ：
不选区间 :
$$f[i][i]\leftarrow f[i-1][i-1]+[B_i=1]-[B_i=0]$$
$$f[i][j]\leftarrow f[i-1][j]\quad(j\geq i)$$
枚举区间 $[i,r]$ ，有 ：
$$f[i][r]\leftarrow f[i-1][i-1\sim r]$$
可以用线段树维护，复杂度为 $O(n\log n)$。
```cpp
#include<algorithm>
#include<cstdio>
#include<vector>
#define MaxN 200500
using namespace std;
int n,a[MaxN<<2],x[MaxN],to,wfc,wfl,wfr,ret;
void build(int l=0,int r=n,int u=1)
{
x[l]=a[u]=(!l ? 0 : n);
if (l==r)return ;
int mid=(l+r)>>1;
build(l,mid,u<<1);
build(mid+1,r,u<<1|1);
}
void chg(int l=0,int r=n,int u=1)
{
if (l==r){x[l]=a[u]=min(x[l],wfc);return ;}
int mid=(l+r)>>1;
if (to<=mid)chg(l,mid,u<<1);
else chg(mid+1,r,u<<1|1);
a[u]=min(a[u<<1],a[u<<1|1]);
}
void qry(int l=0,int r=n,int u=1)
{
if (wfl<=l&&r<=wfr)
{ret=min(ret,a[u]);return ;}
int mid=(l+r)>>1;
if (wfl<=mid)qry(l,mid,u<<1);
if (mid<wfr)qry(mid+1,r,u<<1|1);
}
vector<int> l[MaxN];
int m,b[MaxN];
int main()
{
scanf("%d",&n);build();
for (int i=1;i<=n;i++)scanf("%d",&b[i]);
scanf("%d",&m);
for (int i=1,tl,tr;i<=m;i++){
scanf("%d%d",&tl,&tr);
l[tl].push_back(tr);
}
for (int i=1;i<=n;i++){
for (int j=0;j<l[i].size();j++){
ret=n;wfl=i-1;wfr=l[i][j];qry();
to=l[i][j];wfc=ret;chg();
}
wfc=x[i-1]+(b[i]==1)-(b[i]==0);
to=i;chg();
}
wfl=wfr=n;ret=n;qry();
for (int i=1;i<=n;i++)ret+=(b[i]==0);
printf("%d",ret);
return 0;
}
```