A (2:55)
일 때와 일 때를 잘 나눠서 처리해주면 된다.
B (5:27)
를 계속 곱해주면서 보다 커지면 1로 바꿔주면 된다. 오버플로우가 날 수 있으므로 조심해서 구현해야 한다. 귀찮아서 그냥 int128로 때웠다.
C (38:46, -2)
10분 동안 라는 조건을 못 봤어서 삽질을 했다. 떠오르는게 없어서 먼저 D를 풀었다.
이 문제는 증가 -> 감소 -> 증가하는 수열의 길이의 개수를 구하는 문제인데 감소하는 부분의 정보는 필요가 없고, 증가하는 부분의 정보만 필요하다.
증가하는 부분의 길이만 배열에 담은 뒤, 시작하는 부분과 끝 부분에 남은 길이만큼 부분 수열이 생기기 때문에 연속적인 값들의 곱을 더해주면 답이 나온다.
D (20:08)
좌표와 좌표에 해당하는 값들을 set으로 보관하면서 쿼리가 들어올 때마다 set의 크기를 출력하고 전부 삭제해주면 된다.
삭제 할 때 각 좌표의 반대의 값들도 동시에 제거해야 한다.
F (57:32)
우선 문제에서 중간에 업데이트 쿼리가 주어지기 때문에 세그먼트 트리 문제라고 생각을 했다. 트리에서 세그먼트 트리를 사용하기 위해서는 HLD 또는 오일러 투어 테크닉을 사용해야 한다.
트리를 쪼개는 쿼리를 보면 항상 서브트리 형태로 쪼개지는 것을 볼 수 있다. 이는 오일러 투어 테크닉과 세그먼트 트리로 서브 트리의 합을 빠르게 구할 수 있다.
전체 트리의 합에서 서브 트리의 합을 구하면 나머지 값들도 알 수 있기 때문에 둘의 차를 구해서 정답을 구할 수 있다.
