[BOJ] 백준 18436번 수열과 쿼리 37 (Java)

#18436 수열과 쿼리 37

난이도 : 골드 1

유형 : 세그먼트 트리

18436번: 수열과 쿼리 37

▸ 문제

길이가 N인 수열 A1, A2, ..., AN이 있다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오.

• 1 i x: Ai를 x로 바꾼다.
• 2 l r: l ≤ i ≤ r에 속하는 모든 Ai중에서 짝수의 개수를 출력한다.
• 3 l r: l ≤ i ≤ r에 속하는 모든 Ai중에서 홀수의 개수를 출력한다.

수열의 인덱스는 1부터 시작한다

▸ 입력

첫째 줄에 수열의 크기 N (1 ≤ N ≤ 100,000)이 주어진다.

둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 10^9)

셋째 줄에는 쿼리의 개수 M (1 ≤ M ≤ 100,000)이 주어진다.

넷째 줄부터 M개의 줄에는 쿼리가 한 줄에 하나씩 주어진다. (1 ≤ i ≤ N, 1 ≤ l ≤ r ≤ N, 1 ≤ x ≤ 10^9)

▸ 출력

2, 3번 쿼리의 정답을 한 줄에 하나씩 출력한다.

 

문제 풀이  

짝수 혹은 홀수 세그먼트 트리를 생성하여 구간에 해당하는 짝수 혹은 홀수의 수를 구해주면 된다. 예로 짝수 세그먼트 트리를 만들었다고 했을 때 2번 쿼리는 그대로 세그먼트 트리의 구간 쿼리를 통해서 짝수 개수를 구해주면 되고 3번 쿼리가 주어졌을 때는 구간 길이(b-a+1) - 짝수 개수를 빼주면 홀수 개수를 구할 수 있다.

 

예제에서 주어진 [1 2 3 4 5 6]의 짝수 세그먼트 트리를 구하면 다음과 같다.

 

 

여기서 이제 구간 쿼리를 이용하여 각 구간별 짝수 혹은 홀수의 개수를 구해주면 된다. 예로 [2, 5]의 짝수 개수는 2개임을 알 수 있다.

 

[2, 5] 구간에서 짝수 개수 구하기

풀이 코드 

import java.io.*;
import java.util.StringTokenizer;

public class Main {

	static int[] arr, tree;
	static int n;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		n = Integer.parseInt(br.readLine());
		arr = new int[n+1];
		tree = new int[4*n];
		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i=1; i<=n; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		
		
		init(1,n,1);
		
		StringBuilder sb = new StringBuilder();
		int m = Integer.parseInt(br.readLine());
		for(int i=0; i<m; i++) {
			st = new StringTokenizer(br.readLine());
			int op = Integer.parseInt(st.nextToken());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			if(op == 1) {
				// 홀 > 짝 
				if(arr[a]%2==1 && b%2 ==0) {
					update(1,n,1,a,1);	
				}
				// 짝 > 홀 
				else if(arr[a]%2==0 && b%2==1) { 
					update(1,n,1,a,0);	
				}
				arr[a] =b ;
			}else if(op==2 || op == 3){
				long x = query(1,n,1,a,b);
				if(op == 2) {
					sb.append(x+"\n");
				} else {
					sb.append((b-a+1-x)+"\n");
				}
			} 
		}
		System.out.println(sb.toString());
	}
	
	static int init(int s, int e, int node) {
		if(s==e) {
			if(arr[s]%2==0) return tree[node] = 1;
			else return 0;
		}
		int mid = (s+e)/2;
		return tree[node] = init(s, mid, node*2) +init(mid+1, e, node*2+1);
	}
	
	static int update(int s, int e, int node, int idx, int val) {
		if(idx < s|| e < idx ) return tree[node];
		if(s == e)  {
			return tree[node] = val;
		}
		
		int mid = (s+e)/2;
		return tree[node] = update(s, mid, node*2, idx, val) + update(mid+1, e, node*2+1, idx, val);
	}
	
	static int query(int s, int e, int node, int l, int r) {
		if(r < s || e < l) return 0;
		if(l <= s && e <= r) {
			return tree[node];
		}
		int mid = (s+e)/2;
		return query(s,mid,node*2,l,r)+query(mid+1,e,node*2+1,l,r);
	}
	
}