Submission #47799152

---

Source Code Expand

#ARC155B Abs Abs Function

#Segment Tree: O(logN)
class SegmentTree:
    def __init__(self,n,identity_e,combine_f):
        self._n=n;self._size=2  #size=1だとbisectが不便
        while self._size<self._n:self._size<<=1
        self._identity_e=identity_e;self._combine_f=combine_f;self._node=[self._identity_e]*2*self._size
    def build(self,array):
        assert len(array)==self._n,'array too large'
        for i,v in enumerate(array,start=self._size):self._node[i]=v
        for i in range(self._size-1,0,-1):self._node[i]=self._combine_f(self._node[i<<1|0],self._node[i<<1|1])
    def update(self,index,value):  #一点更新
        i=self._size+index;self._node[i]=value
        while i-1:i>>=1;self._node[i]=self._combine_f(self._node[i<<1|0],self._node[i<<1|1])
    def fold(self,L,R):  #区間取得: [L,R)の区間値を得る
        L+=self._size;R+=self._size;vL,vR=[self._identity_e]*2
        while L<R:
            if L&1:vL=self._combine_f(vL,self._node[L]);L+=1
            if R&1:R-=1;vR=self._combine_f(self._node[R],vR)
            L>>=1;R>>=1
        return self._combine_f(vL,vR)
    #down: Falseなら単調増加、Trueなら単調減少を仮定する。
    #[0:Lt]の作用値がX以上/以下 となる、最小のLtを返す。閉区間なので扱い注意。
    def bisect(self,X,down=False):
        now=1; cnt=self._identity_e
        while now<self._size:
            Lt,Rt=self._node[now<<1|0],self._node[now<<1|1]
            if not down and self._combine_f(cnt,Lt)>=X: now=now<<1|0
            elif   down and self._combine_f(cnt,Lt)<=X: now=now<<1|0
            else: cnt=self._combine_f(cnt,Lt); now=now<<1|1
        return now-self._size


#入力受取
Q,A,B=map(int,input().split()); Query=[tuple(map(int,input().split())) for _ in range(Q)]

#事前に検索候補の値をすべて取得し、座標圧縮しておく
P=set([A-B,A+B])
for t,a,b in Query:
    if t==1: P.add(a-b); P.add(a+b)
    if t==2: P.add(a); P.add(b+1)
P=sorted(P); D={j:i for i,j in enumerate(P)}

#区間最大値を取得するSegTreeを建てる。
#ST[i]: P[i] if (P[i]を追加した後) else -INF
ST=SegmentTree(len(P),-10**18,max)
ST.update(D[A-B],A-B); ST.update(D[A+B],A+B)
#クエリを実行
for t,a,b in Query:
    if t==1:
        ST.update(D[a-b],a-b); ST.update(D[a+b],a+b)
    if t==2:
        #a <= x < b+1 を満たすxが存在するか調べる
        x=ST.fold(D[a],D[b+1])
        if a<=x<=b: print(0)
        else:  #かなり雑に処理する
            ans=10**18
            #1. x<a となる最大のxを取得。foldで可能。
            if D[a]>0: ans=min(ans, abs(a-ST.fold(0,D[a])))
            #2. b<x となる最小のxを取得。bisectで対応。
            Lt=ST.bisect(b+1)
            if Lt<len(P): ans=min(ans,abs(b-P[Lt]))
            #答えを出力
            print(ans)

Submission Info

Judge Result