BOJ 백준 13550 수열과 쿼리 7

 

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

 

 

[ 문제 요약 ]

• l r: l ≤ i ≤ j ≤ r이면서 (Ai + Ai+1 + ...+ Aj) mod K = 0인 가장 긴 연속 부분 수열의 길이를 출력한다. 즉, 연속하는 부분 배열의 누적 합 중 K의 배수인 가장 긴 연속하는 부분 수열의 길이 출력

 

[ 테스트 케이스 설명 ]

5 10		// 수열의 크기(1<=100,000), K(2<=1,000,000)
2 3 5 2 3	// 원소 값 1<=1,000,000,000
2		// 쿼리 개수(1<=100,000)
1 3		// 구간 l <= r
2 4
// 답
3
3

 

 

[ 알고리즘 분류 ]

• 누적 합
• 오프라인 쿼리
• 제곱근 분할법
• mo’s 알고리즘

 

[ 문제 해설 ]

 

구간이 주어질 때, 해당 구간의 부분합을 빠르게 알기 위해 누적합을 이용합니다.

 

그러면 구간 i, j가 주어질 때, sum[j] - sum[i-1] 을 하면 부분합을 빠르게 구할 수 있습니다.

 

sum[j] - sum[i] = k로 나눈 나머지가 0이기 위해서는, sum[i]와, sum[j]를 각각 k로 나눈 나머지가 같아야 합니다.

 

그러므로 처음부터 누적합 입력 시 K로 나눈 나머지를 입력해 주고, 같은 값을 갖는 가장 긴 부분 배열을 찾으면 됩니다.

 

그렇게 생각하면 이 문제는 아래 두 문제와 거의 같습니다.

 

https://kyjdummy.tistory.com/55

BOJ 백준 13545 수열과 쿼리 0

https://kyjdummy.tistory.com/52

BOJ 백준 13546 수열과 쿼리 4

 

K로 나눈 나머지를 담은 배열의 안에 들어있는, 같은 숫자들의 인덱스 차이를 실시간으로 조회할 수 있어야 합니다.

 

그래서 각 원소당 등장하는 인덱스를 담을 ArrayDeque를 선언하여 임의의 수가 등장한 인덱스를 모두 알 수 있도록 합니다.

 

인덱스를 알 수 있기 때문에 해당 임의 숫자의 최대 인덱스, 최소 인덱스 차이를 빠르게 알 수 있습니다.

 

그런데 각 원소의 최대 최소 차이를 바로 안다 해도, 차이 중 최댓값을 찾는 것은 완전 탐색을 해야 합니다.

 

이 부분에서 탐색을 더 빠르게 하기 위해, 인덱스 값 차이를 제곱근 분할법으로 탐색합니다.

 

예를 들어 배열의 길이 차이가 나올 수 있는 최댓값이 10만이면, 10만을 sqrt(N)으로 나눈 결괏값만큼 배열을 선언합니다.

 

fac[] = new int[N / sqrt(N)]

 

이렇게 해놓고, 만약 길이 차이가 50인 값이 나왔다면 해당 50의 구간은 50/sqrt(N) 구간이 됩니다.

 

그 구간에 맞게 +, -를 진행하면, 가장 큰 구간에서부터 낮은 구간까지 탐색해서 내려올 때, 값이 1 이상인 구간은 정답이 존재하는 구간이므로, 그 구간의 가장 큰 길이 차이부터 작은 길이 차이까지 역순으로 탐색하며 답을 출력하면 됩니다.

 

빠른 탐색을 위해 제곱근으로 분할하기 때문에 “제곱근 분할법”알고리즘이라 합니다.

 

그리고 주어지는 쿼리는 업데이트가 없으므로 오프라인 쿼리로 처리하고 Mo’s 알고리즘으로 정렬하여 포인터의 이동이 최소가 되도록 합니다.

 

디테일은 코드를 통해 확인 가능합니다.

 

[ 정답 코드 ]

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;

class Main{
	
	static int sqrt;
	static int N, K, Q;
	static int arr[];
	static int ans[];
	static int fac[];// N / sqrt 한 구간을 담을 배열
	static int cnt[];// 인덱스 차이를 담을 배열
	static ArrayList<Query> query;
	static ArrayDeque<Integer>[] idxList;
	
	public static void main(String[] args)throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());// 수열의 크기(1<=100,000)
		K = Integer.parseInt(st.nextToken());// K(2<=1,000,000)
		idxList = new ArrayDeque[K];
		sqrt = (int)Math.sqrt(N);
		fac = new int[N / sqrt + 1];
		cnt = new int[N + 1];
		arr = new int[N + 1];
		
		st = new StringTokenizer(br.readLine());
		for(int i=1; i<=N; i++)
			arr[i] = (arr[i-1] + Integer.parseInt(st.nextToken())) % K;
		
		for(int i=0; i<K; i++)
			idxList[i] = new ArrayDeque<>();
		
		Q = Integer.parseInt(br.readLine());// 쿼리 개수(1<=100,000)
		ans = new int[Q + 1];
		query = new ArrayList<>();
		
		for(int i=1; i<=Q; i++)
		{
			st = new StringTokenizer(br.readLine());
			int l = Integer.parseInt(st.nextToken());
			int r = Integer.parseInt(st.nextToken());
			query.add(new Query(l-1, r, i, l / sqrt));
		}
		
		Collections.sort(query);
		
		int R = 0;
		int L = 1;
		for(Query q : query)
		{
			while(R < q.right) excute(++R, 1);
			while(q.left < L) excute(--L, 2);
			while(q.right < R) excute(R--, 3);
			while(L < q.left) excute(L++, 4);
			
			ans[q.idx] = find();
		}
		
		StringBuilder sb = new StringBuilder();
		
		for(int i=1; i<=Q; i++)
			sb.append(ans[i]).append('\n');
		
		System.out.print(sb);
	}
	static void excute(int idx, int flag) {
		cal(arr[idx], -1);
		
		switch(flag)
		{
			case 1: idxList[arr[idx]].addLast(idx); break;
			case 2: idxList[arr[idx]].addFirst(idx);break;
			case 3: idxList[arr[idx]].removeLast(); break;
			case 4: idxList[arr[idx]].removeFirst();break;
		}
		
		cal(arr[idx], 1);
	}
	static void cal(int num, int plus) {
		if(idxList[num].size() > 0)
		{
			int diff = idxList[num].peekLast() - idxList[num].peekFirst();
			fac[diff / sqrt] += plus;
			cnt[diff] += plus;
		}
	}
	static int find() {
		for(int i=N/sqrt; i>=0; i--)
		{
			if(fac[i] == 0)
				continue;
			
			int s = i * sqrt;
			int e = Math.min(N, s + sqrt - 1);
			
			while(e >= s)
			{
				if(cnt[e] > 0)
					return e;
				--e;
			}
		}
		return 0;
	}
	static class Query implements Comparable<Query>{
		int left, right, idx, fac;
		Query(int l, int r, int i, int f){
			left = l;
			right = r;
			idx = i;
			fac = f;
		}
		@Override
		public int compareTo(Query o) {
			if(fac != o.fac)
				return fac - o.fac;
			
			if((fac & 1) == 0)
				return right - o.right;
			
			return o.right - right;
		}
	}
}