暴力做法不可行，考虑线段树。

有过线段树刷题的同学可能一眼就看出来是线段树板子题，就是一个区间修改和区间查询的模板。

注意这里卡掉了不加优化的线段树做法。

考虑 $f(x)$ 函数，它作用后 $x$ 的值变化非常快，几乎几次就会变为个位数，我们发现当它成为个位数时 $f(x)$ 函数就没用了。

我们就需要加入一个优化，让我们修改的次数减少一些。即维护区间最大值，只要当前这个区间的最大值都小于 $10$ 了，那么直接不修改这个区间的所有数直接返回。

所以线段树需要维护的值为：

• 最小值
• 最大值
• $x$ 的值

其他操作就和板子操作一样了。具体看提交代码细节。

ps：经过测试输入输出太多，不关闭同步流会跑 $1400ms$，故而时限是 $2s$

时间复杂度 $O((n+m)\log(n))$

#include <bits/stdc++.h>

using u32 = unsigned;
using i64 = long long;
using u64 = unsigned long long;
using i128 = __int128;

constexpr i64 INF = 2e18;

int f(i64 x) {
	int res = 0;
	while (x) {
		res += x % 10;
		x /= 10;
	}
	return res;
}

#define ls u << 1
#define rs u << 1 | 1

template<class Info>
struct SegmentTree {
	int n;
	std::vector<Info> tr;
	SegmentTree(int _): n(_), tr(_ << 2) {}
	SegmentTree(std::vector<i64> a): SegmentTree(int(a.size() - 1)) {
		std::function<void(int, int, int)> build = [&](int u, int l, int r) -> void {
			if (l == r) {
				tr[u] = {l, r, 1, a[l], a[l], a[l]};
				return;
			}
			tr[u] = {l, r};
			int mid = (l + r) >> 1;
			build(ls, l, mid), build(rs, mid + 1, r);
			pushup(u);
		};
		build(1, 1, n);
	}

	void apply(int u, int v) {
		tr[u].apply(v);
	}

	void pushup(int u) {
		tr[u] = tr[ls] + tr[rs];
	}

	void modify(int u, int l, int r) {
		if (tr[u].l == tr[u].r) {
			apply(u, 0);
			return;
		}
		if (l <= tr[u].l && tr[u].r <= r && tr[u].max < 10) return;
		int mid = (tr[u].l + tr[u].r) >> 1;
		if (l <= mid) {
			modify(ls, l, r);
		} 
		if (r > mid) {
			modify(rs, l, r);
		}
		pushup(u);
	}

	Info query(int u, int l, int r) {
		if (l <= tr[u].l && tr[u].r <= r) {
			return tr[u];
		}
		if (r <= tr[ls].r) {
			return query(ls, l, r);
		} else if (l >= tr[rs].l) {
			return query(rs, l, r);
		} else {
			return query(ls, l, r) + query(rs, l, r);
		}
	}
};


struct Info {
	int l, r, cnt;
	i64 min, max, v;
	void apply(int x) {
		v = f(v);
		min = max = v;
	}
};

Info operator+(Info a, Info b){
    Info res {};
    res.l = a.l;
    res.r = b.r;
    res.cnt = a.cnt + b.cnt;
    res.min = std::min(a.min, b.min);
    res.max = std::max(a.max, b.max);
    return res;
}

int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);

	int n;
	std::cin >> n;
	std::vector<i64> a(n + 1);
	for (int i = 1; i <= n; i++) {
		std::cin >> a[i];
	}
	SegmentTree<Info> seg(a);
	int m;
	std::cin >> m;
	while (m--) {
		int op, l, r;
		std::cin >> op >> l >> r;
		if (op == 1) {
			seg.modify(1, l, r);
		} else {
			std::cout << seg.query(1, l, r).min << '\n';
		}
	}

	return 0;
}