---
title: "AtCoder Beginner Contest 242 G(莫隊)"
tags: 題解, 離線
---

https://atcoder.jp/contests/abc242/tasks/abc242_g

#### 題意

給 $N$ 個數 $a_1, a_2, ..., a_N$，每個數的範圍在 $1$ ~ $N$ 之間。給 $Q$ 個查詢，每個查詢是 $l$ 和 $r$，求 $a_l, ..., a_r$ 中，有多少組 pair ($a_i$, $a_j$) 滿足 $a_i = a_j$，其中每個 $a_i$ 不可重複使用。

#### 思路

對於區間 $(L, R)$，假設我們知道它的答案，則可以用很快的速度得知相鄰的區間 $(L-1, R)$、$(L+1, R)$、$(L,R-1)$、$(L, R+1)$ 的答案（how: 維護各數字出現的頻率）。因此這題可以用莫隊做。

用莫隊時只需要寫好 $add(i)$、$remove(i)$、$out(i)$ 即可。
- $add(i)$：將該數字頻率加一，若頻率原本是奇數則答案加一
- $remove(i)$：將該數字頻率減一，若頻率變為奇數則答案減一
- $out(i)$：即目前的答案個數

複雜度為 $O(N\sqrt{Q})$。

#### Code

class Mo:
    def __init__(self, n):
        self.n = n
        self.q = 0

        self.queries = []

    def add_query(self, ql, qr):
        # [ql, qr]
        self.queries.append((ql, qr))
        self.q += 1

    def solve(self):
        def add(idx):
            nonlocal cur
            cur += freq[A[idx]] & 1
            freq[A[idx]] += 1

        def remove(idx):
            nonlocal cur
            freq[A[idx]] -= 1
            cur -= freq[A[idx]] & 1

        def out(idx):
            ans[idx] = cur

        queries = self.queries
        SZ = 128
        NUM = (self.n + SZ - 1) // SZ
        B = [[] for _ in range(NUM)]

        for qi, (ql, qr) in enumerate(queries):
            B[ql // SZ].append(qi)

        for bi in range(NUM):
            B[bi].sort(key=lambda qi: queries[qi][1], reverse=bi & 1)

        L, R = 0, -1
        ans = [0 for _ in range(self.q)]

        cur = 0
        freq = [0 for _ in range(self.n + 1)]

        for qis in B:
            for qi in qis:
                ql, qr = queries[qi]
                for i in range(L, ql):
                    remove(i)
                for i in range(L - 1, ql - 1, -1):
                    add(i)
                for i in range(R + 1, qr + 1):
                    add(i)
                for i in range(R, qr, -1):
                    remove(i)
                L, R = ql, qr
                out(qi)
        return ans

def solve():
    N = int(input())

    global A
    A = list(map(int, input().split()))

    mo = Mo(N)

    Q = int(input())
    for _ in range(Q):
        l, r = map(int, input().split())
        l -= 1; r -= 1
        mo.add_query(l, r)

    ans = mo.solve()
    print(*ans, sep="\n")

if __name__ == "__main__":
    solve()