[atARC085F]NRE

令$(S_{a},S_{b})$表示$a_{i}in S_{a}$且$b_{i}in S_{b}$的i个数，那么答案相当于$S(0,1)+S(1,0)=S(0,1)+S({0,1},0)-S(0,0)$，容易发现$S({0,1},0)=sum_{i=1}^{n}[b_{i}==0]$，那么相当于最小化$S(0,1)-S(0,0)$，因此答案与1的位置无关

然后dp，用$f[i][j]$表示前i个点最小的$S(0,1)-S(0,0)$且$forall min(i,j)le kle n,a_{k}=[kle j]$，考虑转移：

1.如果$ile j$，那么$f[i][j]=min(f[i][j],f[i-1][j])$；如果$j<i$，那么$f[i][j]=min(f[i][j],f[i-1][j]+2b_{i}-1)$

2.对于操作区间$[l,r]$，如果$l=i$，那么$f[i][r]=min(f[i][r],min_{i-1le jle r}(f[i-1][j]))$（注意滚动后要从大到小枚举r）

容易发现以下两种转移都是由$f[i-1]$转移到$f[i]$，用线段树维护，支持区间修改，区间查询最小值，单点取min即可（初始值应该赋为无穷大），最终答案即为$min(f[n][i])+sum_{i=1}^{n}[b_{i}==0]$

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define N 200005
 4 #define L (k<<1)
 5 #define R (L+1)
 6 #define mid (l+r>>1)
 7 vector<int>v[N];
 8 int n,m,x,y,ans,a[N],tag[N<<2],f[N<<2];
 9 void upd(int k,int x){
10     tag[k]+=x;
11     f[k]+=x;
12 }
13 void down(int k){
14     if (tag[k]){
15         upd(L,tag[k]);
16         upd(R,tag[k]);
17         tag[k]=0;
18     }
19 }
20 void update(int k,int l,int r,int x,int y){
21     if (l==r){
22         f[k]=min(f[k],y);
23         return;
24     }
25     down(k);
26     if (x<=mid)update(L,l,mid,x,y);
27     else update(R,mid+1,r,x,y);
28     f[k]=min(f[L],f[R]);
29 }
30 void update(int k,int l,int r,int x,int y,int z){
31     if ((l>y)||(x>r))return;
32     if ((x<=l)&&(r<=y)){
33         upd(k,z);
34         return;
35     }
36     down(k);
37     update(L,l,mid,x,y,z);
38     update(R,mid+1,r,x,y,z);
39     f[k]=min(f[L],f[R]);
40 }
41 int query(int k,int l,int r,int x,int y){
42     if ((l>y)||(x>r))return 0x3f3f3f3f;
43     if ((x<=l)&&(r<=y))return f[k];
44     return min(query(L,l,mid,x,y),query(R,mid+1,r,x,y));
45 }
46 int main(){
47     scanf("%d",&n);
48     for(int i=1;i<=n;i++){
49         scanf("%d",&a[i]);
50         ans+=(a[i]^1);
51     }
52     scanf("%d",&m);
53     for(int i=1;i<=m;i++){
54         scanf("%d%d",&x,&y);
55         v[x].push_back(y);
56     }
57     for(int i=1;i<=n;i++)sort(v[i].begin(),v[i].end());
58     memset(f,0x3f,sizeof(f));
59     update(1,0,n,0,0);
60     for(int i=1;i<=n;i++){
61         for(int j=(int)v[i].size()-1;j>=0;j--)update(1,0,n,v[i][j],query(1,0,n,0,v[i][j]));
62         update(1,0,n,0,i-1,2*a[i]-1);
63     }
64     printf("%d",f[1]+ans);
65 }

View Code

原文链接: https://www.cnblogs.com/PYWBKTDA/p/13343741.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍;

也有高质量的技术群，里面有嵌入式、搜广推等BAT大佬

原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/368897

非原创文章文中已经注明原地址，如有侵权，联系删除

关注公众号【高性能架构探索】，第一时间获取最新文章

转载文章受原作者版权保护。转载请注明原作者出处！

[atARC085F]NRE

相关推荐