백준/ Gold 1 문제 , 백준 파이썬 18436 , 수열과 쿼리 37 [세그먼트 트리]

백준/ Gold 1 문제 , 백준 파이썬 18436 , 수열과 쿼리 37 [세그먼트 트리]

 

 

Check Point !   ( 해당사항 ✓체크 )

1. 막힘 없이 수월하게 풀린 문제인가?

2. 1시간이내로 풀렸던 문제인가?

3. 1시간 이상 or 며칠을 두고 풀어봤더니 풀린 문제인가?

4. 시간을 써도 도무지 풀 수 없는 문제인가?

5. 솔루션을 찾아봤는가?

-------------------------------------------------------------------------------------------
난이도 체감
1. 최상
2. 상
3. 중
4. 하


<이해도>
1. 완벽히 이해
2. 다소 헷갈리는 부분들이 있음
3. 이해 못함


<덧붙일 말>
시간 초과가 자꾸 발생해서 며칠 두고 푼 문제다. 
내가 한 실수는 init 함수 내에서 init 함수를 4번 호출 하는 식으로 했었는데, 배열이 커지면 기하급수적으로 호출이 늘어난 것이였다. 이부분을 고치니 통과했음.

 

문제 출처

 

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

 

풀이

 

 

1. 특정 부분 교체 함수

 

바꾸는 값이 짝수인지 홀수인지 체크해주고 짝수면 0번인덱스에 1, 홀수면 1번 인덱스에 1을 넣어 저장한다.

 

이후 부모 요소들도 자식노드의 각 합을 더해 저장시킨다.

 

 

 

2. 입력 받기 및 각 함수 호출

 

a가 1일때 원래 배열의 값이랑 바꿀 값이 같은 짝수이던가 같은 양수이면 세그먼트트리를 굳이 바꿔줄 필요가없다.

 

그러므로 같다면 넘기고 다를때만 update함수를 사용하여 교체한다.

 

 

a가 2일때는 짝수값이므로 결과값의 0번 인덱스

 

a가 3일때는 홀수값이므로 결과값의 1번 인덱스 값을 출력시킨다.

 

 

정답

 

import sys
input=sys.stdin.readline

def init(start,end,index):
    if start==end:
        if arr[start]%2==0:
            tree[index][0]=1
        else:
            tree[index][1]=1
    else:
        mid=(start+end)//2
        init(start,mid,index*2)
        init(mid+1,end,index*2+1)
        tree[index]=[tree[index*2][0]+tree[index*2+1][0],tree[index*2][1]+tree[index*2+1][1]]
    return tree[index]

def update(start,end,index,w,v):
    if w<start or w>end:
        return
    if start==end:
        if v%2==0:
            tree[index]=[1,0]
        else:
            tree[index]=[0,1]
        return tree[index]
    mid=(start+end)//2
    update(start,mid,index*2,w,v)
    update(mid+1,end,index*2+1,w,v)
    tree[index]=[tree[index*2][0]+tree[index*2+1][0],tree[index*2][1]+tree[index*2+1][1]]

def find_result(start,end,index,left,right):
    if start>right or end <left:
        return [0,0]
    if left<=start and right>=end:
        return tree[index]
    mid=(start+end)//2
    left_node=find_result(start,mid,index*2,left,right)
    right_node=find_result(mid+1,end,index*2+1,left,right)
    return [left_node[0]+right_node[0],left_node[1]+right_node[1]]

N=int(input())
arr=list(map(int,input().rstrip().split()))
tree=[[0,0] for _ in range(N*4)]

init(0,N-1,1)
for i in range(int(input())):
    a,b,c=map(int,input().split())
    if a==1:
        if arr[b-1]%2==c%2:
            arr[b-1]=c
            continue
        else:
            update(0,N-1,1,b-1,c)
            arr[b-1]=c
        
    elif a==2:
        print(find_result(0,N-1,1,b-1,c-1)[0])
    elif a==3:
        print(find_result(0,N-1,1,b-1,c-1)[1])