[백준 18436] 수열과 쿼리 37

작성일 | In |

문제 링크

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

풀이

구간에 속하는 홀수 혹은 짝수의 개수를 알 수 있다면 2, 3번 쿼리에 대한 답을 할 수 있습니다. 홀수를 1로 두고 짝수를 0으로 두었을 때 구간합을 구하면 3번 쿼리에선 그대로 출력하고 2번 쿼리에선 구간의 길이 - 구간합을 출력하면 됩니다. 세그먼트 트리나 펜윅 트리를 사용하면 업데이트와 구간합을 구하는 것을 $O(\log N)$으로 할 수 있기에 전체 시간복잡도 $O(M \log N)$입니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

int n, m, a[100100], t[100100];

void update(int bit, int val){
    while(bit <= n) t[bit] += val, bit += bit & -bit;
}

int find(int bit){
    int re = 0;
    while(bit) re += t[bit], bit -= bit & -bit;
    return re;
}

int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",a+i);
        if(a[i]%2) update(i, 1);
    }

    scanf("%d",&m);
    for(int i=1;i<=m;i++){
        int b, c, d; scanf("%d %d %d",&b,&c,&d);
        if(b == 1){
            if(a[c]%2 != d%2){
                update(c, a[c]%2 ? -1 : 1);
                a[c] = d;
            }
        }
        else{
            int s = find(d) - find(c-1);
            printf("%d\n", b == 2 ? d-c+1 - s : s);
        }
    }
}