Mo
(Mo.py)

• View this file on GitHub
• Last update: 2025-05-11 11:48:02+09:00

Outline

長さ $N$ の列 $A=(A_0, A_1, \dots, A_{N-1})$ と以下の形式の $Q$ 個のクエリがある.

部分列 $(A_L, A_{L+1}, \dots, A_{R-1})$ におけるある値を $F(L,R)$ と書くことにする.

このとき, $Q$ 個の整数の組 $(L_1, R_1), \dots, (L_Q, R_Q)$ が与えられるので, $F(L_1, R_1), \dots, F(L_Q, R_Q)$ を求めよ.

ここで, 以下の条件をみたしているとする.

• $A$ は $Q$ 個のクエリにおいて固定である.
• $Q$ 個のクエリが先読みできる.
• $F(L,R)$ が求まっているとき, $F(L \pm 1, R), F(L, R \pm 1)$ が容易に求める.

このとき, $F(L_1, R_1), \dots, F(L_Q, R_Q)$ を合計 で $O(N \sqrt{Q})$ Time で求めることが出来る.

Code

class Mo:
    def __init__(self, N: int):
        """ 範囲が 0 以上 N "未満" の Mo's Algorithm の準備をする.

        Args:
            N (int): 範囲の上限 (N は含まない)
        """

        self.__N = N
        self.__query_count = 0
        self.left: list[int] = []
        self.right: list[int] = []

    @property
    def N(self) -> int:
        return self.__N

    @property
    def query_count(self) -> int:
        """ 現在登録されているクエリの数を出力する.

        Returns:
            int: 現在登録されているクエリの数
        """

        return self.__query_count

    def add_query(self, l: int, r: int):
        """ 閉区間 [l,r] に対するクエリを追加する.

        Args:
            l (int): 左端
            r (int): 右端
        """

        self.left.append(l)
        self.right.append(r + 1)
        self.__query_count += 1

    def calculate(self, add, delete, rem):
        """ クエリを処理する.

        Args:
            add (Callable[[int]]): add(k): 区間に k を追加する場合の処理
            delete (Callable[[int]]): delete(k): 区画から k を削除する場合の処理
            rem (Callable[[int]]): query(q): 第 q クエリ (add_query に追加した順) の処理
        """

        bucket_size = self.N // (min(self.N, int(self.query_count ** 0.5 + 0.5)))
        bucket_count = (self.N + bucket_size - 1) // bucket_size
        buckets = [[] for _ in range(bucket_count)]

        left = self.left
        right = self.right

        for q in range(self.query_count):
            buckets[left[q] // bucket_size].append(q)

        for i in range(bucket_count):
            buckets[i].sort(key = lambda q: right[q], reverse = i % 2)

        x = y = 0
        for bucket in buckets:
            for q in bucket:
                l = left[q]
                r = right[q]

                for i in range(x - 1, l - 1 , -1):
                    add(i)

                for j in range(y, r):
                    add(j)

                for i in range(x, l):
                    delete(i)

                for j in range(y - 1, r - 1, -1):
                    delete(j)

                x = l
                y = r
                rem(q)

    def calculate_noncommutative(self, add_left, add_right, delete_left, delete_right, rem):
        bucket_size = self.N // (min(self.N, int(self.query_count ** 0.5 + 0.5)))
        bucket_count = (self.N + bucket_size - 1) // bucket_size
        buckets = [[] for _ in range(bucket_count)]

        left = self.left
        right = self.right

        for q in range(self.query_count):
            buckets[left[q] // bucket_size].append(q)

        for i in range(bucket_count):
            buckets[i].sort(key=lambda q: right[q], reverse=i%2)

        x = y = 0
        for bucket in buckets:
            for q in bucket:
                l = left[q]
                r = right[q]

                for i in range(x, l):
                    delete_left(i)

                for i in range(x-1, l-1, -1):
                    add_left(i)

                for j in range(y, r):
                    add_right(j)

                for j in range(y-1, r-1, -1):
                    delete_right(j)

                x = l
                y = r
                rem(q)

Traceback (most recent call last):
  File "/opt/hostedtoolcache/Python/3.13.3/x64/lib/python3.13/site-packages/onlinejudge_verify/documentation/build.py", line 71, in _render_source_code_stat
    bundled_code = language.bundle(stat.path, basedir=basedir, options={'include_paths': [basedir]}).decode()
                   ~~~~~~~~~~~~~~~^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/opt/hostedtoolcache/Python/3.13.3/x64/lib/python3.13/site-packages/onlinejudge_verify/languages/python.py", line 96, in bundle
    raise NotImplementedError
NotImplementedError

Back to top page