골랜디.
배열을 좌표 기준으로 정렬하고, 각 쿼리마다 이분 탐색을 통해 인덱스를 찾으면 된다. 누적 합을 사용해야 안 터짐
두 개씩 짝을 지을 수 있는 막대들을 긴 것부터 사각형을 만들면 된다.
홀수 짝수 인덱스 누적 합 배열을 각각 만들어 주고, upper_bound로 소수 배열의 인덱스 구간\(l\), \(r\)을 찾을 수 있다.
코포 1A로 잘 나올 것처럼 생긴 문제다. 작은 수는, 가장 오른쪽의 '10'을 찾아서 '01'로 바꾼 다음, 이 뒤쪽에 나오는 1들을 왼쪽으로 싹 몰아주면 된다. 큰 수는 반대로 하면 된다.
모음인 알파벳이 나오면, 문자열은 뒤집히게 된다. 굳이 식으로 쓰자면 \(S + a \rightarrow a + rev(S)\)인데, 여기에서 또 모음이 나오면, S는 다시 뒤집히게 된다. \(a + rev(S) + i \rightarrow i + S + a\) 즉, 모음이 앞, 뒤에 번갈아 붙는 것과 같다. 코너케이스에 유의하고, 초기의 '자음만 있는 문자열' S의 길이를 찾기만 하면 된다.
i가 구간 \([l, r]\)에 포함되어야 하므로, 가능한 멀리 뻗어나가면 된다. 왼쪽과 오른쪽 각각에 대해 이분 탐색을 해주면 된다. \(O(Nlg^2N)\)
Maximum Spanning Tree를 만들고, 아무 정점에서 dfs를 돌리면서 정점을 지우면? 된다
정방향으로, \(A_i < A_{i+1}\)인 경우에만 값을 변경해주고, 배열을 뒤집는다. 그러고 방금 한 것을 또 하면 된다.
위와 같으나, 이분 탐색이 추가된 문제이다.
'백준 문제풀이' 카테고리의 다른 글
| 7/22 ~ 7/27 PS (0) | 2022.07.27 |
|---|---|
| 7/19 ~ 7/21 PS (0) | 2022.07.22 |
| 7/1 ~ 7/8 PS (0) | 2022.07.08 |
| 백준 25213 - 조각 케이크 (Hard) [C++] (0) | 2022.07.05 |
| 6/27 ~ 6/30 PS (2) | 2022.06.30 |