[백준] 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 ≤ 109)

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

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

출력

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

 

#include<bits/stdc++.h>

using namespace std;
int arr[1000001];
int tree[4000004];

int inits(int le, int ri, int n) {
	if (le == ri) {
		return tree[n] = arr[le]%2;
	}
	int mid = (le + ri) / 2;
	return tree[n] = inits(le, mid, n * 2) + inits(mid + 1, ri, n * 2 + 1);
}

void update(int le, int ri,int target,int node,int dif) {
	if (target < le || ri < target)//범위 밖이면
		return;
	if (le == ri) {
		tree[node] += dif;
		return;
	}
	tree[node] += dif;
	int mid = (le+ri) / 2;
	update(le, mid, target, node * 2, dif);
	update(mid + 1, ri, target, node * 2 + 1, dif);
}
int query(int le, int ri, int from, int to, int node) {
	if (to < le || ri < from) { //범위 밖
		return 0;
	}
	if (from <= le && ri <= to) {//범위 안
		return tree[node];
	}
	int mid = (le + ri) / 2;
	return query(le, mid, from, to, node * 2) + query(mid + 1, ri, from, to, node * 2 + 1);
}

int main() {
	 ios_base::sync_with_stdio;
	 cin.tie(NULL);
	 cout.tie(NULL);
	int n, m, x, k;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> x;
		arr[i] = x;
	}
	cin >> m;
	int a, b, c, dif;
	inits(0, n-1, 1);
	for (int i = 0; i < m; i++) {
		cin >> a >> b >> c;
		if (a == 1) {
			if (arr[b-1] % 2 == c % 2)continue;
			else {
				if (arr[b-1] % 2 == 0) { //기존 짝수
					arr[b-1] = c;
					update(0, n - 1, b - 1,1, 1);
				}
				else { //기존홀수
					arr[b-1] = c;
					update(0, n - 1, b - 1,1, -1);
				}
			
			}
		}
		else if (a == 2) {
			cout << (c-b+1)-query(0,n-1,b-1,c-1,1) << "\n";
		}
		else {
			cout << query(0,n-1,b-1,c-1,1)<< "\n";
		}
	}
}

골드 1 세그먼트트리 문제입니다

트리의 리프노드에 module 2 값을 넣습니다. 홀수면 1, 짝수면 0이 저장됩니다.

부모노드로 자녀노드의 합이 저장되어 각 구간의 홀수의 갯수가 저장됩니다.

 

update로는 짝수가 홀수로 바뀌는경우 dif=1 홀수가 짝수로 바뀌면 dif=-1이 됩니다.

바뀌지 않다면 그대로 continue합니다.