A10705. New Year and Old Subsequence
编程题
普及/提高-
知识点
题目描述
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 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.
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".
- 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".