수열과 쿼리

https://www.acmicpc.net/workbook/view/914

 

수열과 쿼리 1, 3

https://www.acmicpc.net/problem/13537

https://www.acmicpc.net/problem/13544

Merge Sort Tree를 이용하여 해결할 수 있다. 주어진 구간의 $logN$ 개의 노드들에 대하여 K 이상의 수들을 이분탐색하면 $O(NlogN+Qlog^2{N})$ 안에 해결할 수 있다.

 

수열과 쿼리 5

https://www.acmicpc.net/problem/13547

Mo's algorithm 으로 해결할 수 있다. 특정 구간에 오른쪽, 왼쪽에서 삽입, 삭제하는 시간이 O(T) 라 한다면 전체 시간복잡도는 $O(N^{1.5}T)$ 안에 해결할 수 있다.

서로 다른 수들의 수를 세기 위해서는 각 수들의 빈도를 저장하는 배열 cnt를 관리하고, cnt가 0에서 1로 변할 때는 ans++, 1에서 0으로 변할 때는 ans--를 해주면 된다. T=1이니, 전체 시간복잡도는 $O(N^{1.5})$ 이다.

 

수열과 쿼리 6

https://www.acmicpc.net/problem/13548

수열과 쿼리 5와 비슷한 방법으로 Mo's algorithm 을 이용한다. 가장 많이 등장한 수의 등장 횟수를 세기 위해서 이번에도 각 수들의 빈도를 저장하는 배열 cnt를 관리한다. 이제 이 cnt배열들 중에서 최댓값을 세야 한다. 이를 $O(1)$안에 풀기 위하여 cnt값의 빈도를 저장하는 배열 val을 만든다. 빈도의 최댓값이 감소할 때에는 최대 1씩만 감소한다는 점을 이용하면 cnt와 val을 이용하여 해결할 수 있다.

 

수열과 쿼리 4, 0, 7

https://www.acmicpc.net/problem/13546

https://www.acmicpc.net/problem/13545

https://www.acmicpc.net/problem/13550

수열과 쿼리 4를 해결하면 0, 7 모두 아주 간단한 변형으로 해결할 수 있다.

이번에도 Mo's algorithm 을 사용하는데, 일단 각각의 수들에 대하여 오른쪽, 왼쪽에서 삽입 삭제가 가능한 자료구조인 deque나, list를 사용하여 수들의 위치를 관리하자. 이제 각 수들에 대하여 범위에 속하는 구간에서 |l-r|의 최댓값을 구해야 하는데, 이를 segment tree로도 구할 수 있지만, 이러면 전체 시간복잡도가 $O(Qsqrt(N)lgN)$가 되어 $N<=10^5$ 에서는 위험하다.

이를 빨리 해결하기 위해서 이번에는 sqrt decompostion을 이용하자. 이를 이용하는 이유는 update 는 $O(1)$ 이 되어야 하지만, 전체 쿼리는 Q개이기 때문에 query는 최대 $O(sqrt(N))$ 까지로 처리할 수 있는 여유가 있기 때문이다. 

 

수열과 쿼리 8

https://www.acmicpc.net/problem/13553

이번에도 Mo's algorithm 을 사용하자. 하나의 숫자를 추가할 때 Ai+K, Ai-K 사이의 수들의 수를 더하고 빼 주어야 하니, BIT 를 이용하여 관리하면 $O(Qsqrt(N)lgN)$ 안에 해결할 수 있다.

 

수열과 쿼리 23

https://www.acmicpc.net/problem/16979

이번에도 Mo's algorithm 을 활용하여 풀 수 있는데, 정상적인 상황에서 inversion 의 개수를 셀 때 BIT 를 활용한다는 점을 생각하면 같은 방법으로 BIT를 이용하여 $O(Qsqrt(N)lgN)$ 안에 해결할 수 있다.

 

수열과 쿼리 10

https://www.acmicpc.net/problem/13557

이 문제는 금광 문제에서 사용한 Maximum Subarray Segment Tree를 이용하여 해결할 수 있다. 두 구간이 겹치지 않을 경우에는 두 구간 사이의 구간은 무조건 선택해야 함으로 그냥 합을 더해주고, 왼쪽, 오른쪽 부분은 각각 Maximum Subarray Segment Tree에서의 왼쪽 최대합, 오른쪽 최대합을 이용하면 된다. 두 구간이 겹칠 때는 경우를 나눠서 처리해 주어야 하는데, 겹치는 부분에 구간의 끝과 시작이 모두 있을 때, 하나만 있을때, 모두 없을 때로 경우 나눠서 Maximum Subarray Segment Tree의 값들을 이용하여 해결할 수 있다.

 

수열과 쿼리 11

https://www.acmicpc.net/problem/13704

이 문제는 누적 XOR 배열을 관리하며 해결하자.

새로 추가한 부분의 누적 XOR값이 T라면, 구간 내의 값들 중 T^K 값의 개수만큼 답에 더해주면 된다. 이를 위해서 또 빈도 배열 cnt배열을 관리해야 한다.