提出 #76691343

---

ソースコード 拡げる

from atcoder.segtree import SegTree
import math
import heapq
def solve(n:int,m:int,lrs:list[tuple[int,int]]):
    rls=[(r-1,l-1) for l,r in lrs]
    rls.sort()
    ls=[rls[i][1] for i in range(m)]
    def op(a,b):
        return min(a,b)
    st=SegTree(min,math.inf,ls)
    def nibtan(x:int):#位置x以上のｒのもので最小のl
        ok=m
        ng=-1
        mid=0
        while abs(ok-ng)>1:
            mid=(ok+ng)//2
            if rls[mid][0]>=x:
                ok=mid
            else:
                ng=mid
        if ok==m:
            return n+10
        return st.prod(ok,m)
    mex=[i+1 for i in range(n+1)]
    heapq.heapify(mex)
    kul=0
    sakuzyo=set()
    ans=[]
    inai=set()
    def tuika(x:int):#区間にxを追加する#ただしｘは区間に含まれない数のはず
        sakuzyo.add(x)

        while mex[0] in sakuzyo:
            kesu=heapq.heappop(mex)
            inai.add(kesu)
            sakuzyo.discard(kesu)
        return 
    def lup(kul):
        if ans[kul] in sakuzyo:
            sakuzyo.discard(ans[kul])
        else:
            if ans[kul] not in inai:
                return
            heapq.heappush(mex,ans[kul])
            inai.discard(ans[kul])
    def reset(inai,sakuzyo):
        for item in inai:
            heapq.heappush(mex,item)
        
        return 
            

    for i in range(n):
        minl=nibtan(i)
        if minl>i:
            ans.append(1)
            kul=i+1
            reset(inai,sakuzyo)
            inai=set()
            sakuzyo=set()
        else:
            while minl>kul:
                lup(kul)
                kul+=1
            atai=mex[0]
            ans.append(atai)
            tuika(atai)
    
    return tuple(ans)

            
        
        


        
        


    



if __name__=="__main__":
    for _ in range(int(input())):
        n,m=map(int,input().split())
        lrs=[tuple(map(int,input().split())) for i in range(m)]
        print(*solve(n,m,lrs))

提出情報

ジャッジ結果