cp_library/ds/cnt/range_distinct_counter_cls.py

• View this file on GitHub
• Last update: 2025-06-20 03:24:59+09:00

Depends on

• cp_library/ds/cnt/distinct_counter_cls.py

Code

import cp_library.__header__
import cp_library.ds.__header__
import cp_library.ds.cnt.__header__
from cp_library.ds.cnt.distinct_counter_cls import DistinctCounter

class RangeDistinctCounter(DistinctCounter):
    def __init__(rdc, A: list[int], Amax: int):
        super().__init__(Amax)
        rdc.A = A
        rdc.l = rdc.r = 0
    def add(rdc, i): super().add(rdc.A[i])
    def remove(rdc, i): super().remove(rdc.A[i])
    def move_query(rdc, l: int, r: int):
        while rdc.r < r: rdc.add(rdc.r); rdc.r += 1
        while l < rdc.l: rdc.l -= 1; rdc.add(rdc.l)
        while r < rdc.r: rdc.r -= 1; rdc.remove(rdc.r)
        while rdc.l < l: rdc.remove(rdc.l); rdc.l += 1
        return super().count()

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


from collections import Counter

class DistinctCounter:
    def __init__(dc, Amax: int):
        dc.cnt = 0
        dc.freq = [0]*(Amax+1) if Amax < 5_000_000 else Counter()

    def add(dc, a):
        dc.cnt += dc.freq[a] == 0
        dc.freq[a] += 1

    def remove(dc, a):
        dc.freq[a] -= 1
        dc.cnt -= dc.freq[a] == 0
    
    def count(dc): return dc.cnt

class RangeDistinctCounter(DistinctCounter):
    def __init__(rdc, A: list[int], Amax: int):
        super().__init__(Amax)
        rdc.A = A
        rdc.l = rdc.r = 0
    def add(rdc, i): super().add(rdc.A[i])
    def remove(rdc, i): super().remove(rdc.A[i])
    def move_query(rdc, l: int, r: int):
        while rdc.r < r: rdc.add(rdc.r); rdc.r += 1
        while l < rdc.l: rdc.l -= 1; rdc.add(rdc.l)
        while r < rdc.r: rdc.r -= 1; rdc.remove(rdc.r)
        while rdc.l < l: rdc.remove(rdc.l); rdc.l += 1
        return super().count()

Back to top page