6/3~6/7 PS

과제때문에 쉬엄쉬엄 풀었다. 곧 시험이기도 한데, 공부는 안 할 예정

 

 

 

BOJ 21607 - Polynomial and Easy Queries

\(f\)와 \(g\)를 왜 굳이 저걸 준 것인지를 생각하며 노트에서 놀다보면, \(f(g(x)) = g(f(x))\)임을 알 수 있다. 자신에 대해 f, g를 합성했을 때의 값을 각각 sparse table에 저장하고, update쿼리에서는 뿌려진 f와 g를 레이지 세그로 각각 저장하면 된다.

 

BOJ 17353 - 하늘에서 떨어지는 1, 2, ..., R-L+1개의 별

\(B_i = A_i - A_{i-1}\)이라고 정의하면, B에서 구간 \([l, r]\)에 1을 더해주고, \(B_{r+1}\)에는 구간의 크기를 빼주면 된다. 그리고 \(A_k\)는 \(B\)에서 구간 \([1, k]\)의 합이므로, 간단하게 풀 수 있다.

 

BOJ 13549 - 숨바꼭질 3

다익스트라 기초문제.

 

BOJ 5012 - 불만 정렬 (P4)

inversion의 경우의 수를 구하는 문제는 웰논이니 설명을 생략하겠다. 왼쪽에서 inversion의 개수를 구하고 이를 저장해둔 다음에, 오른쪽에서 inversion의 개수를 구하면서 해당 인덱스에 저장해둔 값을 곱해주면 된다.

 

BOJ 17409 - 증가 수열의 개수 (P4)

dp[i][j] = (i번째에서 길이가 j인 증가 수열의 개수)라고 정의하고 풀면 된다. 세그트리를 사용하는 dp이다.

 

BOJ 13555 - 증가하는 부분 수열 (P3)

notorious coincidence (=17409) 근데 17409는 세그로 풀고 이건 팬윅으로 했다.

 

BOJ 15840 - LCA와 쿼리 (P2)

1을 루트로 했을 때 r의 위치(u와 깊이를 비교하는 등)에 따라 몇 가지 경우가 생긴다. 근데 이걸 굳이 케이스 워크로 할 필요가 없다. r, u, v에서 두 정점의 lca들을 모두 구해주고, 이 lca들 중 깊이가 가장 깊은 정점이 답이 된다.