레이팅 미적용*참고: 이 문제의 시간 제한은 기본의 2배인 4초이다. 메모리 제한은 기본의 2배인 512MB이다.*
파레이돌리아(Pareidolia)는 실제로는 존재하지 않는 익숙한 패턴을 이미지에서 보게 되는 현상이다. 예를 들어 구름에서 얼굴을 보는 것이다. 짐작할 수 있듯이, 농부 존은 항상 소들 곁에 있다 보니 일상 사물에서 소와 관련된 패턴을 자주 본다. 예를 들어 문자열 "bqessiyexbesszieb"를 보면, 농부 존의 눈은 일부 글자를 무시하고 "bessiebessie"만 보게 된다.
문자열 \(s\)가 주어질 때, \(s\)에서 0개 이상의 문자를 삭제하여 만들 수 있는 "bessie"의 최대 반복 횟수를 \(B(s)\)라 하자. 위 예시에서 \(B(\)"bqessiyexbesszieb"\() = 2\)이다. 나아가, 문자열 \(t\)가 주어질 때, \(t\)의 모든 연속 부분 문자열 \(s\)에 대한 \(B(s)\)의 합을 \(A(t)\)라 하자.
농부 존은 a-z 문자로만 이루어진 길이 \(2\cdot 10^5\) 이하의 문자열 \(t\)를 가지고 있다. \(A(t)\)를 계산하고, 각각 \(t\)의 문자 하나를 바꾸는 \(U\) (\(1\le U\le 2\cdot 10^5\))번의 갱신 후에 \(A(t)\)가 어떻게 변하는지 계산하라. 갱신은 누적된다.
출제자: Brandon Wang, Benjamin Qi
배점
- 입력 2: \(|t|, U\le 300\)
- 입력 3-5: \(U\le 10\)
- 입력 6-13: \(|t|, U\le 10^5\)
- 입력 14-21: 추가 제약 조건이 없다.
출제자: Brandon Wang, Benjamin Qi
입력의 첫째 줄에 \(t\)가 주어진다.
다음 줄에 \(U\)가 주어지고, 이어서 \(U\)개의 줄에 각각 위치 \(p\) (\(1\le p\le N\))와 a-z 범위의 문자 \(c\)가 주어지며, 이는 \(t\)의 \(p\)번째 문자가 \(c\)로 바뀜을 의미한다.
\(U+1\)개의 줄에, 갱신 전과 각 갱신 후에 \(t\)의 모든 부분 문자열에 걸쳐 만들 수 있는 bessie의 총 개수를 출력한다.
bessiebessie
3
3 l
7 s
3 s14
7
1
7Before any updates, twelve substrings contain exactly 1 "bessie" and 1 string
contains exactly 2 "bessie"s, so the total number of bessies is
\(12\cdot 1 + 1 \cdot 2 = 14\).
After one update, \(t\) is "belsiebessie." Seven substrings contain exactly one
"bessie."
After two updates, \(t\) is "belsiesessie." Only the entire string contains
"bessie."
riseoj 작성
출처 올림피아드 > USACO > 2022-2023 > US Open > Platinum