글 읽기 - 팬윅트리로 구현했는데 틀리다고 나옵니다....

limulu 1년 전 0

예제 나와있는거랑 테스트 해봤을 때는 괜찮았는데 틀리다고 합니다...

펜윅트리로 잘 짠거 같은데 계속 틀리는 이유를 모르겠습니다......\

혹시 반례 알려주시면 감사하겠습니다...ㅠㅜ

from sys import stdin
input = stdin.readline

def update_2_dimention_fenwick_tree(tree, x, y, w):
    while y <= n:
        x_tmp = x
        while x_tmp <= n:
            tree[y][x_tmp] += w
            x_tmp += x_tmp & -x_tmp
        y += y & -y
    return tree

def query_2_dimention_fenwick_tree(tree, x, y):
    res = 0
    while y > 0:
        x_tmp = x
        while x_tmp > 0:
            res += tree[y][x_tmp]
            x_tmp -= x_tmp & -x_tmp
        y -= y & -y
    return res

n, m = map(int, input().split())

tree = [[0]*(n+1) for _ in range(n+1)]
li = [list(map(int, input().split())) for _ in range(n)]

for y in range(n):
    for x in range(n):
        tree = update_2_dimention_fenwick_tree(tree, x+1, y+1, li[y][x])

for _ in range(m):
    order = list(map(int, input().split()))
    if order[0] == 0:
        tree = update_2_dimention_fenwick_tree(tree, order[1], order[2], order[3]-li[order[2]-1][order[1]-1])
        li[order[2]-1][order[1]-1] = order[3]
    else:
        # w, x1, y1, x2, y2
        # x2y2 - x2y1 - x1y2 + x1y1
        if order[1] > order[3]:
            order[3], order[1] = order[1], order[3]
        if order[2] > order[4]:
            order[4], order[2] = order[2], order[4]
        a = query_2_dimention_fenwick_tree(tree,order[1]-1,order[2]-1)
        b = query_2_dimention_fenwick_tree(tree,order[3],order[2]-1)
        c = query_2_dimention_fenwick_tree(tree,order[1]-1,order[4])
        d = query_2_dimention_fenwick_tree(tree,order[3],order[4])
        print(d-b-c+a)

ohm55545 1년 전 0

li에서 행 열이 반대로 되어있네여

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

팬윅트리로 구현했는데 틀리다고 나옵니다....

limulu 1년 전 0

ohm55545 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말