• 周三. 6月 29th, 2022

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

ARC085D NRE

admin

11月 28, 2021

Descrption

给定序列 ({a_n}),值域为 ({0,1}),和 (m) 种操作,每个操作可以将 ({b_n}) 的某个区间全部赋为一((b_i) 初始时全为零)。最小化 (sum_{i=1}^n [a_i
eq b_i])

Solution

可以看作最大化 (sum_{i=1}^n [a_i=b_i]),初始的答案是 0 的个数。考虑赋值操作对答案的影响,原来为 0,贡献就是 -1,原来是 1,贡献就是 1,记为 (c_i)。所以问题就转换为可以使得一个区间的元素都被选择,要使得最后被选择的所有元素的权值和最大。

那就有点类似背包了,但是会有交集的问题,所以考虑按右端点排序,分类讨论。令 (f_i) 表示将第 (i) 个区间作为结尾的最大权值和。那么就有两种情况。

  1. 两个区间无交集,可以直接转移,(f_i=f_j+S_{r_i}-S_{l_i-1})
  2. 区间有交集,但不能有完全覆盖,(f_i=f_j+S_{r_i}-S_{r_j})
    考虑形式化这些限制条件。第一个就是 (r_j <l_ileq r_i),第二个是 (r_jleq r_i)(r_jgeq l_i) 并且 (l_j<l_i)。发现是个三维偏序,所以无脑 CDQ 分治就可了。
#include<stdio.h>
#include<algorithm>
#include<cassert>
using namespace std;

typedef long long ll;

inline int read(){
    int x=0,flag=1; char c=getchar();
    while(c<'0'||c>'9'){if(c=='-') flag=0;c=getchar();}
    while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+c-48;c=getchar();}
    return flag? x:-x;
}

const int N=2e5+7;

struct Seg{
    int l,r,dp;
}a[N];

int s[N],c[N],n;

inline bool Cmp1(const Seg &X,const Seg &Y){return X.r<Y.r;}
inline bool Cmp2(const Seg &X,const Seg &Y){return X.l<Y.l;}

inline int lowbit(int x){return -x&x;}
inline void add(int x,int v){while(x<=n) c[x]=max(c[x],v),x+=lowbit(x);}
inline int query(int x){int ret=-n;while(x)ret=max(ret,c[x]),x-=lowbit(x);return ret;}
inline void Clear(int x){while(x<=n)c[x]=-n,x+=lowbit(x);}

void CDQ(int lf,int rf){
    if(lf==rf) return ;
    int mid=(lf+rf)>>1; CDQ(lf,mid);
    sort(a+mid+1,a+rf+1,Cmp2);
    for(int i=mid+1,ret=0,j=lf;i<=rf;i++){
        while(j<=mid&&a[j].r<=a[i].l)
            ret=max(ret,a[j].dp),j++;
        a[i].dp=max(a[i].dp,ret+s[a[i].r]-s[a[i].l]);
    }
    sort(a+lf,a+mid+1,Cmp1); int j=mid;
    for(int i=rf;i>mid;i--){
        while(j>=lf&&a[j].r>a[i].l)
            add(a[j].l+1,a[j].dp-s[a[j].r]),j--;
        a[i].dp=max(a[i].dp,query(a[i].l)+s[a[i].r]);
    }
    for(int i=mid;i>j;i--) Clear(a[i].l+1);
    sort(a+mid+1,a+rf+1,Cmp1);
    CDQ(mid+1,rf);
}

int main(){
    n=read(); int ans=0;
    for(int i=1,x;i<=n;i++)
        s[i]=((x=read())? 1:-1)+s[i-1],ans+=x;
    int m=read();
    for(int i=1;i<=n;i++) c[i]=-n;
    for(int i=1;i<=m;i++)
        a[i].l=read()-1,a[i].r=read(),a[i].dp=-n;
    a[++m]=(Seg){0,0,0},sort(a+1,a+1+m,Cmp1),CDQ(1,m);
    int ret=0; for(int i=1;i<=m;i++) ret=max(ret,a[i].dp);
    printf("%d",ans-ret);
}

发表评论

您的电子邮箱地址不会被公开。