BOJ 18436 수열과 쿼리 37

 

tree[node] 를 닫힌 구간 \( [l, r] \) 사이의 홀수의 개수로 정의하면 된다.

 

#include <bits/stdc++.h>

using namespace std;

int tree[440000], arr[110000];

void init(int l, int r, int node) {
    if(l==r) {
        tree[node]=arr[l]%2;
        return;
    }
    
    int mid = l+r>>1;
    init(l, mid, 2*node);
    init(mid+1, r, 2*node+1);
    tree[node]=tree[2*node]+tree[2*node+1];
}

void upd(int l, int r, int node, int p, int v) {
    if(p<l or r < p) return;
    if(l==r) {
        tree[node] = v%2;
        return;
    }
    
    int mid=l+r>>1;
    upd(l, mid, 2*node, p, v);
    upd(mid+1, r, 2*node+1, p, v);
    tree[node] = tree[2*node]+tree[2*node+1]; 
}

int qry(int l, int r, int node, int ql, int qr) {
    if(qr<l or r<ql) return 0;
    if(ql<=l and r<=qr) return tree[node];
    int mid=l+r>>1;
    return qry(l, mid, 2*node, ql, qr)+qry(mid+1, r, 2*node+1, ql, qr);
}

int main() {
    int N, M;
    scanf("%d", &N);
    for(int i=1;i<=N;++i) scanf("%d", &arr[i]);
   
    init(1, N, 1);
    
    scanf("%d", &M);
    while(M--) {
        int q, a,b ;
        scanf("%d%d%d", &q, &a, &b);
        if(q==1) {
            upd(1, N, 1, a, b);
        } else if(q==2){
            printf("%d\n", b-a+1-qry(1, N, 1, a, b));
        } else {
            printf("%d\n", qry(1, N, 1, a, b));
        }
    }
    return 0;
}