수열과 쿼리 37 [BOJ 18436]

세그먼트 트리 기초 문제이다. 이 문제를 보고 풀이를 떠올리지 못했다면 세그먼트 트리에 대한 기초를 다시 공부하기를 추천한다.

 

문제 요약

길이 10만 이하의 수열 A에서 3가지 쿼리를 수행한다.

1 i x : A[i]를 x로 update

2 l r : 구간 [l, r]에 존재하는 A[i] 중 짝수의 개수 출력

3 l r : 구간 [l, r]에 존재하는 A[i] 중 홀수의 개수 출력

 

사용 알고리즘

세그먼트 트리

 

풀이

2번 쿼리와 3번 쿼리 중 하나만 해결하면 나머지 쿼리도 해결할 수 있다. 홀수의 개수를 알면 구간에 있는 전체 수의 개수에서 홀수의 개수를 빼서 짝수의 개수를 계산할 수 있기 때문이다.

우리가 알아야하는 것은 구간에 존재하는 '홀수의 개수'의 구간합이기 때문에, 각 수를 2로 나눈 나머지를 취해준 상태에서 구간합이 우리가 구해야하는 값임을 알 수 있다. 따라서 세그먼트 트리의 각 노드는 '구간에 있는 홀수의 개수'를 저장하며, 초기에 세그먼트 트리를 생성할 때 A[i] 대신 A[i]%2를 넣은 후 일반적인 구간합 세그먼트 트리와 같이 구현해주면 문제를 쉽게 해결할 수 있다.

 

코드

#include<bits/stdc++.h>
#define SIZE 100010
using namespace std;
int seg[SIZE<<2],A[SIZE],N,M;
void init(int l,int r,int node)
{
    if(l>r)return;
    if(l==r){
        seg[node]=A[l]%2;
        return;
    }
    int mid=l+r>>1;
    init(l,mid,node<<1);
    init(mid+1,r,(node<<1)+1);
    seg[node]=seg[node<<1]+seg[(node<<1)+1];
}
void update(int l,int r,int node,int s,int w)
{
    if(l>r||l>s||r<s)return;
    if(s==l&&r==s){
        seg[node]=w%2;
        return;
    }
    int mid=l+r>>1;
    update(l,mid,node<<1,s,w);
    update(mid+1,r,(node<<1)+1,s,w);
    seg[node]=seg[node<<1]+seg[(node<<1)+1];
}
int query(int l,int r,int node,int s,int e)
{
    if(l>r||l>e||r<s)return 0;
    if(s<=l&&r<=e)return seg[node];
    int mid=l+r>>1;
    return query(l,mid,node<<1,s,e)+query(mid+1,r,(node<<1)+1,s,e);
}
int main()
{
    cin>>N;
    for(int i=1;i<=N;i++)scanf("%d",&A[i]);
    init(1,N,1);
    for(cin>>M;M--;){
        int tc,s,e;scanf("%d %d %d",&tc,&s,&e);
        if(tc==1)update(1,N,1,s,e);
        if(tc==2)printf("%d\n",e-s+1-query(1,N,1,s,e));
        if(tc==3)printf("%d\n",query(1,N,1,s,e));
    }
}