글 읽기 - [python3] 2d-segment tree.. 시간초과

randoms 5년 전 0

이 문제를 풀기위해 다음과 같이 2d-segment tree라 불리는 구조를 구현하였습니다.

그런데 시간초과가 나버리네요 ㅠㅠ

2년전 다른 질문에서도 보니 저처럼 쿼드트리로 구현한 분도 시간초과라고 질문이 올라와 있는데,

이 문제는 이 구조로는 풀 수 없는 문제인건가요.. 팬윅트리와는 시간복잡도가 얼마나 차이나기에 이럴까 궁금합니다!

#제출시 주석해제
#import sys
#input=sys.stdin.readline

N,M=map(int,input().split())
L=[list(map(int,input().split()))for i in range(N)]
S=[None]*(2**21)

def init(x1,y1,x2,y2,n):
    global L,S
    if x1==x2 and y1==y2:
        S[n]=L[x1][y1]
        return S[n]
    m1=(x1+x2)//2
    m2=(y1+y2)//2
    S[n]=0
    for x,y,z,w,c in [(x1,y1,m1,m2,1),(x1,m2+1,m1,y2,2),(m1+1,y1,x2,m2,3),(m1+1,m2+1,x2,y2,4)]:
        S[n]+=init(x,y,z,w,4*n+c)
    return S[n]

init(0,0,N-1,N-1,0)

def change(x1,y1,x2,y2,n,a,b,c):
    global S
    if x1==x2==a and y1==y2==b:
        S[n]=c
        return S[n]
    m1=(x1+x2)//2
    m2=(y1+y2)//2
    if x1<=a<=x2 and y1<=b<=y2:
        S[n]=0
        for x,y,z,w,k in [(x1,y1,m1,m2,1),(x1,m2+1,m1,y2,2),(m1+1,y1,x2,m2,3),(m1+1,m2+1,x2,y2,4)]:
            S[n]+=change(x,y,z,w,4*n+k,a,b,c)
    return S[n]

def ans(x1,y1,x2,y2,n,a1,b1,a2,b2):
    global S
    if (x1,y1,x2,y2) == (a1,b1,a2,b2):
        return S[n]
    if x2<a1 or a2<x1 or y2<b1 or b2<y1:
        return 0
    m1=(x1+x2)//2
    m2=(y1+y2)//2
    result=0
    for x,y,z,w,k,a,b,c,d in [(x1,y1,m1,m2,1,a1,b1,min(a2,m1),min(b2,m2)),(x1,m2+1,m1,y2,2,a1,max(m2+1,b1),min(a2,m1),b2),(m1+1,y1,x2,m2,3,max(m1+1,a1),b1,a2,min(b2,m2)),(m1+1,m2+1,x2,y2,4,max(m1+1,a1),max(m2+1,b1),a2,b2)]:
        if not(z<a or c<x or w<b or d<y):
            result+=ans(x,y,z,w,4*n+k,a,b,c,d)
    return result

for _ in range(M):
    p,*t=map(int,input().split())
    if p%2:
        a,b,c,d=t
        print(ans(0,0,N-1,N-1,0,a-1,b-1,c-1,d-1))
    else:
        a,b,c=t
        change(0,0,N-1,N-1,0,a-1,b-1,c)