CF750E - New Year and Old Subsequence

题意：给一个字符串，每次询问它的一个区间，问最少删除多少个字符，使得区间没有子序列 2016，但是有子序列 2017。

My solution

首先考虑贪心，通过预处理的方式找到区间最后一个 7，依次往前贪心的找到最靠后的一组 2017。接下来，我们需要 7 的后面没有 6，7 前面的部分不能组合出 2016。

我们先考虑区间 \(dp\)，设 \(dp_{l,r,L,R}\) 是对于原序列的区间 \([l,r]\)，不能出现 2016 的子区间 \([L,R]\) 作为子序列的最小删除次数。

我们发现，这个可以通过 \(4^3\) 的合并在线段树上维护。因为合并两个相邻区间的时候，我们只需要枚举 \([L,R]\) 的间断点 \(t\)，\([L,t]\) 和 \([t,R]\) 分别不在两边出现即可。我们可以互推来说明两者是等价的。

然后，我们通过四次查询查到我们找到的这组 2016 之间的位置。然后我们发现第四组可以直接删掉，因为这里一个 6 也不能有，我们只需要合并前三组。

而前三组合并的硬性条件是我们选定的 20 不能被删掉，也就意味着，想要 0 和 0 的后面不能出现 016，等价于不能出现 16，没有 01 等价于没有 1。我们把 \(dp\) 重新更新一下然后合并就可以得到正确答案了。

复杂度是 \(O(4^3 (n+q)\log n)\)。但是有四次查询，跑得很慢。

string s;
int n,q,a[200005],L,R;
int lst[200005][10];
struct imfo{
	int dp[4][4];
	imfo(){
		rd(l,4)rep(r,l,3)dp[l][r]=1e9;
	}
	imfo(int imherecnmdjbdxcnmnmzlnmsl){
		rd(l,4)rep(r,l,3){
			dp[l][r]=0*imherecnmdjbdxcnmnmzlnmsl;
		}
	}
	imfo operator +(const imfo b)const{
		imfo res;
		rd(l,4)rep(r,l,3)rep(t,l,r){
			res.dp[l][r]=min(res.dp[l][r],dp[l][t]+b.dp[t][r]);
		}return res;
	}
}I(114514);
 
struct node{
	int l,r;
	imfo s;
}sg[800005];
inline void init(int i,int l,int r){
	sg[i].l=l,sg[i].r=r;
	if(l==r){
		sg[i].s=I;
		if(a[l]==6)sg[i].s.dp[3][3]=1;
		if(a[l]==1)sg[i].s.dp[2][2]=1;
		if(a[l]==0)sg[i].s.dp[1][1]=1;
		if(a[l]==2)sg[i].s.dp[0][0]=1;
		return;
	}
	init(i<<1,l,(l+r)>>1);
	init(i<<1|1,((l+r)>>1)+1,r);
	sg[i].s=sg[i<<1].s+sg[i<<1|1].s;
}
inline imfo query(int i,int l,int r){
	if(sg[i].l>r||sg[i].r<l)return I;
	if(sg[i].l>=l&&sg[i].r<=r)return sg[i].s;
	return query(i<<1,l,r)+query(i<<1|1,l,r);
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>n>>q>>s;
	s='$'+s;
	rp(i,n)a[i]=s[i]-'0';
	rp(i,n){
		rd(j,10)lst[i][j]=lst[i-1][j];
		lst[i][a[i]]=i;
	}init(1,1,n);
	rp(_,q){
		cin>>L>>R;
		int a7=lst[R][7],a1=lst[a7][1],a0=lst[a1][0],a2=lst[a0][2];
		if(a2<L){
			cout<<-1<<endl;
			continue;
		}
		imfo a=query(1,a1+1,R),b=query(1,a0+1,a1-1),c=query(1,a2+1,a0-1),d=query(1,L,a2-1);
		ll ans=a.dp[3][3];
		b.dp[1][3]=b.dp[2][3];
		b.dp[1][2]=b.dp[2][2];
		b.dp[1][1]=1e9;
		c.dp[0][3]=c.dp[1][3];
		c.dp[0][2]=c.dp[1][2];
		c.dp[0][1]=c.dp[1][1];
		c.dp[0][0]=1e9;
		imfo res=d+c+b;
		cout<<ans+res.dp[0][3]<<endl;
	}
	return 0;
}
//Crayan_r

rng_58's solution

对于上面的做法，我们重新设计状态，我们把 7 也加入进要判断的区间里面。但是 \(dp\) 状态就不是简单的“不能出现”，而是“满足要求”。也就是，凡是有 xx76 的状态，都是“保留 xx7 而消去 xx6”。

对于这个状态，我们同样可以通过原先的转移式转移。因为我们可以把转移拆成 6 的转移和 7 的转移，分开论证的话就可以很容易发现是等价的。

然后我们只需要对 \([l,r]\) 进行一次查询就可以得到满足要求的答案。复杂度 \(O(5^3(n+q)\log n)\)，但是信息合并部分的常数非常小，因为本质上是一个区间 \(dp\)。跑的很快。

Code by rng_58