302983: CF580E. Kefa and Watch
Memory Limit:256 MB
Time Limit:1 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
Kefa and Watch
题意翻译
长度为 $n$ 的字符串,每个字符是 $\mathtt{0} \sim \mathtt{9}$ 的数位,$m + k$ 种操作: 1. 格式为 `1 l r c`,表示将 $l \sim r$ 赋值为 $c$,保证 $0 \le c \le 9$。这种修改操作恰好 $m$ 个。 2. 格式为 `2 l r d`,表示询问 $l \sim r$ 是否有长度为 $d$ 的循环节。这种询问操作恰好 $k$ 个。 数据范围:$n \leqslant 10^5$,$m + k \leqslant 10^5$,$0 \leqslant c \leqslant 10$,$1 \leqslant d \leqslant r - l + 1$。 Translated by @attack题目描述
One day Kefa the parrot was walking down the street as he was on the way home from the restaurant when he saw something glittering by the road. As he came nearer he understood that it was a watch. He decided to take it to the pawnbroker to earn some money. The pawnbroker said that each watch contains a serial number represented by a string of digits from $ 0 $ to $ 9 $ , and the more quality checks this number passes, the higher is the value of the watch. The check is defined by three positive integers $ l $ , $ r $ and $ d $ . The watches pass a check if a substring of the serial number from $ l $ to $ r $ has period $ d $ . Sometimes the pawnbroker gets distracted and Kefa changes in some substring of the serial number all digits to $ c $ in order to increase profit from the watch. The seller has a lot of things to do to begin with and with Kefa messing about, he gave you a task: to write a program that determines the value of the watch. Let us remind you that number $ x $ is called a period of string $ s $ ( $ 1<=x<=|s| $ ), if $ s_{i}=s_{i+x} $ for all $ i $ from 1 to $ |s|-x $ .输入输出格式
输入格式
The first line of the input contains three positive integers $ n $ , $ m $ and $ k $ ( $ 1<=n<=10^{5} $ , $ 1<=m+k<=10^{5} $ ) — the length of the serial number, the number of change made by Kefa and the number of quality checks. The second line contains a serial number consisting of $ n $ digits. Then $ m+k $ lines follow, containing either checks or changes. The changes are given as 1 $ l $ $ r $ $ c $ ( $ 1<=l<=r<=n $ , $ 0<=c<=9 $ ). That means that Kefa changed all the digits from the $ l $ -th to the $ r $ -th to be $ c $ . The checks are given as 2 $ l $ $ r $ $ d $ ( $ 1<=l<=r<=n $ , $ 1<=d<=r-l+1 $ ).
输出格式
For each check on a single line print "YES" if the watch passed it, otherwise print "NO".
输入输出样例
输入样例 #1
3 1 2
112
2 2 3 1
1 1 3 8
2 1 2 1
输出样例 #1
NO
YES
输入样例 #2
6 2 3
334934
2 2 5 2
1 4 4 3
2 1 6 3
1 2 3 8
2 3 6 1
输出样例 #2
NO
YES
NO