刷题记录: wannafly25 E 牛客NC19469 01串 [线段树维护动态dp]

传送门:牛客

题目描述:

Bieber拥有一个长度为n的01 串，他每次会选出这个串的一个子串作为曲谱唱歌，考虑该子串从左
往右读所组成的二进制数P。 Bieber每一秒歌唱可以让P增加或减少 2 的 k次方（k由Bieber选
定），但必须保证任意时刻其P大于等于0。
Bieber 是一位追求效率的人 每次Bieber都想知道他歌唱的最少时间将这个数P变成0。
Bieber 正和 一位DJ合作，他随时可能修改串上的一个字符。
输入:
4
1101
1
1 1 4
输出:
3

本文参考了:这篇题解与这篇题解与我的一位学长的详细解释.

说实话,那两篇题解写的是真的简略,而且这道题是牛客上的题,这就意味着基本上没有几篇题解,事实上也是如此,全网只有这两篇,在想这道题的过程中,我曾一度想要放弃,但是一想到我当初写牛客题解的初衷不就是写那些题解稀少的题的题解来帮助其他人更好的刷牛客竞赛的题吗??,然后就请教了一位大佬学长.故最后有了这篇题解.

---

首先这道题的解法是线段树维护动态dp,官方的贪心想法要比动态dp麻烦许多倍,因此此处就只考虑动态dp的做法.

所谓动态dp就是可修改的dp.所以我们得先考虑出dp方程.考虑使用$dp[i][j]$来记录一段区间从后面的区间进位上来$j$,并且向前面的区间进位上去$i$的情况下变为0的最小步骤数.可能有很多人看完这个dp方程会有点疑惑,就像我刚开始看到题解中的dp方程完全一头雾水一样,因此我举个栗子:(当我们计算A区间$dp[0][0]$的情况)

只考虑两个连续的区间B、C和他们组成的区间A的关系
比如B为0100 C为1011,那A就是0100 1011
这时候我们如果希望A变为全0，那就是B和C都变为全0
那么此时就是C区间向B区间进位了或者没有进位(在这里,我们贪心的想一下,显然进位最大是1的时候是最优的,不然我们由后面进位2显然超过了B区间直接+1的步骤数所以此处只考虑进位为0/1的情况).

解释一下此处的进位是什么意思.因为一系列操作,我们的C区间想变为0的话,有两种情况,要么没有进位,C区间直接变成了0000,要么C区间变成了10000,然后向前面进了一位,然后此时C变成0000,B区间因为C区间的进位变成了0101,此时的两种情况分别C区间分别对应的$dp$方程就是$dp[0][0],dp[1][0]$.
注意此时的10000情况可以直接通过一个操作变成0000!!

对应我们的C区间的进位情况,显然我们的B区间也会有两种情况:
1.当我们的C区间是$dp[0][0]$的情况时,因为C区间是B区间紧挨着的区间,所以此时B区间必没有向它进位的区间,这就意味着B区间此时只有$dp[0][1]$(因为A区间为(0,0),所以B区间不能向前进位).此时我们的A区间变为0所需要的步骤就是$B.dp[0][0]+C.dp[0][0]$
2.当我们的C区间是$dp[1][0]$的情况时,因为C区间是B区间紧挨着的区间,所以此时B区间必获得了一个进位,所以此时我们的B区间只能是$dp[0][1]$,此时我们的A区间变为0所需要的步骤数就是$B.dp[0][1]+C.dp[1][0]$

类似的我们A区间还有三种情况,分别是1.A区间向前面区间进位,后面区间没有向A区间进位 2.A区间向前面区间进位,后面区间向A区间进位 3.A区间没有向前面区间进位,后面区间向A区间进位,分析的方法同上,此处就不在赘述了

顺便附带一下对于初始化的解释(以区间为单个1为例):
dp[0][0]=1,直接减去2的0次幂，1步
dp[0][1]=1,减去2的1次幂，因为此时得到一个进位,原本的1变成了10，所以去掉10
dp[1][0]=1,需要向前进位一个1,所以添加一个2的0次幂，1变为10
dp[1][1]=0,不用额外操作，1加上后面进位的1后变为10，可以直接进位

至此,dp分析结束

---

对于此题来说,我们需要维护的是一个带修改的dp,我们可以将我们的dp方程看成一个二维的矩阵,然后对于我们的区间合并来说,就是两个矩阵的合并,对于这个,我们可以使用线段树进行维护,具体维护方法可以参考具体代码

---

下面是具体的代码部分:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define root 1,n,1
#define ls rt<<1
#define rs rt<<1|1
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
inline ll read() {ll x=0,w=1;char ch=getchar();for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') w=-1;for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';return x*w;
}
#define maxn 1000000
const double eps=1e-8;
#define	int_INF 0x3f3f3f3f
#define ll_INF 0x3f3f3f3f3f3f3f3f
struct Segment_tree{int l,r;int dp[2][2];void init(int x) {if(x==1) {dp[0][0]=dp[1][0]=dp[0][1]=1;dp[1][1]=0;}else {dp[0][0]=0;dp[0][1]=1;dp[1][0]=1;dp[1][1]=1;}}
}tree[maxn*4];
Segment_tree operator + (Segment_tree x,Segment_tree y) {Segment_tree z;z.l=x.l;z.r=y.r;z.dp[0][0]=min(x.dp[0][0]+y.dp[0][0],x.dp[0][1]+y.dp[1][0]);z.dp[0][1]=min(x.dp[0][0]+y.dp[0][1],x.dp[0][1]+y.dp[1][1]);z.dp[1][0]=min(x.dp[1][0]+y.dp[0][0],x.dp[1][1]+y.dp[1][0]);z.dp[1][1]=min(x.dp[1][0]+y.dp[0][1],x.dp[1][1]+y.dp[1][1]);return z;
}
int n,m;int a[maxn];
void pushup(int rt) {tree[rt]=tree[ls]+tree[rs];
}
void build(int l,int r,int rt) {tree[rt].l=l;tree[rt].r=r;if(l==r) {tree[rt].init(a[l]);return ;}int mid=(l+r)>>1;build(lson);build(rson);pushup(rt);
}
void update(int pos,int v,int rt) {if(tree[rt].l==pos&&tree[rt].r==pos) {tree[rt].init(v);return ;}int mid=(tree[rt].l+tree[rt].r)>>1;if(pos<=mid) update(pos,v,ls);else update(pos,v,rs);pushup(rt);
}
Segment_tree query(int l,int r,int rt) {if(tree[rt].l==l&&tree[rt].r==r) {return tree[rt];}int mid=(tree[rt].l+tree[rt].r)>>1;if(r<=mid) return query(l,r,ls);else if(l>mid) return query(l,r,rs);else return query(l,mid,ls)+query(mid+1,r,rs);
}
int main() {n=read();string s;cin>>s;m=read();for(int i=1;i<=s.length();i++) a[i]=s[i-1]-'0';build(root);for(int i=1;i<=m;i++) {int opt=read();if(opt==1) {int l=read(),r=read();printf("%d\n",query(l,r,1).dp[0][0]);}else {int x=read(),y=read();update(x,y,1);}}return 0;
}