A × B (HARD)

각 칸에 현재 값이 존재하는지와, 존재한다면 그 값을 관리해야 한다.

구간의 최솟값과 최댓값을 함께 저장하는 세그먼트 트리를 사용한다. 비어 있는 구간은 별도의 상태로 나타낸다. 두 노드를 합칠 때 한쪽이 비어 있다면 다른 쪽을 그대로 사용하고, 양쪽 모두 비어 있지 않다면 최솟값끼리의 최솟값과 최댓값끼리의 최댓값을 저장한다.

1번 쿼리는 해당 위치의 리프를 값이 존재하는 상태로 갱신한다. 3번 쿼리는 해당 리프를 빈 상태로 갱신한다. 2번 쿼리는 구간 노드들을 합쳐 최솟값과 최댓값을 얻는다. 결과가 빈 상태라면 출력하지 않고, 그렇지 않다면 두 값을 곱해 출력한다.

값의 절댓값이 최대 $10^9$이므로 곱은 최대 $10^{18}$이다. 따라서 64비트 정수형을 사용해야 한다.

각 테스트 케이스의 시간 복잡도는 $O((N+M)\log N)$이고, 공간 복잡도는 $O(N)$이다.

Solution written by GPT5.6