unordered_map이 PS하는 블로그

Lazy propagation을 여러 가지 쿼리를 통해 전파하는 경우 어떤 것을 먼저 전파할지 결정하는 것이 매우 중요하다. 하지만 이 문제에서는 3개의 쿼리가 어떤 하나의 쿼리의 일부가 된다. 이를 인지하면 구현량도 많이 줄일 수 있어 실수도 덜 나오고 빠르게 풀 수 있다. 그리고 이 문제가 D5가 박혀있지만 플래 기여가 상당히 많고, 이제 플래로 내려올 때가 된 것 같다. D5 티어에 쫄지 말고 아이디어를 잡기 위해 노력해보자. 문제 요약 길이 10만 이하의 수열 A에 대해 다음 4가지 쿼리를 수행한다. 1 x y v : 구간 [x, y]에 속한 모든 i에 대해 A[i]=(A[i]+v)%MOD 적용 2 x y v : 구간 [x, y]에 속한 모든 i에 대해 A[i]=(A[i]*v)%MOD 적용 3 x..

수쿼 스타일의 문제를 보다보면 특정 구간에 등차수열을 더하거나, 피보나치 수열을 더하는 등의 문제를 볼 수 있다. 이 문제를 통해 등차수열에 관한 쿼리는 어떻게 처리하는지 익혀보길 바란다. 그리고 다이아라고 되어있긴 한데 왜 다이아인지 전혀 모르겠다. 플1 정도가 적당해보이고, 사람에 따라 더 내려서 생각할 수도 있을 것 같다. 푸른색 티어에 겁먹지 말고 도전해보자. 문제 요약 길이 10만 이하의 수열 A에서 다음 2가지 쿼리를 수행한다. 1 i j x y : 구간 [i, j]에 초항이 x이고 공차가 y인 등차수열 더하기 2 i j : 구간 [i, j]에 포함되는 등차수열인 구간 [l, r] 중 가장 긴 것의 길이를 출력 사용 알고리즘 금광 세그 풀이 태그에 레이지가 달려있긴 한데 사실 레이지가 필수적이..

수열과 쿼리 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는 해당 구간에 들어있는 서로 다른 숫자의 개수이..