글 읽기 - 이 문제 파이썬에서 세그먼트 트리를 이용해서 풀 수 있나요??(시간제한)

blutics 6년 전 0

제가 세그먼트 트리 + bisect를 이용해서 풀고 있는데.......

풀 수 있나요??!!!ㅎㅎㅎㅎㅎㅎㅎ

이거 세그먼트 트리 세팅할때 너무 오래 걸리는거 같은데.......ㅠㅠ

array를 써야하나......음.......

어제보다는 내장 함수도 쓰고 해서 다듬기는 했는데.....

오늘도 변수가 알파벳으로해서 읽기는 힘든 코드이지만!!!

조언부탁드립니다ㅠ

import math
import heapq
import bisect
import sys

class segTree():
    def __init__(self,x):
        self.origin=x
        self.tree=[0]*(2**(int(math.log(len(x),2))+2))
        self.ms_init(x,self.tree,1,len(x))
    def ms_init(self,x,y,i,j,z=1):
        a=len(x)
        k=(i+j)//2
        b=self.ms_init(x,y,i,k,2*z) if k-i+1>0 and i-j else x[i-1:k] 
        c=self.ms_init(x,y,k+1,j,2*z+1) if j-k>0 and i-j else x[k:j]
        d=[*heapq.merge(b,c)]
        self.tree[z]=[i,j,d]
        return d
    def node_search(self,y,z,l,x=1):
        a=self.tree[x][0]
        b=self.tree[x][1]
        if (a<=y<=b) or (a<=z<=b):
            if (a==y and b==y) or (a==z and b==z) or (a==y and b==z):
                l+=x,
                return
        else:
            if y<a and b<z:l+=x,
            return
        self.node_search(y,z,l,2*x)
        self.node_search(y,z,l,2*x+1)
    def rank(self,x,y):
        sum=0
        for i in y:
            sum+=bisect.bisect(self.tree[i][2],x)
        return sum
    def kth_bisect(self,x,y,z):
        l=[]
        self.node_search(x,y,l)
        for i in l:
            e=self.tree[i][2]
            a=0
            b=len(e)
            if self.rank(e[-1],l)<z:continue
            if self.rank(e[0],l)>z:continue
            while 1:
                k=self.rank(e[(b+a)//2],l)
                if k<z:
                    if self.rank(e[(b+a)//2+1],l)>z:break
                    a=(b+a)//2
                elif k>z:
                    b=(b+a)//2
                else:
                    return e[(b+a)//2]

sys.stdin.readline()
p=segTree([*map(int,sys.stdin.readline().split())])
for i in sys.stdin.readlines():
    x,y,z=map(int,i.split())
    print(p.kth_bisect(x,y,z))