题目描述

难度分:$1500$

输入$T(\leq 10^3)$表示$T$组数据。所有数据的$n$之和$\leq 2 \times 10^5$，$q$之和$\leq 2 \times 10^5$。

每组数据输入$n$、$q(1 \leq n,q \leq 2 \times 10^5)$和长为$n$的数组$a(1 \leq a[i] \leq 10^9)$。下标从$1$开始。

然后输入$q$个询问，格式如下：

• 1 l r：把下标在$[l,r]$中的数都更新成其数位和，例如$a[i]=420$，更新成$a[i]=4+2+0=6$。
• 2 x：输出$a[x]$。

输入样例

3
5 8
1 420 69 1434 2023
1 2 3
2 2
2 3
2 4
1 2 5
2 1
2 3
2 5
2 3
9999 1000
1 1 2
2 1
2 2
1 1
1
2 1

输出样例

6
15
1434
1
6
7
36
1
1

算法

树状数组实现差分数组

比较容易发现的一点就是，一个数进行不了几次用数位和代替自己的操作就会变成一位数。如此一来，再进行这样的操作也不会再改变自身的值了。

可以用一个树状数组$tr$来实现差分数组。执行操作一，就在树状数组的$l$位置加$1$，$r+1$位置减$1$，相当于执行区间$[l,r]$上的区间加法；执行操作二就求前缀$[1,x]$上的累加和，就是一次对树状数组$tr$的单点查询操作，查询出来的结果就是$x$位置执行了多少次操作。假设$cnt$次，就直接暴力对$a[x]$执行$cnt$次操作再输出答案就可以了，注意$cnt$可能很大，这时候在$a[x]$变成一位数的时候就停止操作。

复杂度分析

时间复杂度

处理每个询问需要对树状数组执行单点修改或查询前缀和，时间复杂度都是$O(log_2n)$的。对于操作二，还需要对$a[x]$真实执行操作，可以看成是一个比较大的常数，忽略不计。因此，整个算法的时间复杂度为$O(qlog_2n)$。

空间复杂度

除了输入的数组，空间消耗的瓶颈就是树状数组，因此额外空间复杂度为$O(n)$。

C++ 代码

#include <bits/stdc++.h>

using namespace std;
int t, n, q;

class Fenwick {
public:
    explicit Fenwick(int n): sums_(n + 1) {}

    int lowbit(int x) {
        return x&-x;
    }

    void add(int idx, int val) {
        for(++idx; idx < sums_.size(); idx += lowbit(idx)) {
            sums_[idx] += val;
        }
    }

    int query(int idx) {
        int ans = 0;
        for(++idx; idx > 0; idx -= lowbit(idx)) {
            ans += sums_[idx];
        }
        return ans;
    }

    int query(int left, int right) {
        return query(right) - query(left - 1);
    }

private:
    vector<int> sums_;
};

int dfs(int cur, int depth) {
    if(depth == 0 || cur < 10) return cur;
    int nxt = 0;
    while(cur) {
        nxt += cur % 10;
        cur /= 10;
    }
    return dfs(nxt, depth - 1);
}

int main() {
    scanf("%d", &t);
    while(t--) {
        scanf("%d%d", &n, &q);
        vector<int> nums;
        for(int i = 1; i <= n; i++) {
            int a;
            scanf("%d", &a);
            nums.push_back(a);
        }
        Fenwick tr(n + 5);
        while(q--) {
            int typ;
            scanf("%d", &typ);
            if(typ == 1) {
                int l, r;
                scanf("%d%d", &l, &r);
                l--, r--;
                tr.add(l, 1);
                tr.add(r + 1, -1);
            }else {
                int x;
                scanf("%d", &x);
                int cnt = tr.query(x - 1);
                printf("%d\n", dfs(nums[x - 1], cnt));
            }
        }
    }
    return 0;
}