mo's algorithm 썸네일형 리스트형 BOJ)13548 수열과 쿼리 6 문제: icpc.me/13548 길이가 N인 수열이 주어질 때 구간 i j 사이에 가장 많이 등장한 수가 몇번 등장했는지 출력하는 문제이다. 이 문제를 온라인으로 수행하려고하면 굉장히 힘들어 보인다. 하지만 업데이트가 이루어지지 않기 때문에 오프라인 쿼리 문제로 변형시켜서 풀어볼 수 있다. 따라서 이 문제를 mo's algorithm을 이용하여 풀건데 가장 많이 등장하는 수를 결정해야 하기 때문에 현재까지 가장 많이 등장하는 수를 계속 가지고 있어야하고 각각의 수가 몇번 등장하였나 배열을 a, i번 등장한 수가 몇개 있나 배열을 b에 각각 저장해두면 현재 쿼리의 답이 x면 만약 add로 인하여 추가 된 b가 x보다 크다면 x를 증가시켜주고 erase로 인하여 x만큼 등장한 수가 없어진다면 x를 감소시켜주.. 더보기 BOJ)8462 배열의 힘 문제: icpc.me/8462 시퀀스와 쿼리가 주어질 때 매 쿼리에 대한 답을 출력하는 문제이다. 쿼리는 구간이 주어지면 구간에 존재하는 모든 자연수 s에 대하여 (s 의 개수의 제곱) x s를 합한 값이다. 쿼리와 시퀀스가 10만이기 때문에 적어도 쿼리를 log나 root 시간에 처리해주고 싶지만 안타깝게도 저 쿼리를 해당 시간에 처리하기는 힘든거 같다. 하지만 쿼리 도중에 업데이트가 일어나지 않기 때문에 쿼리를 정렬한 뒤 mo's 알고리즘으로 접근한다면 해답을 얻을 수 있다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657#include #include usin.. 더보기 이전 1 다음