题意：给一个字符串，每次询问它的一个区间，问最少删除多少个字符，使得区间没有子序列 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\)。跑的很快。