cp-library

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

View the Project on GitHub kobejean/cp-library

:heavy_check_mark: cp_library/ds/view/view5_cls.py

Depends on

Required by

Verified with

Code

import cp_library.__header__
from typing import Generic
from cp_library.misc.typing import _T1, _T2, _T3, _T4, _T5
from cp_library.alg.iter.sort.isort_ranged_fn import isort_ranged
import cp_library.ds.__header__
import cp_library.ds.view.__header__

class view5(Generic[_T1, _T2, _T3, _T4, _T5]):
    __slots__ = 'A1', 'A2', 'A3', 'A4', 'A5', 'l', 'r'
    def __init__(V, A1: list[_T1], A2: list[_T2], A3: list[_T3], A4: list[_T4], A5: list[_T5], l: int = 0, r: int = 0): 
        V.A1, V.A2, V.A3, V.A4, V.A5, V.l, V.r = A1, A2, A3, A4, A5, l, r
    def __len__(V): return V.r - V.l
    def __getitem__(V, i: int): 
        if 0 <= i < V.r - V.l: return V.A1[V.l+i], V.A2[V.l+i], V.A3[V.l+i], V.A4[V.l+i], V.A5[V.l+i]
        else: raise IndexError
    def __setitem__(V, i: int, v: tuple[_T1, _T2, _T3, _T4, _T5]): V.A1[V.l+i], V.A2[V.l+i], V.A3[V.l+i], V.A4[V.l+i], V.A5[V.l+i] = v
    def __contains__(V, v: tuple[_T1, _T2, _T3, _T4, _T5]): raise NotImplemented
    def set_range(V, l: int, r: int): V.l, V.r = l, r
    def index(V, v: tuple[_T1, _T2, _T3, _T4, _T5]): raise NotImplemented
    def reverse(V):
        l, r = V.l, V.r-1
        while l < r: 
            V.A1[l], V.A1[r] = V.A1[r], V.A1[l]
            V.A2[l], V.A2[r] = V.A2[r], V.A2[l]
            V.A3[l], V.A3[r] = V.A3[r], V.A3[l]
            V.A4[l], V.A4[r] = V.A4[r], V.A4[l]
            V.A5[l], V.A5[r] = V.A5[r], V.A5[l]
            l += 1; r -= 1
    def sort(V, reverse=False): isort_ranged(V.A1, V.A2, V.A3, V.A4, V.A5, l=V.l, r=V.r, reverse=reverse)
    def pop(V): V.r -= 1; return V.A1[V.r], V.A2[V.r], V.A3[V.r], V.A4[V.r], V.A5[V.r]
    def append(V, v: tuple[_T1, _T2, _T3, _T4, _T5]): V.A1[V.r], V.A2[V.r], V.A3[V.r], V.A4[V.r], V.A5[V.r] = v; V.r += 1
    def popleft(V): V.l += 1; return V.A1[V.l-1], V.A2[V.l-1], V.A3[V.l-1], V.A4[V.l-1], V.A5[V.l-1]
    def appendleft(V, v: tuple[_T1, _T2, _T3, _T4, _T5]): V.l -= 1; V.A1[V.l], V.A2[V.l], V.A3[V.l], V.A4[V.l], V.A5[V.l] = v
    def validate(V): return 0 <= V.l <= V.r <= len(V.A1)
'''
╺━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━╸
             https://kobejean.github.io/cp-library               
'''
from typing import Generic
from typing import TypeVar

_S = TypeVar('S'); _T = TypeVar('T'); _U = TypeVar('U'); _T1 = TypeVar('T1'); _T2 = TypeVar('T2'); _T3 = TypeVar('T3'); _T4 = TypeVar('T4'); _T5 = TypeVar('T5'); _T6 = TypeVar('T6')




def argsort_ranged(A: list[int], l: int, r: int, reverse=False):
    P = Packer(r-l-1); I = [A[l+i] for i in range(r-l)]; P.ienumerate(I, reverse); I.sort()
    for i in range(r-l): I[i] = (I[i] & P.m) + l
    return I



class Packer:
    __slots__ = 's', 'm'
    def __init__(P, mx: int): P.s = mx.bit_length(); P.m = (1 << P.s) - 1
    def enc(P, a: int, b: int): return a << P.s | b
    def dec(P, x: int) -> tuple[int, int]: return x >> P.s, x & P.m
    def enumerate(P, A, reverse=False): P.ienumerate(A:=list(A), reverse); return A
    def ienumerate(P, A, reverse=False):
        if reverse:
            for i,a in enumerate(A): A[i] = P.enc(-a, i)
        else:
            for i,a in enumerate(A): A[i] = P.enc(a, i)
    def indices(P, A: list[int]): P.iindices(A:=list(A)); return A
    def iindices(P, A):
        for i,a in enumerate(A): A[i] = P.m&a


def isort_ranged(*L: list, l: int, r: int, reverse=False):
    n = r - l
    order = argsort_ranged(L[0], l, r, reverse=reverse)
    inv = [0] * n
    # order contains indices in range [l, r), need to map to [0, n)
    for i in range(n): inv[order[i]-l] = i
    for i in range(n):
        j = order[i] - l  # j is in range [0, n)
        for A in L: A[l+i], A[l+j] = A[l+j], A[l+i]
        order[inv[i]], order[inv[j]] = order[inv[j]], order[inv[i]]
        inv[i], inv[j] = inv[j], inv[i]
    return L



class view5(Generic[_T1, _T2, _T3, _T4, _T5]):
    __slots__ = 'A1', 'A2', 'A3', 'A4', 'A5', 'l', 'r'
    def __init__(V, A1: list[_T1], A2: list[_T2], A3: list[_T3], A4: list[_T4], A5: list[_T5], l: int = 0, r: int = 0): 
        V.A1, V.A2, V.A3, V.A4, V.A5, V.l, V.r = A1, A2, A3, A4, A5, l, r
    def __len__(V): return V.r - V.l
    def __getitem__(V, i: int): 
        if 0 <= i < V.r - V.l: return V.A1[V.l+i], V.A2[V.l+i], V.A3[V.l+i], V.A4[V.l+i], V.A5[V.l+i]
        else: raise IndexError
    def __setitem__(V, i: int, v: tuple[_T1, _T2, _T3, _T4, _T5]): V.A1[V.l+i], V.A2[V.l+i], V.A3[V.l+i], V.A4[V.l+i], V.A5[V.l+i] = v
    def __contains__(V, v: tuple[_T1, _T2, _T3, _T4, _T5]): raise NotImplemented
    def set_range(V, l: int, r: int): V.l, V.r = l, r
    def index(V, v: tuple[_T1, _T2, _T3, _T4, _T5]): raise NotImplemented
    def reverse(V):
        l, r = V.l, V.r-1
        while l < r: 
            V.A1[l], V.A1[r] = V.A1[r], V.A1[l]
            V.A2[l], V.A2[r] = V.A2[r], V.A2[l]
            V.A3[l], V.A3[r] = V.A3[r], V.A3[l]
            V.A4[l], V.A4[r] = V.A4[r], V.A4[l]
            V.A5[l], V.A5[r] = V.A5[r], V.A5[l]
            l += 1; r -= 1
    def sort(V, reverse=False): isort_ranged(V.A1, V.A2, V.A3, V.A4, V.A5, l=V.l, r=V.r, reverse=reverse)
    def pop(V): V.r -= 1; return V.A1[V.r], V.A2[V.r], V.A3[V.r], V.A4[V.r], V.A5[V.r]
    def append(V, v: tuple[_T1, _T2, _T3, _T4, _T5]): V.A1[V.r], V.A2[V.r], V.A3[V.r], V.A4[V.r], V.A5[V.r] = v; V.r += 1
    def popleft(V): V.l += 1; return V.A1[V.l-1], V.A2[V.l-1], V.A3[V.l-1], V.A4[V.l-1], V.A5[V.l-1]
    def appendleft(V, v: tuple[_T1, _T2, _T3, _T4, _T5]): V.l -= 1; V.A1[V.l], V.A2[V.l], V.A3[V.l], V.A4[V.l], V.A5[V.l] = v
    def validate(V): return 0 <= V.l <= V.r <= len(V.A1)
Back to top page