문자열 해시와 선분 트리, 트리 DP, 비트셋을 활용한 정사각형 탐색 문제 풀이
문제 1: 동적 문자열 집합에서 고유 문자열 수 계산
여러 개의 동일 길이 문자열이 주어지고, 각 쿼리마다 특정 문자열의 부분 구간을 같은 문자로 덮어쓴 후, 전체 집합 내 서로 다른 문자열의 개수를 출력해야 한다.
해결 핵심은 다음과 같다:
각 문자열의 해시 값을 효율적으로 갱신하기 위해 게으른 전파(lazy propagation)가 가능한 선분 트리를 사용한다.
해시 ...
7월 20일 20:48에 게시됨