티스토리 뷰
대회는 말렸습니다. 기존처럼 2시간 동안 문제를 보면서 풀이 2개와 유사풀이 2개를 생각했는데, 1번 2번을 푼 뒤 3번과 5번의 유사풀이를 구현하고 실패하다 보니 어느새 시간이 거의 끝나 있었습니다.
1번: 트리의 경로 a,b에 있는 간선들에 1을 추가해야 하는 쿼리가 주어지는데, 트리를 적절히 만들어서 모든 간선의 값이 짝수가 되게 하도록 해야 합니다. 쿼리들을 간선으로 표현했을 때, 모든 정점의 degree가 짝수이면 됩니다. 홀수인 경우가 있으면 정점에서 뻗어나가는 간선들 중에 어느 하나는 홀수여야 하고, 그런 경우가 없으면 잘 만들어 줄 수 있다.
2번: 어떤 수열의 부분수열 중 모든 원소가 K 이하인 것의 개수를 구하는 쿼리를 여러 번 해야 한다. 이는 유니온 파인드를 사용해 해결할 수 있다. 수열의 원소들을 크기 순서대로 보면서 유니온 파인드에 넣어주고, 각 집합들의 크기*(크기+1)/2을 관리해주면 된다.
3번: 업데이트되는 수열에서 1~K까지의 수가 모두 들어가는 최소 길이의 부분순열을 찾는 문제다. 단순한 스위핑 풀이 위주로 생각한 나머지, 세그먼트 트리 쪽으로는 생각을 많이 안 해봤지만, 정해는 세그먼트 트리였다. 세그먼트 트리의 각 노드에서 각 숫자가 나오는 가장 왼쪽 위치, 가장 오른쪽 위치를 저장한 뒤, 합칠 때는 왼쪽 노드의 가장 오른쪽 위치와 오른쪽 노드의 가장 왼쪽 위치를 사용해준다. 이 위치들을 정렬해준 다음 투 포인터 식으로 해주면 원하는 시간복잡도를 맞출 수 있지만, 상수 커팅이 필요할 수도 있다. 가장 왼쪽 위치와 오른쪽 위치도 새로 만들어야 하는데, 가장 왼쪽 위치는 왼쪽 노드에서 그대로 가져오되 없으면 오른쪽 노드에서 가져오면 된다.
4번과 5번 풀이는 업솔빙 한 뒤에 적겠습니다.
5번: 수열에서 구간 K개를 골라서 구간의 합집합에 모든 원소가 포함되게 하고, 구간 내부의 있는 원소들의 합의 합을 최대화해야 하는 문제이다. 이는 Alien trick을 사용해서 풀 수 있다. 구간 K개를 고른다는 조건을 없애고, 구간을 고를 때 구간의 합을 답에 더하는 대신 구간의 합 + 람다를 더하도록 하자. 이 상황에서의 최댓값은 구간 합+람다가 0 이상인 모든 구간을 포함시킨 뒤(이는 세그먼트 트리로 할 수 있습니다), 그 구간들에 하나도 포함이 되지 않은 원소들을 dp로 커버해 주면 됩니다. a~b까지를 커버할 때의 dp 식은 dp[b]=dp[a-1]+a 왼쪽의 원소들 중 구간에 포함된 원소들 중 가장 오른쪽 몇 개의 합 중 최댓값+b 오른쪽의 원소들 중 구간에 포함된 원소들 중 가장 오른쪽 몇 개의 합 중 최댓값+람다입니다+a~b까지의 원소들의 합입니다. 이는 a<=b 중 dp[a-1]+a 왼쪽의 원소들 중 구간에 포함된 원소들 중 가장 오른쪽 몇 개의 합 중 최댓값+a부터 N-1까지의 합들의 최댓값을 저장해 주면 O(N)에 할 수 있습니다.
에일리언 트릭에 반정수를 사용하는 부분, a 왼쪽의 원소들 중 구간에 포함된 원소들 중 가장 오른쪽 몇 개의 합 중 최댓값을 구하는 부분 등 구현에서 생각할 부분이 많았습니다.
그리고 오버플로우가 났는데, 롱 롱 범위 내로 할 수 있을 방법이 있을 것 같지만 더 편한 방법인 int128을 썼습니다.