CF750E New Year and Old Subsequence

• 25通过
• 34提交
• 题目来源
• 评测方式 RemoteJudge
• 标签
• 难度 省选/NOI-
• 时空限制 3000ms / 256MB
• 提示：收藏到任务计划后，可在首页查看。

题目描述

定义一个数字串满足性质$nice$当且仅当：该串包含子串$2017$，且不包含子串$2016$。

定义一个数字串的函数$ugliness$为：该串至少删去几个字符，可以使得剩余串满足性质$nice$；如果该串没有满足性质$nice$的子串，则该串的$ugliness$是$-1$。

给定一个长度为$n$的字符串$t$，和$q$次询问，每次询问用$(l,r)$表示。对于每次询问，回答$ugliness(t[l,r])$。

输入输出格式

输入格式：

第一行输入两个整数$n,q$ ，其中$n$是字符串$s$的长度，$q$是询问的个数。

第二行输入完全由十进制数字组成的字符串$s$。

接下来的$n$行，每行输入两个整数$l,r$，描述一个询问。

输出格式：

对于每个询问，输出一行答案。

数据范围：

$$4 \leq n \leq 200000,1 \leq q \leq 200000,1 \leq l \leq r \leq n$$

题目描述

A string $t$ is called nice if a string "2017" occurs in $t$ as a subsequence but a string "2016" doesn't occur in $t$ as a subsequence. For example, strings "203434107" and "9220617" are nice, while strings "20016", "1234" and "20167" aren't nice.

The ugliness of a string is the minimum possible number of characters to remove, in order to obtain a nice string. If it's impossible to make a string nice by removing characters, its ugliness is $-1$ .

Limak has a string $s$ of length $n$ , with characters indexed $1$ through $n$ . He asks you $q$ queries. In the $i$ -th query you should compute and print the ugliness of a substring (continuous subsequence) of $s$ starting at the index $a_{i}$ and ending at the index $b_{i}$ (inclusive).

输入输出格式

输入格式：

The first line of the input contains two integers $n$ and $q$ ( $4<=n<=200000$ , $1<=q<=200000$ ) — the length of the string $s$ and the number of queries respectively.

The second line contains a string $s$ of length $n$ . Every character is one of digits '0'–'9'.

The $i$ -th of next $q$ lines contains two integers $a_{i}$ and $b_{i}$ ( $1<=a_{i}<=b_{i}<=n$ ), describing a substring in the $i$ -th query.

输出格式：

For each query print the ugliness of the given substring.

输入输出样例

输入样例#1： 复制
8 3
20166766
1 8
1 7
2 8

输出样例#1： 复制
4
3
-1

输入样例#2： 复制
15 5
012016662091670
3 4
1 14
4 15
1 13
10 15

输出样例#2： 复制
-1
2
1
-1
-1

输入样例#3： 复制
4 2
1234
2 4
1 2

输出样例#3： 复制
-1
-1


说明

In the first sample:

• In the first query, $ugliness($ "20166766" $)=4$ because all four sixes must be removed.
• In the second query, $ugliness($ "2016676" $)=3$ because all three sixes must be removed.
• In the third query, $ugliness($ "0166766" $)=-1$ because it's impossible to remove some digits to get a nice string.

In the second sample:

• In the second query, $ugliness($ "01201666209167" $)=2$ . It's optimal to remove the first digit '2' and the last digit '6', what gives a string "010166620917", which is nice.
• In the third query, $ugliness($ "016662091670" $)=1$ . It's optimal to remove the last digit '6', what gives a nice string "01666209170".
提示
标程仅供做题后或实在无思路时参考。
请自觉、自律地使用该功能并请对自己的学习负责。
如果发现恶意抄袭标程，将按照I类违反进行处理。