一句话妙~
原题是要我们求下标从1到n.可以选择一些操作,让原本全是0的ai的区间[l,r]变成1,求ai和bi不同数量的min.
咋一眼看似乎十分懵逼,接下来就是一个很巧妙的转化了.首先我们定义二元组(i,j)代表同一下标下第一个数是多少(0/1),第二个数是多少(0/1).
然后我们就可以发现答案就是要我们求(0,1)+(1,0)的数量.Emmm接着转化一下,把第一维的1去掉,方便我们dp,是不是就是(0,1)-(0,0)+(x,0).(x,0)已知,我们只要求(0,1)-(0,0)数量的一个最小值即可,这里我们考虑dp,令f[i]表示到了i这个位子,这个表达式的最小值是多少,Emmmm,这里需要我们用个数据结构来维护一下区间最值,线段树树状数组(这里我们用树状数组,因为只有单点修改而已)都可~如此这题就完美的解决了.
代码如下:

#include <bits/stdc++.h>
using namespace std;
const int N=3e5+5;
int h[N],a[N];
int n,q;
int hmin[N];
int lowbit(int x)   {  return x&(-x); }
void add(int pos,int val)//在点pos更新值为val.
{
    h[pos]=val;//这句没必要.
    while(pos<=n)
    {
        hmin[pos]=min(val,hmin[pos]);//这个点成为val.
        int cnt=lowbit(pos);
        for(int i=1;i<cnt;i<<=1)
        {
            hmin[pos]=min(hmin[pos-i],hmin[pos]);
        }
        pos+=lowbit(pos);
    }
}

int query(int l,int r)//查询区间l,r的min.
{
    int res=2e9;
    while(r>=l)
    {
        res=min(h[r],res),r--;
        for(;r-lowbit(r)>=l;r-=lowbit(r))
        {
            res=min(hmin[r],res);
        }
    }
    return res;
}

vector<int>v[N];

int main()
{
    scanf("%d",&n);int ans=0;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        ans+=(a[i]==0);
    }
    scanf("%d",&q);
    while(q--)
    {
        int l,r;
        scanf("%d%d",&l,&r);
        v[l].push_back(r);
    }
    memset(h,0x3f,sizeof h);
    memset(hmin,0x3f,sizeof hmin);
    h[0]=0;hmin[0]=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<v[i].size();j++)
        {
            int r=v[i][j];
            int mi=h[i-1];//假如我取了这个,那是不是我就是0.
            mi=min(mi,query(max(i-1,1),r));
            if(mi<h[r])
            {
                add(r,mi);
            }
        }
        h[i]=min(h[i],h[i-1]+(a[i]==0?-1:1));
    }
    printf("%d\n",h[n]+ans);
    return 0;
}