unordered_map이 PS하는 블로그

수열과 쿼리 4와 수열과 쿼리 7과 같은 문제이다. 수열과 쿼리 4가 가장 기본형 문제이므로 수열과 쿼리 4를 풀면 이 문제도 자연스럽게 풀린다. 수열과 쿼리 4의 풀이 링크는 아래에 있다. https://unorderedmap.tistory.com/33 수열과 쿼리 4 [BOJ 13546] 수열과 쿼리 0과 수열과 쿼리 7과 같은 문제인데, 이 문제가 가장 기본형인 것 같다. 수열과 쿼리 6의 응용 버전이기도 하다. 이 문제의 풀이를 모르겠다면 수열과 쿼리 6을 먼저 풀어보기 바란다. unorderedmap.tistory.com 문제 요약 1과 -1로만 이루어진 길이 10만 이하의 수열 A에서 다음 쿼리를 수행한다. i j : 구간 [i, j]에 포함되는 구간 중 구간합이 0인 가장 긴 구간의 길이 출..

수열과 쿼리 0과 수열과 쿼리 7과 같은 문제인데, 이 문제가 가장 기본형인 것 같다. 수열과 쿼리 6의 응용 버전이기도 하다. 이 문제의 풀이를 모르겠다면 수열과 쿼리 6을 먼저 풀어보기 바란다. 아래는 수열과 쿼리 6 풀이 링크이다. https://unorderedmap.tistory.com/31 수열과 쿼리 6 [BOJ 13548] 티어가 하나 낮은 수열과 쿼리 5의 풀이를 확장한다. 수쿼 5를 아직 안 풀었다면 이 문제와 같이 푸는 것을 추천한다. 아래는 수열과 쿼리 5의 풀이가 담긴 링크이다. https://unorderedmap.tistory.com/28 unorderedmap.tistory.com 문제 요약 길이 10만 이하의 수열 A에서 다음 쿼리를 수행한다. (단, 수열의 각 원소는 10..

재밌는데 고려할게 많아서 조금 귀찮다. 처음 풀 때는 12번만에 맞았고, 다시 풀 때도 한 번 틀렸다. 디테일한 구현을 많이 해보지 않았다면 한 번에 AC를 받기에는 어려울 수도 있는 문제이기에 비슷한 난이도의 아이디어를 가진 문제들보다 더 높은 티어를 받은 것 같다. 문제 요약 길이 10만 이하의 수열 A와 100만 이하의 수 K에 대하여 다음 쿼리를 수행한다. l r : 구간 [l, r]에 포함되는 구간 [i, j] 중 A[i]^A[i+1]^...^A[j]=K인 구간의 수를 출력 사용 알고리즘 Mo's Algorithm 풀이 XOR의 성질에 따라 어떤 구간의 XOR 값은 누적 XOR을 통해 O(N)에 전처리하여 O(1)에 구할 수 있다. B[i]를 A[1]^...^A[i]라고 하면, A[i]^...^..

티어가 하나 낮은 수열과 쿼리 5의 풀이를 확장한다. 수쿼 5를 아직 안 풀었다면 이 문제와 같이 푸는 것을 추천한다. 아래는 수열과 쿼리 5의 풀이가 담긴 링크이다. https://unorderedmap.tistory.com/28 수열과 쿼리 5 [BOJ 13547] 서로 다른 수에 대한 쿼리를 다루는 문제 중 쉬운 문제로, 어려운 아이디어 없이도 해결할 수 있다. 이게 왜 P2일까...? 더 많은 풀이가 존재한다고 하는데, 필자의 풀이는 쉽다고 생각하여 P4를 기 unorderedmap.tistory.com 문제 요약 길이 10만 이하의 수열 A에 대해 다음 쿼리를 수행한다. i j : 구간 [i, j]에 가장 많이 등장하는 수가 몇 번 등장했는지 출력한다. 사용 알고리즘 Mo's Algorithm ..

서로 다른 수에 대한 쿼리를 다루는 문제 중 쉬운 문제로, 어려운 아이디어 없이도 해결할 수 있다. 이게 왜 P2일까...? 더 많은 풀이가 존재한다고 하는데, 필자의 풀이는 쉽다고 생각하여 P4를 기여했다. 풀고 난 뒤 다른 사람 코드를 보며 이 문제를 푸는 다른 방법에 대해 찾아보는 것도 재미있다. 문제 요약 길이 10만 이하의 수열 A에서 다음 쿼리를 수행한다. i j : 구간 [i, j]에 존재하는 서로 다른 수의 개수를 출력 사용 알고리즘 Mo's Algorithm 풀이 Mo's Algorithm을 사용하여 쿼리를 처리할 것이고, 새로운 배열 B[]와 변수 result를 관리할 것이다. B[i]는 해당 구간에 들어있는 숫자 i의 개수, result는 해당 구간에 들어있는 서로 다른 숫자의 개수이..

수열과 쿼리 8, 9와 함께 풀면 좋은 문제이다. 아직 안 풀었다면 함께 풀어보는 것을 추천한다. 문제 요약 길이 10만 이하의 수열 A에서 다음 쿼리를 수행한다. s e : 구간 [s, e]에 존재하는 iAj인 (i, j) 쌍의 수를 출력 사용 알고리즘 펜윅 트리 Mo's Algorithm 풀이 어떤 수열에 대해 쿼리 1 N을 처리해보자. 이를 처리하는 것은 어렵지 않다. 처음 원소부터 하나씩 세그먼트 트리에 넣으면서, 이미 들어간 원소 중 자신보다 큰 원소의 수를 쿼리로 세주면 된다. 시간복잡도는 O(NlogN)이다. 이를 통해 우리는 쿼리를 처리하기 위해서 어떤 구간의 모든 수를 담고 있는 세그먼트 트리가 있어야한다는 사실을 알 수 있다. 그렇다면 이를 Mo's Algorithm으로 쿼리와 쿼리 사..

Mo's Algorithm과 세그먼트 트리가 완전히 체화되어 있다면 쉽게 풀 수 있는 문제이지만, 그게 아니라면 아이디어를 떠올리기 조금 힘들다. 그래서 별 다른 아이디어 없이도 P1의 티어를 받은 것 같다. 문제 요약 길이 10만 이하의 수열 A에서 다음 쿼리를 수행한다. l r : 구간 [l, r]에 있는 i, j(i

이 문제는 내가 N달 동안 고민한 문제로, 자구충이라면 다4 수쿼 정도는 풀 수 있어야하지 않을까 싶어서 업솔빙도 안했다. 그리고 최근에 다시 고민을 하다가 문제를 푸는데에 핵심적인 아이디어를 떠올려 풀 수 있게 되었다. vector의 몇 안되는 다이아 이상 자력솔 중 하나이다. 문제 요약 길이 10만 이하의 수열 A, B에서 다음 쿼리를 수행한다. i j k : i