풀이를 아는 문제만 적었습니다. 정확하지 않을 수 있습니다.
A: 길이 5의 path는 임의로 재정렬할 수 있다. 그리고 많은 경우에 정점 6개의 트리는 일자형 트리로 변환할 수 있다. 트리의 지름을 4로 만든 후에 다양한 변환을 거치면 된다.
B: 1번째 원소는 i=1인 경우로만 변경할 수 있다. p[1]을 맞춘 후에 2번째 원소, 3번째 원소도 순차적으로 맞춰보자.
C: 현재 R칸에 있다고 가정하자. 오른쪽 K개의 칸을 모두 탐색하지 않고 가장 가까이 있는 오른쪽의 R까지만 탐색해도 된다. TL이 빡세다.
E: heavy edge가 바뀌는 횟수가 bound된다. 이유는 hld와 같은 원리로 설명 가능하다. hld와 lazy segment tree로 적용하면 (N+Q)log^2N에 풀린다.
F: 1~i까지가 1부터 i까지로 이루어져 있는 경우가 없는 것이 irreducible permutation이다. 1<=i<n인 모든 i에 대해서 해당 경우의 개수를 세주면 답이다.
G: 45도 좌표를 돌리자. 맨해튼 거리에서 원은 정사각형으로 나타난다. 세 점이 monotone하게 있지 않다면 항상 지나는 정사각형이 존재한다. 세그스위핑으로 해결 가능
I: x는 2^k-1의 꼴이다.
J: 사용하는 간선의 개수를 관찰로 줄이는 문제이다. 세그먼트 트리 적용하는 문제가 아니다.
K: S에 있는 원소중 (는 앞에 오고 )는 뒤에 오도록 스왑하는 것이 최선이다. 바뀌는 괄호문자열을 봤을 때 어떤 지점을 기준으로 왼쪽의 )는 (로 바뀌고 오른쪽의 (는 )로 바뀐다. [1, i] 중 j개의 )를 골라서 (로 바꿨을 때 올바른 괄호열의 prefix가 되는 경우를 dp로 구해주고 반대쪽 suffix도 마찬가지로 해준 뒤에 적절히 하면 된다. 괄호열이 올바른 괄호문자열인 경우에는 2^2n-1이 답임을 주의하자.