题意：
类似上一题，给定一个长度2e5的字符串，2e5个询问，每次问从区间 [l,r] 里面最少删去多少而可以使得结果中存在2017但是不存在2016。这个是比较好的一道题，之前我从没来遇到过动态维护动态规划的。。。这叫什么，动态动态规划？（雾）
题解：
首先考虑简单版的问题，如果不考虑查询，单次做问整个序列最少去掉多少该怎么做？我当时是考虑了很多，但是如果按照正常的考虑方式的话就会越想越复杂，不知道该维护什么样的一个状态。该以什么作为状态呢？如果按照状压的思路会发现无法转移，因为他这个2016和2017都是有顺序的啊，不能状压搞，但是也不能把前面的所有情况搞出来，复杂度会爆炸。看了题解发现有人提正则表达式和有限状态机才明白了。。。之前做的那个题简单是因为他很好转移，是不包含当前前缀时最少需要删除多少，而这个题目的状态需要定义为包含当前状态机节点对应的前缀且不包含严格包含当前状态机节点对应的前缀最少需要删除多少个字符。。。意思就是20的时候不能有201和2017的时候的需要删除的最少字符。。
然后考虑状态的转移，这个有限状态机可以匹配出来2017，但是匹配出来之后呢？我们应该拒绝掉所有的2016，注意这时候，从状态2017和201都可以转移到2016，所以我们当前如果已经匹配完且达到2017/201的时候，转移回到本身都需要多删掉一个字符，也就是本身。。。其他情况是如果要往下一个节点走的时候，回到自身的代价是1，往下走的代价是0.。。其实也就是一个选择，选择当前的这个字符留还是不留，，，，跟谁匹配的话比较好。。
然后他很妙的一点就是这个转移可以写成矩阵的形式，当然这不是一个矩阵乘法，是一个很怪的操作，类似Floyd最短路的方法，然后这个矩阵操作是满足结合律的（我也不知道为什么满足结合律）。。。。就可以用线段树维护了。。。
甚至说这个题甚至可以改成带修的。。
#include <bits/stdc++.h>
using namespace std;
const int maxn = 200020;
const int inf = 1e9;
struct node
{
int a[5][5];
node operator + ( const node b ) const
{
node c;
for( int i = 0 ; i < 5 ; i++ )
for( int j = 0 ; j < 5 ; j++ )
{
c.a[ i ][ j ] = inf;
for( int k = 0 ; k < 5 ; k++ )
c.a[ i ][ j ] = min( c.a[ i ][ j ], a[ i ][ k ] + b.a[ k ][ j ] );
}
return c;
}
}e[maxn << 2];
char s[maxn];
int n, Q;
void build(int x, int l, int r)
{
if( l == r )
{
for( int i = 0 ; i < 5 ; i++ )
for( int j = 0 ; j < 5 ; j++ )
e[ x ].a[ i ][ j ] = ( i == j ) ? 0 : 1e9;
if( s[ l ] == '2' )
{
e[ x ].a[ 0 ][ 0 ] = 1;
e[ x ].a[ 0 ][ 1 ] = 0;
}
else if( s[ l ] == '0' )
{
e[ x ].a[ 1 ][ 1 ] = 1;
e[ x ].a[ 1 ][ 2 ] = 0;
}
else if( s[ l ] == '1' )
{
e[ x ].a[ 2 ][ 2 ] = 1;
e[ x ].a[ 2 ][ 3 ] = 0;
}
else if( s[ l ] == '7' )
{
e[ x ].a[ 3 ][ 3 ] = 1;
e[ x ].a[ 3 ][ 4 ] = 0;
}
else if( s[ l ] == '6' )
{
e[ x ].a[ 3 ][ 3 ] = 1;
e[ x ].a[ 4 ][ 4 ] = 1;
}
return ;
}
int mid = l + r >> 1;
build( x << 1, l, mid );
build( x << 1 | 1, mid + 1, r );
e[ x ] = e[ x << 1 ] + e[ x << 1 | 1 ];
}
node query(int x, int l, int r, int ql, int qr)
{
if( l == ql && r == qr )
return e[ x ];
int mid = l + r >> 1;
if( qr <= mid ) return query( x << 1, l, mid, ql, qr );
if( ql > mid ) return query( x << 1 | 1, mid + 1, r, ql, qr );
return query( x << 1, l, mid, ql, mid ) + query( x << 1 | 1, mid + 1, r, mid + 1, qr );
}
int main()
{
scanf( "%d%d%s", &n, &Q, s + 1 );
build( 1, 1, n );
while( Q-- )
{
int l, r;
scanf( "%d%d", &l, &r );
node sss=query( 1, 1, n, l, r );
int ans = query( 1, 1, n, l, r ).a[ 0 ][ 4 ];
if( ans == inf )
printf( "-1\n" );
else
printf( "%d\n", ans );
}
}
/*
a[i][j] the cost of transition from state_i to state_j
11 100
22017720172
1 5
1 0 1000000000 1000000000 1000000000
1000000000 0 1000000000 1000000000 1000000000
1000000000 1000000000 0 1000000000 1000000000
1000000000 1000000000 1000000000 0 1000000000
1000000000 1000000000 1000000000 1000000000 0
2 0 1000000000 1000000000 1000000000
1000000000 0 1000000000 1000000000 1000000000
1000000000 1000000000 0 1000000000 1000000000
1000000000 1000000000 1000000000 0 1000000000
1000000000 1000000000 1000000000 1000000000 0
2 1 0 1000000000 1000000000
1000000000 1 0 1000000000 1000000000
1000000000 1000000000 0 1000000000 1000000000
1000000000 1000000000 1000000000 0 1000000000
1000000000 1000000000 1000000000 1000000000 0
2 1 1 0 1000000000
1000000000 1 1 0 1000000000
1000000000 1000000000 1 0 1000000000
1000000000 1000000000 1000000000 0 1000000000
1000000000 1000000000 1000000000 1000000000 0
2 1 1 1 0
1000000000 1 1 1 0
1000000000 1000000000 1 1 0
1000000000 1000000000 1000000000 1 0
1000000000 1000000000 1000000000 1000000000 0
2 1 1 2 0
1000000000 1 1 2 0
1000000000 1000000000 1 2 0
1000000000 1000000000 1000000000 2 0
1000000000 1000000000 1000000000 1000000000 0
3 1 1 2 0
1000000000 1 1 2 0
1000000000 1000000000 1 2 0
1000000000 1000000000 1000000000 2 0
1000000000 1000000000 1000000000 1000000000 0
3 2 1 2 0
1000000000 2 1 2 0
1000000000 1000000000 1 2 0
1000000000 1000000000 1000000000 2 0
1000000000 1000000000 1000000000 1000000000 0
3 2 2 1 0
1000000000 2 2 1 0
1000000000 1000000000 2 1 0
1000000000 1000000000 1000000000 2 0
1000000000 1000000000 1000000000 1000000000 0
3 2 2 2 0
1000000000 2 2 2 0
1000000000 1000000000 2 2 0
1000000000 1000000000 1000000000 3 0
1000000000 1000000000 1000000000 1000000000 0
*/