unordered_map이 PS하는 블로그

수열과 쿼리 0과 수열과 쿼리 4와 같은 문제이다. 정확히는 수열과 쿼리 0에서 mod K만 씌우면 된다. 수열과 쿼리 0의 풀이 링크로 이 문제의 풀이를 대체한다. https://unorderedmap.tistory.com/34 수열과 쿼리 0 [BOJ 13545] 수열과 쿼리 4와 수열과 쿼리 7과 같은 문제이다. 수열과 쿼리 4가 가장 기본형 문제이므로 수열과 쿼리 4를 풀면 이 문제도 자연스럽게 풀린다. 수열과 쿼리 4의 풀이 링크는 아래에 있다. https://u unorderedmap.tistory.com 코드 더보기 #include #define SIZE 100003 typedef long long ll; using namespace std; struct Query { int id, s, e..

수열과 쿼리 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 ..

수열과 쿼리 18과 완전히 같은 문제이다. 아래 링크에는 수열과 쿼리 18에 대한 설명이 있다. https://unorderedmap.tistory.com/27 수열과 쿼리 18 [BOJ 14504] 수열과 쿼리 3 문제는 머지 소트 트리를 이용해 해결할 수 있다. 아직 안 풀어봤다면 수열과 쿼리 3을 꼭 먼저 풀고, 수열과 쿼리 18에서 업데이트 쿼리를 어떻게 적용할 수 있을지 생각해보자. 여 unorderedmap.tistory.com

실버도 문제다! 문제 요약 처음에 0이 하나 포함되어있는 배열 A에서 다음 4가지 쿼리를 수행한다. 1 x : 수열 맨 뒤에 x 추가 2 x : 수열에서 가장 앞에 있는 x 하나 제거 3 : 수열 원소 합 출력 4 : 수열 원소 XOR 출력 사용 알고리즘 없음 풀이 XOR의 성질에 따라 a^b^c^...^z에서 a^b^c^...^y를 구하고 싶으면 (a^b^c^...^z)^z를 하면 된다. XOR은 교환법칙과 결합법칙이 모두 성립하기 때문이다. 따라서 1, 2번 연산을 하면서 수열 원소 합/수열 원소 XOR을 관리해줄 수 있고, 출력만 하면 된다. 1번 쿼리에서 '맨 뒤에 추가', 2번 쿼리에서 '가장 앞에 있는 것 하나 제거'와 같은 내용은 문제를 거창하게 만들기 위한 도구이니 가볍게 무시해주자. 코드..

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

수열과 쿼리 3 문제는 머지 소트 트리를 이용해 해결할 수 있다. 아직 안 풀어봤다면 수열과 쿼리 3을 꼭 먼저 풀고, 수열과 쿼리 18에서 업데이트 쿼리를 어떻게 적용할 수 있을지 생각해보자. 여담으로, 이 문제는 수열과 쿼리 1.5와 완전히 같은 문제이다. 문제 요약 길이 10만 이하의 수열 A에서 다음 2가지 쿼리를 수행한다. 1 i j k : 구간 [i, j]에서 A의 원소 중 k보다 큰 것의 개수를 출력 2 i k : A[i]=k로 업데이트 사용 알고리즘 제곱근 분할법 풀이 k보다 큰 원소의 수를 lower_bound나 upper_bound를 이용하여 구하겠다는 발상까지는 머지 소트 트리와 같다. 하지만 업데이트 쿼리가 들어온다면 기존의 머지 소트 트리에서 O(logN)개의 정렬된 vector를..

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