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/unittests/ds/tree/bit/bit4_cls_test.py

Depends on

Code

# verification-helper: PROBLEM https://onlinejudge.u-aizu.ac.jp/courses/lesson/2/ITP1/1/ITP1_1_A

import pytest

class TestBIT4:
    def test_basic_operations(self):
        """Test basic BIT4 operations"""
        values = [(1, 10, 100, 1000), (2, 20, 200, 2000), (3, 30, 300, 3000)]
        bit = BIT4(values)
        
        assert len(bit) == 3
        assert bit[0] == (1, 10, 100, 1000)
        assert bit[1] == (2, 20, 200, 2000)
        assert bit[2] == (3, 30, 300, 3000)
        
        assert bit.sum(1) == (1, 10, 100, 1000)
        assert bit.sum(2) == (3, 30, 300, 3000)
        assert bit.sum(3) == (6, 60, 600, 6000)

    def test_sum_range(self):
        """Test range sum operations"""
        values = [(1, 10, 100, 1000), (2, 20, 200, 2000), (3, 30, 300, 3000)]
        bit = BIT4(values)
        
        assert bit.sum_range(0, 2) == (3, 30, 300, 3000)
        assert bit.sum_range(1, 3) == (5, 50, 500, 5000)

    def test_initialization_with_size(self):
        """Test initialization with size"""
        bit = BIT4(5, (0, 0, 0, 0))
        assert len(bit) == 5
        for i in range(5):
            assert bit[i] == (0, 0, 0, 0)

from cp_library.ds.tree.bit.bit4_cls import BIT4

if __name__ == '__main__':
    from cp_library.test.unittest_helper import run_verification_helper_unittest
    run_verification_helper_unittest()
# verification-helper: PROBLEM https://onlinejudge.u-aizu.ac.jp/courses/lesson/2/ITP1/1/ITP1_1_A

import pytest

class TestBIT4:
    def test_basic_operations(self):
        """Test basic BIT4 operations"""
        values = [(1, 10, 100, 1000), (2, 20, 200, 2000), (3, 30, 300, 3000)]
        bit = BIT4(values)
        
        assert len(bit) == 3
        assert bit[0] == (1, 10, 100, 1000)
        assert bit[1] == (2, 20, 200, 2000)
        assert bit[2] == (3, 30, 300, 3000)
        
        assert bit.sum(1) == (1, 10, 100, 1000)
        assert bit.sum(2) == (3, 30, 300, 3000)
        assert bit.sum(3) == (6, 60, 600, 6000)

    def test_sum_range(self):
        """Test range sum operations"""
        values = [(1, 10, 100, 1000), (2, 20, 200, 2000), (3, 30, 300, 3000)]
        bit = BIT4(values)
        
        assert bit.sum_range(0, 2) == (3, 30, 300, 3000)
        assert bit.sum_range(1, 3) == (5, 50, 500, 5000)

    def test_initialization_with_size(self):
        """Test initialization with size"""
        bit = BIT4(5, (0, 0, 0, 0))
        assert len(bit) == 5
        for i in range(5):
            assert bit[i] == (0, 0, 0, 0)

'''
╺━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━╸
             https://kobejean.github.io/cp-library               
'''
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')


'''
╺━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━╸
            ┏━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓            
            ┃                                    7 ┃            
            ┗━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┯━┛            
            ┏━━━━━━━━━━━━━━━━━━┓                 │              
            ┃                3 ┃◄────────────────┤              
            ┗━━━━━━━━━━━━━━━━┯━┛                 │              
            ┏━━━━━━━━┓       │  ┏━━━━━━━━┓       │              
            ┃      1 ┃◄──────┤  ┃      5 ┃◄──────┤              
            ┗━━━━━━┯━┛       │  ┗━━━━━━┯━┛       │              
            ┏━━━┓  │  ┏━━━┓  │  ┏━━━┓  │  ┏━━━┓  │              
            ┃ 0 ┃◄─┤  ┃ 2 ┃◄─┤  ┃ 4 ┃◄─┤  ┃ 6 ┃◄─┤              
            ┗━┯━┛  │  ┗━┯━┛  │  ┗━┯━┛  │  ┗━┯━┛  │              
              │    │    │    │    │    │    │    │              
              ▼    ▼    ▼    ▼    ▼    ▼    ▼    ▼              
            ┏━━━┓┏━━━┓┏━━━┓┏━━━┓┏━━━┓┏━━━┓┏━━━┓┏━━━┓            
            ┃ 0 ┃┃ 1 ┃┃ 2 ┃┃ 3 ┃┃ 4 ┃┃ 5 ┃┃ 6 ┃┃ 7 ┃            
            ┗━━━┛┗━━━┛┗━━━┛┗━━━┛┗━━━┛┗━━━┛┗━━━┛┗━━━┛            
╺━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━╸
           Data Structure - Tree - Binary Index Tree            
'''
from typing import Generic




def argsort(A: list[int], reverse=False):
    P = Packer(len(I := list(A))-1); P.ienumerate(I, reverse); I.sort(); P.iindices(I)
    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_parallel(*L: list, reverse=False):
    inv, order = [0]*len(L[0]), argsort(L[0], reverse=reverse)
    for i, j in enumerate(order): inv[j] = i
    for i, j in enumerate(order):
        for A in L: A[i], A[j] = A[j], A[i]
        order[inv[i]], inv[j] = j, inv[i]
    return L


class list4(Generic[_T1, _T2, _T3, _T4]):
    __slots__ = 'A1', 'A2', 'A3', 'A4'
    def __init__(lst, A1: list[_T1], A2: list[_T2], A3: list[_T3], A4: list[_T4]):
        lst.A1, lst.A2, lst.A3, lst.A4 = A1, A2, A3, A4
    def __len__(lst): return len(lst.A1)
    def __getitem__(lst, i: int): return lst.A1[i], lst.A2[i], lst.A3[i], lst.A4[i]
    def __setitem__(lst, i: int, v: tuple[_T1, _T2, _T3, _T4]): lst.A1[i], lst.A2[i], lst.A3[i], lst.A4[i] = v
    def __contains__(lst, v: tuple[_T1, _T2, _T3, _T4]): raise NotImplementedError
    def index(lst, v: tuple[_T1, _T2, _T3, _T4]): raise NotImplementedError
    def reverse(lst): lst.A1.reverse(); lst.A2.reverse(); lst.A3.reverse(); lst.A4.reverse()
    def sort(lst, reverse=False): isort_parallel(lst.A1, lst.A2, lst.A3, lst.A4, reverse=reverse)
    def pop(lst): return lst.A1.pop(), lst.A2.pop(), lst.A3.pop(), lst.A4.pop()
    def append(lst, v: tuple[_T1, _T2, _T3, _T4]):
        v1, v2, v3, v4 = v
        lst.A1.append(v1); lst.A2.append(v2); lst.A3.append(v3); lst.A4.append(v4)
    def add(lst, i: int, v: tuple[_T1, _T2, _T3, _T4]): lst.A1[i] += v[0]; lst.A2[i] += v[1]; lst.A3[i] += v[2]; lst.A4[i] += v[3]
from typing import Generic, Union, Callable, Optional

class BITBase(Generic[_T]):
    _lst = list
    K: int = 1
    
    def __init__(bit, v: Union[int, list[_T]], e: _T = None) -> None:
        if isinstance(v, int):
            bit._n = v
            if bit._lst is list:
                bit._d = [e]*v if e is not None else [0]*v
            elif e is not None:
                bit._d = bit._lst(*([e_]*v for e_ in e))
            else:
                bit._d = bit._lst(*([0]*v for _ in range(bit.K)))
        else:
            bit.build(v)
        bit.e = e if e is not None else (0 if bit._lst is list else tuple(0 for _ in range(bit.K)))
        bit._lb = 1 << bit._n.bit_length()

    def build(bit, data: list[_T]):
        bit._n = len(data)
        if bit._lst is list:
            bit._d = bit._lst(data)
        else:
            bit._d = bit._lst(*([data[i][j] for i in range(len(data))] for j in range(len(data[0]))))
        for i in range(bit._n):
            if (r := i | i + 1) < bit._n:
                bit._add(r, bit._d[i])

    def _add(bit, i: int, x: _T) -> None:
        bit._d[i] = bit._op(bit._d[i], x)
    
    def _op(bit, a: _T, b: _T) -> _T:
        return a + b
    
    def _sub(bit, a: _T, b: _T) -> _T:
        return a - b

    def add(bit, i: int, x: _T) -> None:
        while i < bit._n: bit._add(i, x); i |= i + 1

    def sum(bit, n: int) -> _T:
        s = bit.e
        while n: s, n = bit._op(s, bit._d[n - 1]), n & n - 1
        return s

    def sum_range(bit, l: int, r: int) -> _T:
        s = bit.e
        while r: s, r = bit._op(s, bit._d[r - 1]), r & r - 1
        while l: s, l = bit._sub(s, bit._d[l - 1]), l & l - 1
        return s

    def __len__(bit) -> int: return bit._n

    def __getitem__(bit, i: int) -> _T:
        s, l = bit._d[i], i & (i + 1)
        while l != i: s, i = bit._sub(s, bit._d[i - 1]), i - (i & -i)
        return s

    get = __getitem__

    def __setitem__(bit, i: int, x: _T) -> None:
        bit.add(i, bit._sub(x, bit[i]))

    set = __setitem__

    def prelist(bit) -> list[_T]:
        pre = [bit.e] + bit._d[:] if bit._lst is list else bit._lst(*([e_] * (bit._n + 1) for e_ in bit.e))
        for i in range(bit._n): pre[i+1] = bit._d[i]
        for i in range(bit._n + 1):
            if i & i - 1 < bit._n + 1:
                pre[i] = bit._op(pre[i], pre[i & i - 1])
        return pre

    def bisect_left(bit, v, key: Optional[Callable] = None) -> int:
        i = 0
        s = bit.e
        if v <= s: return -1
        m = bit._lb
        
        if key:
            while m := m >> 1:
                if (ni := m | i) <= bit._n and key(ns := bit._op(s, bit._d[ni - 1])) < v:
                    s, i = ns, ni
        else:
            while m := m >> 1:
                if (ni := m | i) <= bit._n and (ns := bit._op(s, bit._d[ni - 1])) < v:
                    s, i = ns, ni
        return i

    def bisect_right(bit, v, key: Optional[Callable] = None) -> int:
        i = 0
        s = bit.e
        m = bit._lb
        
        if key:
            while m := m >> 1:
                if (ni := m | i) <= bit._n and key(ns := bit._op(s, bit._d[ni - 1])) <= v:
                    s, i = ns, ni
        else:
            while m := m >> 1:
                if (ni := m | i) <= bit._n and (ns := bit._op(s, bit._d[ni - 1])) <= v:
                    s, i = ns, ni
        return i

class BIT4(BITBase[_T]):
    _lst = list4
    K = 4
    def _add(bit, i: int, x: _T) -> None: bit._d.add(i, x)
    def _op(bit, a, b): return a[0] + b[0], a[1] + b[1], a[2] + b[2], a[3] + b[3]
    def _sub(bit, a, b): return a[0] - b[0], a[1] - b[1], a[2] - b[2], a[3] - b[3]

if __name__ == '__main__':
    
    """
    Helper for making unittest files compatible with verification-helper.
    
    This module provides a helper function to run a dummy Library Checker test
    so that unittest files can be verified by oj-verify.
    """
    
    def run_verification_helper_unittest():
        """
        Run a dummy AOJ ITP1_1_A test for verification-helper compatibility.
        
        This function should be called in the __main__ block of unittest files
        that need to be compatible with verification-helper.
        
        The function:
        1. Prints "Hello World" (AOJ ITP1_1_A solution)
        2. Runs pytest for the calling test file
        3. Exits with the pytest result code
        """
        import sys
        
        # Print "Hello World" for AOJ ITP1_1_A problem
        print("Hello World")
        
        import io
        from contextlib import redirect_stdout, redirect_stderr
    
        # Capture all output during test execution
        output = io.StringIO()
        with redirect_stdout(output), redirect_stderr(output):
            # Get the calling module's file path
            frame = sys._getframe(1)
            test_file = frame.f_globals.get('__file__')
            if test_file is None:
                test_file = sys.argv[0]
            result = pytest.main([test_file])
        
        if result != 0: 
            print(output.getvalue())
        sys.exit(result)
    run_verification_helper_unittest()
Back to top page