Argestes and Sequence

预备知识：如何获取数字的第 D 位

题目中规定第 1 位是最低位（个位）。数字 $V$ 的第 $D$ 位可以通过以下公式计算： $(V / 10^{D-1}) \% 10$

由于 $D$ 最大为 10，我们可以预处理 $10$ 的幂次来加速计算。

cpp

long long powers[11];
void precompute_powers() {
    powers[1] = 1;
    for (int i = 2; i <= 10; ++i) powers[i] = powers[i - 1] * 10;
}

// 获取 val 的第 D 位数字
inline int get_digit(long long val, int D) {
    return (val / powers[D]) % 10;
}

方法一：树状数组 (BIT)

树状数组擅长处理单点修改和区间前缀和查询。这里的查询条件是“第 $D$ 位是 $P$ ”，这并不是一个直接的数值求和。

核心思想： 我们可以建立多个树状数组。具体来说，对于每一个可能的位数 $D$ ( $1 \le D \le 10$ ) 和每一个可能的数字 $P$ ( $0 \le P \le 9$ )，我们都建立一个树状数组。记 tree[D][P] 为一个树状数组。如果原数组 $a[i]$ 的第 $D$ 位是 $P$ ，那么我们在 tree[D][P] 的位置 $i$ 上加上 1。

这样，查询区间 $[L, R]$ 内第 $D$ 位是 $P$ 的数字个数，就转化为了在 tree[D][P] 上查询区间 $[L, R]$ 的和，即 query(tree[D][P], R) - query(tree[D][P], L-1)。

复杂度分析：

空间复杂度：我们需要 $10 \times 10 = 100$ 个大小为 $N$ 的树状数组。总空间约为 $100 \times 10^5 \times 4$ 字节 $\approx 40$ MB，是可以接受的。
时间复杂度：
- 初始化：遍历 $N$ 个数，对每个数更新 10 个 BIT，总共 $O(N \log N \times 10)$ 。
- 修改 (S X Y)：修改一个数涉及到在 10 个 BIT 中减去旧值的贡献，并加上新值的贡献。总共 $O(\log N \times 20)$ 。
- 查询 (Q L R D P)：只需要在指定的一个 BIT 上进行两次查询。总共 $O(\log N)$ 。
- 总时间复杂度为 $O((N + M) \log N)$ ，常数较大但足以通过。

特征数组思想

你的理解非常准确，完全正确！

这正是这个解法的核心思想。你已经抓住了问题的本质。

让我用更正式一点的语言把你的想法再梳理一遍，加深印象：

1. 核心思想：特征数组 (Indicator Array)

你提到的“桶”或者那个 [1 1 1 0 0 0] 的数组，在算法中通常被称为特征数组或者指示器数组。

对于题目中的每一个特定的查询要求——“第 $D$ 位是 $P$ ”，我们可以想象存在一个概念上的布尔数组（只包含 0 和 1），记作 $B_{D,P}$ 。

数组 $B_{D,P}$ 的定义如下：对于原数组 $a$ 中的第 $i$ 个元素 $a[i]$ ：

如果 $a[i]$ 的第 $D$ 位恰好是 $P$ ，那么 $B_{D,P}[i] = 1$ 。
如果 $a[i]$ 的第 $D$ 位不是 $P$ ，那么 $B_{D,P}[i] = 0$ 。

举个例子： 假设原数组 $a = [123, 456, 128, 789, 421]$ 我们关注：第 2 位（十位）是 2 的数字。即 $D=2, P=2$ 。

$a[1]=1\textbf{2}3 \rightarrow$ 符合 $\rightarrow B_{2,2}[1] = 1$
$a[2]=456 \rightarrow$ 不符 $\rightarrow B_{2,2}[2] = 0$
$a[3]=1\textbf{2}8 \rightarrow$ 符合 $\rightarrow B_{2,2}[3] = 1$
$a[4]=789 \rightarrow$ 不符 $\rightarrow B_{2,2}[4] = 0$
$a[5]=4\textbf{2}1 \rightarrow$ 符合 $\rightarrow B_{2,2}[5] = 1$

那么，概念上的特征数组 $B_{2,2}$ 就是 [1, 0, 1, 0, 1]。

2. 问题的转化

题目要求查询：在区间 $[L, R]$ 内，有多少个数字满足“第 $D$ 位是 $P$ ”。

转化到特征数组 $B_{D,P}$ 上，这个问题就变成了： 求特征数组 $B_{D,P}$ 在区间 $[L, R]$ 内的元素和。

即： $\sum_{i=L}^{R} B_{D,P}[i]$ 。

因为满足条件的记为 1，不满足的记为 0，所以它们的和就是满足条件的个数。

3. BIT 的角色：动态维护区间和

现在问题变成了我们最熟悉的形式：单点修改，区间求和。

如果数组 $B_{D,P}$ 是静态不变的，我们可以用前缀和数组在 $O(1)$ 时间内求出区间和。

但题目有修改操作（S X Y）：将 $a[X]$ 改为 $Y$ 。这意味着 $a[X]$ 的各个位上的数字可能会变，从而导致多个特征数组在位置 $X$ 上的值（0 或 1）发生变化。

如果用原始数组维护 $B_{D,P}$ ，修改是 $O(1)$ ，但区间求和是 $O(N)$ ，太慢。
如果用前缀和数组维护 $B_{D,P}$ ，区间求和是 $O(1)$ ，但修改是 $O(N)$ ，太慢。

这时候，树状数组 (BIT) 就登场了。它正是为了平衡这两者而生的数据结构。

你所说的 tree[D][P]，实际上就是基于特征数组 $B_{D,P}$ 构建的树状数组。

当我们在 $a[X]$ 的第 $D$ 位上观察到数字 $P$ 时，我们在概念上把 $B_{D,P}[X]$ 设为了 1。在代码里，我们就执行 bit_update(tree[D][P], X, 1)。
当我们查询区间 $[L, R]$ 时，我们实际上是在求特征数组的区间和，代码里就是 bit_query(tree[D][P], R) - bit_query(tree[D][P], L - 1)。

总结

你的想法非常透彻。

这个解法就是把一个复杂的复合条件查询，通过特征化（变成 0/1 数组）转化为标准的区间求和问题，然后因为需要支持动态修改，所以引入了树状数组来维护这个求和过程。

C++ 代码实现 (BIT)：

cpp

#include <iostream>
#include <vector>
#include <cstdio>
#include <cstring>

using namespace std;

// --- 快读快写模板 ---
inline int read() {
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
    return x * f;
}
inline long long readll() {
    long long x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
    return x * f;
}
inline void write(int x) {
    if (x > 9) write(x / 10);
    putchar(x % 10 + '0');
}
// --------------------

const int MAXN = 100005;
long long a[MAXN]; // 原数组
int n, m;
int tree[11][10][MAXN]; // 100个树状数组：tree[D][P][idx]
long long powers[11];   // 预存10的幂

void precompute_powers() {
    powers[1] = 1;
    for (int i = 2; i <= 10; ++i) powers[i] = powers[i - 1] * 10;
}

inline int get_digit(long long val, int D) {
    return (val / powers[D]) % 10;
}

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

// 在指定的 BIT 上进行更新
void bit_update(int d, int p, int idx, int val) {
    for (; idx <= n; idx += lowbit(idx)) {
        tree[d][p][idx] += val;
    }
}

// 在指定的 BIT 上进行前缀和查询
int bit_query(int d, int p, int idx) {
    int sum = 0;
    for (; idx > 0; idx -= lowbit(idx)) {
        sum += tree[d][p][idx];
    }
    return sum;
}

void solve() {
    n = read(); m = read();
    memset(tree, 0, sizeof(tree)); // 多组数据，切记清空
    for (int i = 1; i <= n; ++i) {
        a[i] = readll();
        // 初始化 BIT，对每个位置的每一位进行记录
        for (int d = 1; d <= 10; ++d) {
            bit_update(d, get_digit(a[i], d), i, 1);
        }
    }

    char type[2];
    for (int k = 0; k < m; ++k) {
        scanf("%s", type);
        if (type[0] == 'S') { // 修改操作
            int x = read();
            long long y = readll();
            long long old_val = a[x];
            // 1. 移除旧值的贡献
            for (int d = 1; d <= 10; ++d) {
                bit_update(d, get_digit(old_val, d), x, -1);
            }
            a[x] = y; // 更新原数组
            // 2. 添加新值的贡献
            for (int d = 1; d <= 10; ++d) {
                bit_update(d, get_digit(y, d), x, 1);
            }
        } else { // 查询操作
            int l = read(), r = read(), d = read(), p = read();
            // 利用区间减法原理查询
            int ans = bit_query(d, p, r) - bit_query(d, p, l - 1);
            write(ans);
            putchar('\n');
        }
    }
}

int main() {
    precompute_powers(); // 预处理
    int t = read();
    while (t--) {
        solve();
    }
    return 0;
}

方法二：分块 (Square Root Decomposition)

分块是一种通用性很强的方法，特别适合处理一些树状数组或线段树不好维护的复杂区间信息。

核心思想：

本质: 区间信息是什么 ask(l,r,d,p) , 可以用这个来统计区间信息,关键字d,p, $d \times p = 10 \times 10 = 100$ ,任何一个区间的信息可以使用长度为100的数组存下. 使用分块来进行暴力优化

将数组 $a$ 分成 $\sqrt{N}$ 个块，每个块的大小约为 $\sqrt{N}$ 。对于每一个块，我们维护一个统计数组 cnt[block_id][D][P]，表示在第 block_id 个块中，第 $D$ 位是 $P$ 的数字有多少个。

修改 (S X Y)：找到 $X$ 所在的块，更新该块的 cnt 数组。先减去旧值 $a[X]$ 在各个位上的计数，然后更新 $a[X]=Y$ ，再加上新值 $Y$ 在各个位上的计数。复杂度 $O(10)$ 。
查询 (Q L R D P)：查询区间 $[L, R]$ 可能跨越多个块。
- 对于两端不完整的块（散块），直接暴力遍历原数组 $a$ 进行统计。复杂度 $O(\sqrt{N})$ 。
- 对于中间完整的块，直接累加预处理好的 cnt[block_id][D][P]。复杂度 $O(\sqrt{N})$ 。