[BOJ 18436] 수열과 쿼리 37

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

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부터 시작한다.

 

 

- 알고리즘 정리

 

1번 쿼리가 입력으로 들어오면 새로 들어오는 수의 홀짝 여부가 이전 수와 다른 경우에 update() 함수를 수행해줍니다.

2, 3번 쿼리가 들어오면 각 구간의 홀수의 개수를 리턴해줍니다.

 

 

- 코드 작성

 

#include<bits/stdc++.h>
using namespace std;

#define MAX 100000
int arr[MAX+1],tree[MAX*4+1];

int init(int start,int end,int node){
	if(start==end){
		return tree[node]=arr[start]%2==0?0:1;
	}
	int mid=(start+end)/2;
	return tree[node]=init(start,mid,node*2)+init(mid+1,end,node*2+1);
}

void update(int start,int end,int node,int idx,int w,int value){
	if(idx<start||idx>end){ 
		return;
	}
	if(w%2==0){
		tree[node]--;
	}
	else{
		tree[node]++;
	}
	if(start==end){
		tree[node]=value;
		return;
	}
	int mid=(start+end)/2;
	update(start,mid,node*2,idx,w,value);
	update(mid+1,end,node*2+1,idx,w,value);
}

int query(int start,int end,int node,int left,int right){
	if(start>right||end<left){
		return 0;
	}
	if(left<=start && end<=right){
		return tree[node]; 
	}
	int mid=(start+end)/2;
	return query(start,mid,node*2,left,right)+query(mid+1,end,node*2+1,left,right);
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int n,m;	
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>arr[i];
	}
	init(1,n,1);
	cin>>m;
	for(int i=0;i<m;i++){
		int q,idx,w,l,r;
		cin>>q;
		if(q==1){
			cin>>idx>>w;
			if(arr[idx]%2==0 && w%2==1){
				update(1,n,1,idx,w,1);
			}
			else if(arr[idx]%2==1 && w%2==0){
				update(1,n,1,idx,w,0);
			}
			arr[idx]=w;
		}
		if(q==2){
			cin>>l>>r;
			int num=r-l+1;
			cout<<num-query(1,n,1,l,r)<<'\n';
		}
		if(q==3){
			cin>>l>>r;
			cout<<query(1,n,1,l,r)<<'\n';
		}
	}
}

코드 제출 결과