ABC206 D — KAIBUNsyo

1# -*- coding: utf-8 -*-2 3 4class UnionFind:5    """Represents a data structure that tracks a set of elements partitioned6       into a number of disjoint (non-overlapping) subsets.7    Landau notation: O(α(n)), where α(n) is the inverse Ackermann function.8    See:9    https://www.youtube.com/watch?v=zV3Ul2pA2Fw10    https://en.wikipedia.org/wiki/Disjoint-set_data_structure11    https://atcoder.jp/contests/abc120/submissions/444494212    """13 14    def __init__(self, number_count: int):15        """16        Args:17            number_count: The size of elements (greater than 2).18        """19        self.parent_numbers = [-1 for _ in range(number_count)]20        self._number_count = number_count21 22    def find_root(self, number: int) -> int:23        """Follows the chain of parent pointers from number up the tree until24           it reaches a root element, whose parent is itself.25        Args:26            number: The trees id (0-index).27        Returns:28            The index of a root element.29        """30        if self.parent_numbers[number] < 0:31            return number32 33        self.parent_numbers[number] = self.find_root(self.parent_numbers[number])34        return self.parent_numbers[number]35 36    def get_group_size(self, number: int) -> int:37        """38        Args:39            number: The trees id (0-index).40        Returns:41            The size of group.42        """43        return -self.parent_numbers[self.find_root(number)]44 45    def is_same_group(self, number_x: int, number_y: int) -> bool:46        """Represents the roots of tree number_x and number_y are in the same47           group.48        Args:49            number_x: The trees x (0-index).50            number_y: The trees y (0-index).51        """52        return self.find_root(number_x) == self.find_root(number_y)53 54    def merge_if_needs(self, number_x: int, number_y: int) -> bool:55        """Uses find_root to determine the roots of the tree number_x and56           number_y belong to. If the roots are distinct, the trees are combined57           by attaching the roots of one to the root of the other.58        Args:59            number_x: The trees x (0-index).60            number_y: The trees y (0-index).61        """62        x = self.find_root(number_x)63        y = self.find_root(number_y)64 65        if x == y:66            return False67 68        if self.get_group_size(x) >= self.get_group_size(y):69            self.parent_numbers[x] += self.parent_numbers[y]70            self.parent_numbers[y] = x71        else:72            self.parent_numbers[y] += self.parent_numbers[x]73            self.parent_numbers[x] = y74        return True75 76 77def main():78    import sys79 80    input = sys.stdin.readline81 82    n = int(input())83    a = list(map(int, input().split()))84    m = 2 * 10 ** 5 + 1085    uf = UnionFind(m)86    ans = 087 88    for i in range(n):89        ans += uf.merge_if_needs(a[i], a[n - i - 1])90 91    print(ans)92 93 94if __name__ == "__main__":95    main()96