題目的難度顏色使用 Luogu 上的分級，由簡單到困難分別為 🔴🟠🟡🟢🔵🟣⚫。

🔗 CF1791F. Range Update Point Query

tags: `二分搜尋(Binary Search)` `併查集(Disjoint Set Union)`

題意

給定一個陣列 $a_1, a_2, \dots, a_n$ ，你需要處理總共 $q$ 個更新和查詢，共有兩種型別：

1 l r — 對於每個索引 $i$ ，滿足 $l \leq i \leq r$ ，將 $a_i$ 的值更新為 $a_i$ 的各位數字之和。
2 x — 輸出 $a_x$ 。

思路：區間併查集 + 暴力

注意到 數字一旦 $\leq 9$ ，就不會再發生變化，因此我們可以利用區間併查集來維護所有 $> 9$ 的數字下標。之後對於每個查詢 1 l r，我們只需要將 $l$ 到 $r$ 的數字都更新一次即可，並透過區間併查集，跳過已經 $\leq 9$ 的數字。

具體來說，可以利用併查集來維護一個下標集合，初始情況下每個位置都存在。如果某個位置的數字更新之後變成 $\leq 9$ ，就意味著該位置已經不再需要更新，可以「刪除」該位置。這裡刪除的實現方式是：將該位置與其右鄰合併，使得後續從該位置查找時能直接跳到下一個還需要操作的位置。

而將一個數字 $x$ 更新為其各位數字之和後，數值會大幅減少，由於 $x$ 的位數為 $\log_{10}(x)$ ，因此其值最大為 $9\cdot \log_{10}(x)$ 。因此對於每個數字而言，進行 $O(\log^* x)$ 次更新後就必然 $\leq 9$ ，這就保證了每個數字參與暴力更新的次數十分有限，可以認為是常數級別。

複雜度分析

時間複雜度： $O((n+q) \cdot \alpha(n))$ ，其中 $\alpha(n)$ 是阿克曼函數的反函數，可以視為常數。
空間複雜度： $O(n)$

python

class UnionFind:
    __slots__ = ['n', 'pa']

    def __init__(self, n: int):
        self.n = n
        self.pa = list(range(n)) # 父節點

    def find(self, x: int) -> int:
        while self.pa[x] != x:
            self.pa[x] = self.pa[self.pa[x]]
            x = self.pa[x]
        return x

    def union(self, x: int, y: int) -> bool:
        fx, fy = self.find(x), self.find(y)
        if fx == fy:
            return False
        self.pa[fx] = fy
        return True

def calc(x):
    res = 0
    while x:
        res += x % 10
        x //= 10
    return res

t = int(input())

for _ in range(t):
    n, q = map(int, input().split())
    A = list(map(int, input().split()))
    uf = UnionFind(n + 1)
    for _ in range(q):
        op, *args = map(int, input().split())
        if op == 1:
            l, r = map(lambda x : x - 1, args)
            idx = uf.find(l)
            while (idx <= r):
                A[idx] = calc(A[idx])
                if A[idx] < 10:
                    uf.union(idx, idx + 1)  # 向右合併
                idx = uf.find(idx + 1)
        else:
            idx = args[0] - 1
            print(A[idx])

寫在最後

PROMPT

masterpiece, best quality, high quality, highres, extremely detailed CG unity 8k wallpaper, extremely detailed, High Detail, vibrant colors, anime style, cover art,

1girl, solo, Koyori, Hakui Koyori, Hakui Koyori (hololive), pink hair, long hair, braids in hair, purple eyes, fox ears, fox tail, black choker, white short-sleeved blouse, pink bow, pink trim on blouse, pink and purple plaid pleated skirt, white thigh garter on left leg, white knee-high socks, lace-trimmed socks, brown loafers,

reaching up to touch cherry blossoms, sitting on stone wall, spring season, cherry blossom trees in full bloom, soft dreamy lighting, urban background with buildings, gentle breeze, sakura petals falling, peaceful atmosphere, outdoors, clear spring day, looking up with wonder

In this enchanting spring scene, Hakui Koyori sits gracefully on a stone wall beneath a canopy of blooming cherry trees. The soft pink petals create a dreamlike atmosphere around her as she reaches up with one hand to gently touch the blossoms. Her expression captures a moment of serene wonder as she gazes upward at the beautiful sakura, with delicate petals occasionally drifting down in the gentle spring breeze.

和上禮拜週賽Q4一樣，都是區間併查集的應用。