AT3673 [ARC085D] NRE 题解

Problem

​ 给定一个全为\(0\)的数组\(A\)，给一个数组\(B\)和\(m\)个操作，每个操作将数组\(A\)指定区间改成\(1\)，问合理选择部分操作后使得两个数组的\(\sum[A_i \neq B_i]\)最小。

Solution

​ 考虑把这个式子变形一下：

\[\sum[A_i \neq B_i] \\ \rightarrow \sum[A_i=0][B_i=1]+\sum[A_i=1][B_i=0] \\ \rightarrow \sum[A_i=0]+\sum[B_i=0]([A_i=1]-[A_i=0]) \]

​ 第一项\([A_i=0]\)是个定值，\(([A_i=1]-[A_i=0])\)也只和\(A\)有关，所以现在要考虑的只有\([B_i=0]\)。

​ 考虑DP，设\(f_i\)表示前\(i\)个中上式的最小值。首先可以从\(f_i\)转移到\(f_{i+1}\)，表示不选以\(i\)为左端点的区间，要么可以转移到右端点

Code

#include<bits/stdc++.h>
using namespace std;

vector<int>L[200005];

int n,m,Ans;

int A[200005];

struct Segment_Tree{

    #define ls k<<1|0
    #define rs k<<1|1
    #define inf 0x3f3f3f3f

    int tag[800005],Min[800005];

    inline void Pushup(int k){
        Min[k]=min(Min[ls],Min[rs]);
    }

    inline void Pushdown(int k){
        if(tag[k]){
            tag[ls]+=tag[k];
            tag[rs]+=tag[k];
            Min[ls]+=tag[k];
            Min[rs]+=tag[k];
            tag[k];
        }
        return;
    }

    void Initialize(){
        memset(Min,0x3f,sizeof Min);
    }

    void Insert(int k,int l,int r,int pos,int val){
        if(l==r){
            Min[k]=min(Min[k],val);
            return;
        }
        Pushdown(k);
        int mid=l+r>>1;
        if(pos<=mid)
            Insert(ls,l,mid+0,pos,val);
        else
            Insert(rs,mid+1,r,pos,val);
        return Pushup(k);
    }

    void Change(int k,int l,int r,int wl,int wr,int val){
        if(wl> r||l> wr)
            return;
        if(wl<=l&&r<=wr){
            tag[k]+=val;
            Min[k]+=val;
            return;
        }
        Pushdown(k);
        int mid=l+r>>1;
        Change(ls,l,mid+0,wl,wr,val);
        Change(rs,mid+1,r,wl,wr,val);
        return Pushup(k);
    }

    int query(int k,int l,int r,int wl,int wr){
        if(wl> l||l> wr)    
            return inf;
        if(wl<=l&&r<=wr)
            return Min[k];
        Pushdown(k);
        int res=inf,mid=l+r>>1;
        res=min(res,query(ls,l,mid+0,wl,wr));
        res=min(res,query(rs,mid+1,r,wl,wr));
        return res;
    }

    #undef ls
    #undef rs
    #undef inf

}T;

inline int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){
       if(ch=='-')f=-1;
       ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
       x=(x<<1)+(x<<3)+ch-'0';
       ch=getchar();
    }
    return x*f;
}

int main(){
    
    n=read();

    for(register int i=1;i<=n;++i)
        A[i]=read();
    
    m=read();

    for(register int i=1;i<=m;++i){
        int l=read();
        int r=read();   
        L[l].push_back(r);
    }

    T.Initialize();

    T.Insert(1,0,n,0,0);

    for(register int i=1;i<=n;++i){
        int N=L[i].size();
        for(register int k=0;k<N;++k){
            int Min=T.query(1,0,n,0,L[i][k]);
            T.Insert(1,0,n,L[i][k],Min);
        }
        T.Change(1,0,n,0,i-1,A[i]?+1:-1);
        Ans+=(A[i]==0);
    }

    printf("%d\n",Ans+T.query(1,0,n,0,n));

    return 0;
}