题目描述
一个全部为 \(0\) 的数组 \(a\) 。给01数组 \(b\) 和 \(q\) 个操作，每个操作 \(l_i,r_i\) ，即将 \(a\) 的 \([l_i,r_i]\) 全部赋值为 \(1\) ，你可以选一些操作，不要一些操作，求最后 \(a\) 和 \(b\) 最少有多少位不同。
\(1 \leq n,q \leq 2 \times 10^5\) 。
算法解析
很多区间，求最值，不可贪心，一眼 dp。
考虑一个状态数为 \(q\) 的 dp，设 \(f_i\) 是考虑前 \(i\) 个区间，且第 \(i\) 个必选，\([1,r_i]\) 的答案。这种区间会相互影响的题，一般思路是考虑区间的位置关系：
如果不交：
\[f_i = \min_{j < i}f_j + num1_{[r_j + 1,l_i - 1]} + num0_{[l_i,r_i]}
\]
如果相交：
\[f_i = \min_{j < i} f_j + num0_{[r_j + 1,r_i]}
\]
分为这两种情况，由于 \(num0\) （ \(0\) 个数）和 \(num1\) （ \(1\) 个数）可以差分，我们考虑将 \(j\) 的信息统一放进两棵线段树里面，取最小值。每次单点修改，区间查询。
但是笔者在这样实现的时候就傻眼了：第 \(5\) 个样例中有完全包含的情况，这种情况不应该用来转移，也就是说 \(j\) 的左右端点都有要求，这时候我们怎么办呢？树套树或者 CDQ？
事实上，我们尝试转变线段树的模式，每个 \(f_i\) 算出来之后分别贡献到 \([l_i,r_i]\) 和 \([r_i + 1,n]\) ，然后查询的时候单点查询当前区间左端点处的答案即可，就通过只贡献一部分的形式解决了这个问题。
这启发我们线段树的模式不同，最后求答案的难易度也不同，写线段树时要向模板题那样明确你要什么操作。
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5,inf = 0x3f3f3f3f;
struct Segment_Tree{
int a[N << 2],tag[N << 2];
inline void pushdown(int pos)
{
a[pos << 1] = min(a[pos << 1],tag[pos]);
a[pos << 1 | 1] = min(a[pos << 1 | 1],tag[pos]);
tag[pos << 1] = min(tag[pos << 1],tag[pos]);
tag[pos << 1 | 1] = min(tag[pos << 1 | 1],tag[pos]);
tag[pos] = inf;
}
inline void pushup(int pos) {a[pos] = min(a[pos << 1],a[pos << 1 | 1]);}
inline void modify(int l,int r,int L,int R,int k,int pos)
{
if(L <= l && r <= R) {a[pos] = min(a[pos],k); tag[pos] = min(tag[pos],k); return;}
int mid = (l + r) >> 1;
pushdown(pos);
if(L <= mid) modify(l,mid,L,R,k,pos << 1);
if(R > mid) modify(mid + 1,r,L,R,k,pos << 1 | 1);
pushup(pos);
}
inline int query(int l,int r,int x,int pos)
{
if(l == r) return a[pos];
int mid = (l + r) >> 1,ret = inf;
pushdown(pos);
if(x <= mid) ret = query(l,mid,x,pos << 1);
else ret = query(mid + 1,r,x,pos << 1 | 1);
pushup(pos);
return ret;
}
}t1,t2;
int f[N],n,b[N],m,num0[N],num1[N];
struct Q{
int l,r;
}q[N];
int main()
{
memset(t1.a,0x3f,sizeof(t1.a)); memset(t2.a,0x3f,sizeof(t2.a)); memset(t1.tag,0x3f,sizeof(t1.tag)); memset(t2.tag,0x3f,sizeof(t2.tag));
scanf("%d",&n);
for(int i = 1;i <= n;i++) scanf("%d",&b[i]);
for(int i = 1;i <= n;i++) num0[i] = num0[i - 1] + (b[i] == 0),num1[i] = num1[i - 1] + (b[i] == 1);
scanf("%d",&m);
for(int i = 1;i <= m;i++) scanf("%d%d",&q[i].l,&q[i].r);
sort(q + 1,q + m + 1,[&](Q x,Q y) {if(x.r != y.r) return x.r < y.r; return x.l > y.l;});
t1.modify(0,n,0,n,0,1); q[0].r = 0;
for(int i = 1;i <= m;i++)
{
int val1 = t1.query(0,n,q[i].l,1) + num1[q[i].l - 1] + num0[q[i].r] - num0[q[i].l - 1];
int val2 = t2.query(0,n,q[i].l,1) + num0[q[i].r];
f[i] = min(val1,val2);
t1.modify(0,n,q[i].r + 1,n,f[i] - num1[q[i].r],1);
t2.modify(0,n,q[i].l,q[i].r,f[i] - num0[q[i].r],1);
}
int ans = inf;
for(int i = 0;i <= m;i++) ans = min(ans,f[i] + num1[n] - num1[q[i].r]);
printf("%d",ans);
return 0;
}