cp-library

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub kobejean/cp-library

:heavy_check_mark: test/library-checker/data-structure/range_reverse_range_sum.test.py

Depends on

Code

# verification-helper: PROBLEM https://judge.yosupo.jp/problem/range_reverse_range_sum

from operator import add

def main():
    N, Q = read()
    TreapMonoidReversibe.reserve(1+N+Q)
    T = TreapMonoidReversibe(add, 0)
    T.build(read())
    for _ in range(Q):
        t, l, r = read()
        if t == 0:
            T.reverse(l,r)
        else:
            write(T.prod(l,r))

from cp_library.ds.tree.bst.treap_monoid_reversible_cls import TreapMonoidReversibe
from cp_library.io.read_fn import read
from cp_library.io.write_fn import write

if __name__ == '__main__':
    main()
# verification-helper: PROBLEM https://judge.yosupo.jp/problem/range_reverse_range_sum

from operator import add

def main():
    N, Q = read()
    TreapMonoidReversibe.reserve(1+N+Q)
    T = TreapMonoidReversibe(add, 0)
    T.build(read())
    for _ in range(Q):
        t, l, r = read()
        if t == 0:
            T.reverse(l,r)
        else:
            write(T.prod(l,r))

'''
╺━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━╸
             https://kobejean.github.io/cp-library               
'''


def reserve(A: list, est_len: int) -> None: ...
try:
    from __pypy__ import resizelist_hint
except:
    def resizelist_hint(A: list, est_len: int):
        pass
reserve = resizelist_hint




i64_max = (1<<63)-1

class BST:
    __slots__ = 'r'
    K,sub,st=[-1],[-1,-1],[]
    def __init__(T):T.r=T._nr()
    def _nt(T):return T.__class__()
    def _nr(T):r=len(T.K);T.K.append(i64_max);T.sub.append(-1);T.sub.append(-1);return r
    def _nn(T,k):n=len(T.K);T.K.append(k);T.sub.append(-1);T.sub.append(-1);return n
    def insert(T,k):T._i(T.r<<1,k,n:=T._nn(k));T._r();return n
    def get(T,k):
        if~(i:=T._f(T.r<<1,k)):return i
        raise KeyError
    def pop(T,k):
        if ~(i:=T._t(T.r<<1,k)):T._d(i,T.st[-1]);T._r();return i
        else:T.st.clear();raise KeyError
    def __delitem__(T,k):
        if~(i:=T._t(T.r<<1,k)):T._d(i,T.st[-1]);T._r()
        else:T.st.clear();raise KeyError
    def __contains__(T,k):return 0<=T._f(T.r<<1,k)
    def _f(T,s,k):
        i = T.sub[s]
        while~i and T.K[i]!=k:T._p(i);i=T.sub[i<<1|(T.K[i]<k)]
        return i
    def _t(T,s,k):
        T.st.append(s)
        while~(i:=T.sub[s])and T.K[i]!=k:T._p(i);T.st.append(s:=i<<1|(T.K[i]<k))
        return i
    def _i(T,s,k,n):
        T.st.append(s)
        while ~T.sub[s]:T._p(i:=T.sub[s]);T.st.append(s:=i<<1|(T.K[i]<k))
        i,T.sub[s]=T.sub[s],n
    def _d(T,i,s): raise NotImplemented
    def _r(T):T.st.clear()
    def _p(T,i): pass
    @classmethod
    def reserve(cls,sz):sz+=1;reserve(cls.K,sz);reserve(cls.sub,sz<<1);reserve(cls.st,sz.bit_length()<<1)
    def _node_str(T, i): return f"{T.K[i]}"
    def __str__(T):
        def rec(i, pre="", is_right=False):
            if i == -1: return ""
            ret = "";T._p(i)
            if ~(r:=T.sub[i<<1|1]):ret+=rec(r,pre+("   "if is_right else"│  "),True)
            ret+=pre+("┌─ "if is_right else"└─ ")+T._node_str(i)+"\n"
            if ~(l:=T.sub[i<<1]):ret+=rec(l,pre+("   "if not is_right else"│  "),False)
            return ret
        return rec(T.sub[T.r<<1]).rstrip()

class BSTUpdates(BST):
    def _u(T,i): pass
    def _r(T):
        while T.st:T._u(T.st.pop()>>1)

class CartesianTree(BST):
    K,P,sub,st=[-1],[42],[-1,-1],[]
    def _nr(T):T.P.append(-1);return super()._nr()
    def _nn(T,k,p=-1):T.P.append(p);return super()._nn(k)
    def get(T,k):return T.P[BST.get(T,k)]
    def pop(T,k):return T.P[BST.pop(T,k)]
    def split(T,k):S=T._nt();T._sp(T.sub[T.r<<1],k,S.r<<1,T.r<<1);T._r();return S,T
    def insert(T,k,p):T._i(T.r<<1,k,n:=T._nn(k,p));T._r();return n
    def __getitem__(T,k):return T.get(k)
    def _i(T,s,k,n):
        T.st.append(s)
        while~T.sub[s]and T.P[i:=T.sub[s]]<T.P[n]:T._p(i);T.st.append(s:=i<<1|(T.K[i]<k))
        i,T.sub[s]=T.sub[s],n
        if~i:T._sp(i,k,n<<1,n<<1|1)
    def _sp(T,i,k,l,r):
        T.st.append(l)
        if 1<l^r:T.st.append(r)
        while~i:
            T._p(i)
            if T.K[i]<k:T.sub[l]=i;i=T.sub[l:=i<<1|1];T.st.append(l)
            else:T.sub[r]=i;i=T.sub[r:=i<<1];T.st.append(r)
        T.sub[l]=T.sub[r]=-1
    def _m(T,s,l,r):
        T.st.append(s)
        while~l and~r:
            if T.P[l]<T.P[r]:T._p(l);T.sub[s]=l;l=T.sub[s:=l<<1|1]
            else:T._p(r);T.sub[s]=r;r=T.sub[s:=r<<1]
            T.st.append(s)
        T.sub[s]=l if~l else r
    def _d(T,i,s):T._p(i);T._m(s,T.sub[i<<1],T.sub[i<<1|1])
    @classmethod
    def reserve(cls,sz):super(CartesianTree,cls).reserve(sz);reserve(cls.P,sz+1)

class Treap(CartesianTree):
    __slots__='e'
    K,V,P,sub,st=[-1],[-1],[42],[-1,-1],[]
    def __init__(T,e=-1):T.e=e;super().__init__()
    def _nt(T):return T.__class__(T.e)
    def _nr(T):T.V.append(T.e);return super()._nr()
    def _nn(T,k,v):T.V.append(v);return super()._nn(k,(T.P[-1]*1103515245+12345)&0x7fffffff)
    def insert(T,k,v):return super().insert(k,v)
    def get(T,k):return T.V[BST.get(T,k)]
    def pop(T,k):return T.V[BST.pop(T,k)]
    def set(T,k,v):T._s(T.r<<1,k,v);T._r()
    def __setitem__(T,k,v):T.set(k,v)
    def _s(T,s,k,v):
        if ~(i:=T._t(s,k)):T.V[i]=v;T.st.append(i<<1)
        else:
            n=T._nn(k,v)
            while T.P[n]<T.P[i:=T.st[-1]>>1]:T._p(T.st.pop())
            T._p(i)
            i,T.sub[s]=T.sub[s:=i<<1|(i!=T.r and T.K[i]<k)],n
            if~i:T._sp(i,k,n<<1,n<<1|1)
    def _node_str(T, i): return f"{T.K[i]}:{T.V[i]}"
    @classmethod
    def reserve(cls,hint):super(Treap,cls).reserve(hint);reserve(cls.V,hint+1)

class TreapMonoid(Treap, BSTUpdates):
    __slots__='op'
    K,V,A,P,sub,st=[-1],[-1],[-1],[42],[-1,-1],[]
    def __init__(T,op,e=-1):T.op=op;super().__init__(e)
    def _nt(T):return T.__class__(T.op,T.e)
    def _nr(T):T.A.append(T.e);return super()._nr()
    def _nn(T,k,v):T.A.append(v);return super()._nn(k, v)
    def prod(T,l,r):
        # find common ancestor
        a=T.sub[T.r<<1]
        while~a and not l<=T.K[a]<r:T._p(a);a=T.sub[a<<1|(T.K[a]<l)]
        if a<0:return T.e
        # left subtreap
        ac,i=T.V[a],T.sub[a<<1]
        while~i:
            T._p(i)
            if not(b:=T.K[i]<l):
                if~(j:=T.sub[i<<1|1]):ac=T.op(T.A[j],ac)
                ac=T.op(T.V[i],ac)
            i=T.sub[i<<1|b]
        # right subtreap
        i=T.sub[a<<1|1]
        while~i:
            T._p(i)
            if b:=T.K[i]<r:
                if~(j:=T.sub[i<<1]):ac=T.op(ac,T.A[j])
                ac=T.op(ac,T.V[i])
            i=T.sub[i<<1|b]
        return ac
    def all_prod(T):return T.A[T.r]
    def __getitem__(T,k):
        if isinstance(k,int):return T.get(k)
        elif isinstance(k,slice):return T.prod(k.start,k.stop)
    @classmethod
    def reserve(cls,sz):super(TreapMonoid,cls).reserve(sz);reserve(cls.A,sz+1)
    def _u(T,i):
        T.A[i]=T.V[i]
        if~(l:=T.sub[i<<1]):T.A[i]=T.op(T.A[l],T.A[i])
        if~(r:=T.sub[i<<1|1]):T.A[i]=T.op(T.A[i],T.A[r])
    def _v(T,i=None):
        if i is None:
            assert T.all_prod() == (ac := T._v(i) if ~(i := T.sub[T.r<<1]) else T.e)
            return ac
        T._p(i);ac = T.V[i]
        if ~(l:=T.sub[i<<1]):
            assert T.P[i] <= T.P[l]
            assert T.K[l] <= T.K[i]
            ac = T.op(T._v(l), ac)
        if ~(r:=T.sub[i<<1|1]):
            assert T.P[i] <= T.P[r]
            assert T.K[i] <= T.K[r]
            ac = T.op(ac, T._v(r))
        assert T.A[i] == ac
        return ac

class BSTSized(BSTUpdates):
    K,sz,sub,st=[-1],[0,0],[-1,-1],[]
    def _nr(T):T.sz.append(0);T.sz.append(0);return super()._nr()
    def _nn(T,k):T.sz.append(0);T.sz.append(0);return super()._nn(k)
    def kth(T,k):
        if 0<=k<len(T):return T._k(T.r<<1,k)
        raise KeyError
    def __len__(T):return T.sz[T.r<<1]
    def _k(T,s,k):
        while ~k:
            T._p(T.sub[s])
            if (sz:=T.sz[s:=T.sub[s]<<1])<=k:k-=1+sz;s^=1
        return s>>1
    def _kt(T,s,k):
        while ~k:
            T._p(T.sub[s]);T.st.append(s)
            if (sz:=T.sz[s:=T.sub[s]<<1])<=k:k-=1+sz;s^=1
        return s>>1
    def _u(T,i):
        T.sz[s]=T.sz[l<<1]+1+T.sz[l<<1|1] if~(l:=T.sub[s:=i<<1]) else 0
        T.sz[s]=T.sz[r<<1]+1+T.sz[r<<1|1] if~(r:=T.sub[s:=i<<1|1]) else 0
    @classmethod
    def reserve(cls,sz):super().reserve(sz);reserve(cls.sz,(sz+1)<<1)

class BSTImplicit(BSTSized):
    K,sz,sub,st=None,[0,0],[-1,-1],[]
    def _nr(T):r=len(T.sz)>>1;T.sz.append(0);T.sz.append(0);T.sub.append(-1);T.sub.append(-1);return r
    def _nn(T,k):n=len(T.sz)>>1;T.sz.append(0);T.sz.append(0);T.sub.append(-1);T.sub.append(-1);return n
    def pop(T,k):
        if 0<=k<len(T):T._d(i:=T._kt(T.r<<1,k),T.st[-1]);T._r();return i
        else:raise KeyError
    def __contains__(T,k):raise NotImplemented
    def __delitem__(T,k):
        if 0<=k<len(T):T._d(T._kt(T.r<<1,k),T.st[-1]);T._r()
        else:raise KeyError
    def _f(T,s,k):return T._k(s,k)
    def _t(T,s,k):return T._kt(s,k)
    def _i(T,s,k,n):T.sub[T._kt(s,k)]=n
    @classmethod
    def reserve(cls,sz):sz+=1;reserve(cls.st,sz.bit_length()<<1);reserve(cls.sz,sz<<1);reserve(cls.sub,sz<<1)

class BSTReversible(BSTImplicit):
    K,rev,sz,sub,st=None,[0],[0,0],[-1,-1],[]
    def _nr(T):T.rev.append(0);return super()._nr()
    def _nn(T,k):T.rev.append(0);return super()._nn(k)
    def _p(T,i):
        if T.rev[i]:
            T.sub[l],T.sub[r],T.sz[l],T.sz[r]=T.sub[r:=i<<1|1],T.sub[l:=i<<1],T.sz[r],T.sz[l]
            if~(l:=T.sub[l]):T.rev[l]^=1
            if~(r:=T.sub[r]):T.rev[r]^=1
            T.rev[i]=0
    @classmethod
    def reserve(cls,sz):super().reserve(sz);reserve(cls.rev,sz+1)

class BSTReversible(BSTImplicit):
    K,rev,sz,sub,st=None,[0],[0,0],[-1,-1],[]
    def _nr(T):T.rev.append(0);return super()._nr()
    def _nn(T,k):T.rev.append(0);return super()._nn(k)
    def _p(T,i):
        if T.rev[i]:
            T.sub[l],T.sub[r],T.sz[l],T.sz[r]=T.sub[r:=i<<1|1],T.sub[l:=i<<1],T.sz[r],T.sz[l]
            if~(l:=T.sub[l]):T.rev[l]^=1
            if~(r:=T.sub[r]):T.rev[r]^=1
            T.rev[i]=0
    @classmethod
    def reserve(cls,sz):super().reserve(sz);reserve(cls.rev,sz+1)

class BSTSized(BSTUpdates):
    K,sz,sub,st=[-1],[0,0],[-1,-1],[]
    def _nr(T):T.sz.append(0);T.sz.append(0);return super()._nr()
    def _nn(T,k):T.sz.append(0);T.sz.append(0);return super()._nn(k)
    def kth(T,k):
        if 0<=k<len(T):return T._k(T.r<<1,k)
        raise KeyError
    def __len__(T):return T.sz[T.r<<1]
    def _k(T,s,k):
        while ~k:
            T._p(T.sub[s])
            if (sz:=T.sz[s:=T.sub[s]<<1])<=k:k-=1+sz;s^=1
        return s>>1
    def _kt(T,s,k):
        while ~k:
            T._p(T.sub[s]);T.st.append(s)
            if (sz:=T.sz[s:=T.sub[s]<<1])<=k:k-=1+sz;s^=1
        return s>>1
    def _u(T,i):
        T.sz[s]=T.sz[l<<1]+1+T.sz[l<<1|1] if~(l:=T.sub[s:=i<<1]) else 0
        T.sz[s]=T.sz[r<<1]+1+T.sz[r<<1|1] if~(r:=T.sub[s:=i<<1|1]) else 0
    @classmethod
    def reserve(cls,sz):super().reserve(sz);reserve(cls.sz,(sz+1)<<1)

class CartesianTreeSized(CartesianTree, BSTSized):
    K,P,sz,sub,st=[-1],[42],[0,0],[-1,-1],[]
    def kth(T,k): return T.P[BSTSized.kth(T,k)]
    def _nr(T):T.P.append(-1);return BSTSized._nr(T)
    def _nn(T,k,p=-1):T.P.append(p);return BSTSized._nn(T,k)
    @classmethod
    def reserve(cls,sz):BSTSized.reserve.__call__(sz);reserve(cls.P,sz+1)

class CartesianTreeReversible(CartesianTreeSized,BSTReversible):
    def _nr(T):T.P.append((T.P[-1]*1103515245+12345)&0x7fffffff);return BSTReversible._nr(T)
    def _nn(T,k,v):T.P.append(v);return BSTReversible._nn(T,k)
    def reverse(T,l,r):
        if l>=r:return
        lo,hi = l>0,r<len(T)
        s = T.r<<1
        if hi:T._sp(T.sub[s],r,s,1);T._r()
        if lo:T._sp(T.sub[s],l,0,s);T._r()
        T.rev[T.sub[s]]^=1
        if hi:T._m(s,T.sub[s],T.sub[1]);T._r()
        if lo:T._m(s,T.sub[0],T.sub[s]);T._r()
    @classmethod
    def reserve(cls,sz):BSTReversible.reserve.__call__(sz);reserve(cls.P,sz+1)

class CartesianTreeImplicit(CartesianTreeSized,BSTImplicit):
    K,P,sz,sub,st=None,[42],[0,0],[-1,-1],[]
    def _nr(T):T.P.append((T.P[-1]*1103515245+12345)&0x7fffffff);return BSTImplicit._nr(T)
    def _nn(T,k,p):T.P.append(p);return BSTImplicit._nn(T,k)
    def _i(T,s,k,n):
        T.st.append(s)
        while ~k and ~T.sub[s] and T.P[i:=T.sub[s]]<T.P[n]:
            T._p(i)
            if (sz:=T.sz[s:=i<<1])<k:k-=1+sz;s^=1
            T.st.append(s)
        i,T.sub[s]=T.sub[s],n
        if~i:T._sp(i,k,n<<1,n<<1|1)
    def _sp(T,i,k,l,r):
        T.st.append(l)
        if 1<l^r:T.st.append(r)
        while~i:
            T._p(i)
            if (sz:=T.sz[i<<1])<k:k-=1+sz;T.sub[l]=i;i=T.sub[l:=i<<1|1];T.st.append(l)
            else:T.sub[r]=i;i=T.sub[r:=i<<1];T.st.append(r)
        T.sub[l]=T.sub[r]=-1
    def _node_str(T, i): return f"{T.P[i]}"
    @classmethod
    def reserve(cls,sz):BSTImplicit.reserve.__call__(sz);reserve(cls.P,sz+1)

class TreapSized(Treap, CartesianTreeSized):
    K,V,P,sz,sub,st=[-1],[-1],[42],[0,0],[-1,-1],[]
    def _nr(T):T.V.append(T.e);return CartesianTreeSized._nr(T)
    def _nn(T,k,v):T.V.append(v);return CartesianTreeSized._nn(T,k,(T.P[-1]*1103515245+12345)&0x7fffffff)
    def kth(T,k): return T.V[BSTSized.kth(T,k)]
    @classmethod
    def reserve(cls,sz):CartesianTreeSized.reserve.__call__(sz);reserve(cls.V,sz+1)

class TreapImplicit(TreapSized,CartesianTreeImplicit):
    K,V,P,sz,sub,st=None,[-1],[42],[0,0],[-1,-1],[]
    def _nr(T):T.V.append(T.e);return CartesianTreeImplicit._nr(T)
    def _nn(T,k,v):T.V.append(v);return CartesianTreeImplicit._nn(T,k,(T.P[-1]*1103515245+12345)&0x7fffffff)
    def set(T,k,v):T._s(T.r<<1,k,v);T._r()
    def _i(T,s,k,n):
        T.st.append(s)
        while ~k and ~T.sub[s] and T.P[i:=T.sub[s]]<T.P[n]:
            T._p(i)
            if (sz:=T.sz[s:=i<<1])<k:k-=1+sz;s^=1
            T.st.append(s)
        i,T.sub[s]=T.sub[s],n
        if~i:T._sp(i,k,n<<1,n<<1|1)
    def _sp(T,i,k,l,r):
        T.st.append(l)
        if 1<l^r:T.st.append(r)
        while~i:
            T._p(i)
            if (sz:=T.sz[i<<1])<k:k-=1+sz;T.sub[l]=i;i=T.sub[l:=i<<1|1];T.st.append(l)
            else:T.sub[r]=i;i=T.sub[r:=i<<1];T.st.append(r)
        T.sub[l]=T.sub[r]=-1
    def _s(T,s,k,v):T.V[i:=T._t(s,k)]=v;T.st.append(i<<1)
    def _node_str(T, i): return f"{T.V[i]}"
    @classmethod
    def reserve(cls,sz):CartesianTreeImplicit.reserve.__call__(sz);reserve(cls.V,sz+1)

class TreapReversible(TreapImplicit,CartesianTreeReversible):
    K,V,P,sz,sub,st=None,[-1],[42],[0,0],[-1,-1],[]
    def _nr(T):T.V.append(T.e);return CartesianTreeReversible._nr(T)
    def _nn(T,k,v):T.V.append(v);return CartesianTreeReversible._nn(T,k,(T.P[-1]*1103515245+12345)&0x7fffffff)
    @classmethod
    def reserve(cls,sz):CartesianTreeReversible.reserve.__call__(sz);reserve(cls.V,sz+1)

class TreapMonoidReversibe(TreapMonoid,TreapReversible):
    __slots__='op'
    K,V,A,P,rev,sz,sub,st=None,[-1],[-1],[42],[0],[0,0],[-1,-1],[]
    def build(T,V):
        if not V: return
        base, rnd, P = len(T.V), T.P[-1], [0]*(N:=len(V))
        for i in range(N): P[i] = rnd = (rnd*1103515245+12345)&0xfffffff
        P.sort()
        T.V.extend(V); T.A.extend(V)
        T.P.extend(zeros:=[0]*N); T.rev.extend(zeros)
        T.sz.extend(zeros); T.sz.extend(zeros); T.sub.extend([-1]*(N<<1))
        N += base
        s,i = 2,base
        while i < N: T.P[i] = P.pop(); i += s
        s,hs,i,l = 4,1,base+1,-1
        while P:
            while i < N:
                T.P[i] = P.pop()
                l, r = i<<1,i<<1|1
                T.sub[l] = i-hs
                T.sz[l] = T.sz[(i-hs)<<1]+1+T.sz[(i-hs)<<1|1]
                T.A[i] = T.op(T.A[i-hs],T.A[i])
                if i+hs<N:
                    T.sub[r] = i+hs
                    T.sz[r] = T.sz[(i+hs)<<1]+1+T.sz[(i+hs)<<1|1]
                    T.A[i] = T.op(T.A[i],T.A[i+hs])
                elif i<N-1:
                    T.sub[r] = l = i+(1<<((N-1-i).bit_length()-1))
                    T.sz[r] = T.sz[l<<1]+1+T.sz[l<<1|1]
                    T.A[i] = T.op(T.A[i],T.A[l])
                i += s
            i,s,hs = base+s-1,s<<1,hs<<1
        T.sub[T.r<<1] = r = base+hs-1
        T.sz[T.r<<1] = T.sz[r<<1]+1+T.sz[r<<1|1]
        T.A[T.r] = T.A[r]

    def _nr(T):T.A.append(T.e);return TreapReversible._nr(T)
    def _nn(T,k,v):T.A.append(v);return TreapReversible._nn(T,k,v)
    def prod(T,l,r):
        # find common ancestor
        a=T.sub[T.r<<1]
        while~a:
            T._p(a)
            if l<=(sz:=T.sz[s:=a<<1])<r:break
            if sz<l:l-=1+sz;r-=1+sz;s^=1
            a=T.sub[s]
        if a<0:return T.e
        r-=T.sz[a<<1]+1
        # left subtreap
        ac,i=T.V[a],T.sub[a<<1]
        while~i and ~l:
            T._p(i)
            if (sz:=T.sz[s:=i<<1])<l:l-=1+sz;s^=1
            else:
                if~(j:=T.sub[i<<1|1]):ac=T.op(T.A[j],ac)
                ac=T.op(T.V[i],ac)
            i=T.sub[s]
        # right subtreap
        i=T.sub[a<<1|1]
        while~i and ~r:
            T._p(i)
            if (sz:=T.sz[s:=i<<1])<r:
                if~(j:=T.sub[s]):ac=T.op(ac,T.A[j])
                ac=T.op(ac,T.V[i])
                r-=1+sz;s^=1
            i=T.sub[s]
        return ac
    @classmethod
    def reserve(cls,sz):TreapReversible.reserve.__call__(sz);reserve(cls.A,sz+1)
    def _u(T,i):
        T.A[i]=T.V[i]
        T.sz[s]=T.sz[l<<1]+1+T.sz[l<<1|1] if~(l:=T.sub[s:=i<<1]) else 0
        T.sz[s]=T.sz[r<<1]+1+T.sz[r<<1|1] if~(r:=T.sub[s:=i<<1|1]) else 0
        if~(l:=T.sub[i<<1]):T.A[i]=T.op(T.A[l],T.A[i])
        if~(r:=T.sub[i<<1|1]):T.A[i]=T.op(T.A[i],T.A[r])
    # def _node_str(T, i): return f"{i=} V{T.V[i]} A{T.A[i]} ({T.sz[i<<1]}:{T.sz[i<<1|1]})"
    def _node_str(T, i): return f"{T.V[i]}"

if __name__ == '__main__':
    L = 31
    T = TreapMonoidReversibe(add, 0)
    V = [*range(L)]
    T.build(V)
    print(T)
    # for L in range(2000):
    #     T = TreapMonoidReversibe(add, 0)
    #     V = [*range(L)]
    #     T.build(V)
    #     assert len(T) == L, f'{V}\n{T}'


from typing import Iterable, Type, Union, overload
import typing
from collections import deque
from numbers import Number
from types import GenericAlias 
from typing import Callable, Collection, Iterator, Union
import os
import sys
from io import BytesIO, IOBase


class FastIO(IOBase):
    BUFSIZE = 8192
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        BUFSIZE = self.BUFSIZE
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        BUFSIZE = self.BUFSIZE
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    stdin: 'IOWrapper' = None
    stdout: 'IOWrapper' = None
    
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable

    def write(self, s):
        return self.buffer.write(s.encode("ascii"))
    
    def read(self):
        return self.buffer.read().decode("ascii")
    
    def readline(self):
        return self.buffer.readline().decode("ascii")
try:
    sys.stdin = IOWrapper.stdin = IOWrapper(sys.stdin)
    sys.stdout = IOWrapper.stdout = IOWrapper(sys.stdout)
except:
    pass
from typing import TypeVar
_T = TypeVar('T')
_U = TypeVar('U')

class TokenStream(Iterator):
    stream = IOWrapper.stdin

    def __init__(self):
        self.queue = deque()

    def __next__(self):
        if not self.queue: self.queue.extend(self._line())
        return self.queue.popleft()
    
    def wait(self):
        if not self.queue: self.queue.extend(self._line())
        while self.queue: yield
 
    def _line(self):
        return TokenStream.stream.readline().split()

    def line(self):
        if self.queue:
            A = list(self.queue)
            self.queue.clear()
            return A
        return self._line()
TokenStream.default = TokenStream()

class CharStream(TokenStream):
    def _line(self):
        return TokenStream.stream.readline().rstrip()
CharStream.default = CharStream()


ParseFn = Callable[[TokenStream],_T]
class Parser:
    def __init__(self, spec: Union[type[_T],_T]):
        self.parse = Parser.compile(spec)

    def __call__(self, ts: TokenStream) -> _T:
        return self.parse(ts)
    
    @staticmethod
    def compile_type(cls: type[_T], args = ()) -> _T:
        if issubclass(cls, Parsable):
            return cls.compile(*args)
        elif issubclass(cls, (Number, str)):
            def parse(ts: TokenStream): return cls(next(ts))              
            return parse
        elif issubclass(cls, tuple):
            return Parser.compile_tuple(cls, args)
        elif issubclass(cls, Collection):
            return Parser.compile_collection(cls, args)
        elif callable(cls):
            def parse(ts: TokenStream):
                return cls(next(ts))              
            return parse
        else:
            raise NotImplementedError()
    
    @staticmethod
    def compile(spec: Union[type[_T],_T]=int) -> ParseFn[_T]:
        if isinstance(spec, (type, GenericAlias)):
            cls = typing.get_origin(spec) or spec
            args = typing.get_args(spec) or tuple()
            return Parser.compile_type(cls, args)
        elif isinstance(offset := spec, Number): 
            cls = type(spec)  
            def parse(ts: TokenStream): return cls(next(ts)) + offset
            return parse
        elif isinstance(args := spec, tuple):      
            return Parser.compile_tuple(type(spec), args)
        elif isinstance(args := spec, Collection):
            return Parser.compile_collection(type(spec), args)
        elif isinstance(fn := spec, Callable): 
            def parse(ts: TokenStream): return fn(next(ts))
            return parse
        else:
            raise NotImplementedError()

    @staticmethod
    def compile_line(cls: _T, spec=int) -> ParseFn[_T]:
        if spec is int:
            fn = Parser.compile(spec)
            def parse(ts: TokenStream): return cls([int(token) for token in ts.line()])
            return parse
        else:
            fn = Parser.compile(spec)
            def parse(ts: TokenStream): return cls([fn(ts) for _ in ts.wait()])
            return parse

    @staticmethod
    def compile_repeat(cls: _T, spec, N) -> ParseFn[_T]:
        fn = Parser.compile(spec)
        def parse(ts: TokenStream): return cls([fn(ts) for _ in range(N)])
        return parse

    @staticmethod
    def compile_children(cls: _T, specs) -> ParseFn[_T]:
        fns = tuple((Parser.compile(spec) for spec in specs))
        def parse(ts: TokenStream): return cls([fn(ts) for fn in fns])  
        return parse
            
    @staticmethod
    def compile_tuple(cls: type[_T], specs) -> ParseFn[_T]:
        if isinstance(specs, (tuple,list)) and len(specs) == 2 and specs[1] is ...:
            return Parser.compile_line(cls, specs[0])
        else:
            return Parser.compile_children(cls, specs)

    @staticmethod
    def compile_collection(cls, specs):
        if not specs or len(specs) == 1 or isinstance(specs, set):
            return Parser.compile_line(cls, *specs)
        elif (isinstance(specs, (tuple,list)) and len(specs) == 2 and isinstance(specs[1], int)):
            return Parser.compile_repeat(cls, specs[0], specs[1])
        else:
            raise NotImplementedError()

class Parsable:
    @classmethod
    def compile(cls):
        def parser(ts: TokenStream): return cls(next(ts))
        return parser

@overload
def read() -> list[int]: ...
@overload
def read(spec: Type[_T], char=False) -> _T: ...
@overload
def read(spec: _U, char=False) -> _U: ...
@overload
def read(*specs: Type[_T], char=False) -> tuple[_T, ...]: ...
@overload
def read(*specs: _U, char=False) -> tuple[_U, ...]: ...
def read(*specs: Union[Type[_T],_U], char=False):
    if not char and not specs: return [int(s) for s in TokenStream.default.line()]
    parser: _T = Parser.compile(specs)
    ret = parser(CharStream.default if char else TokenStream.default)
    return ret[0] if len(specs) == 1 else ret

def write(*args, **kwargs):
    '''Prints the values to a stream, or to stdout_fast by default.'''
    sep, file = kwargs.pop("sep", " "), kwargs.pop("file", IOWrapper.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", "\n"))
    if kwargs.pop("flush", False):
        file.flush()

if __name__ == '__main__':
    main()
Back to top page