题目题解

问题理解

给定一个长度为 $n$ 的数组 $a$，元素值在 $[0, m-1]$ 之间。
操作：选择一个元素 $a_i$，将其变为 $(a_i + k) \bmod m$。
两种查询：

• 1 i x：将 $a_i$ 修改为 $x$（持久化）。
• 2 k：询问能否通过若干次（包括零次）操作，使数组变为非递减（即 $a_1 \le a_2 \le \dots \le a_n$）。

每个查询 $2$ 独立，不实际修改数组。

---

第一步：可达值的特征

对于固定的 $k$，设 $g = \gcd(k, m)$。
经过若干次 $+k$ 操作，$a_i$ 只能变成与 $a_i$ 模 $g$ 同余的值。
并且所有与该余数同余的值都可以达到（因为 $\frac{k}{g}$ 与 $\frac{m}{g}$ 互质，可以生成模 $\frac{m}{g}$ 的完全剩余系，从而在 $\bmod m$ 下遍历该余数类）。

因此，每个 $a_i$ 的可选值集合是：

$$S_i = \{ x \in [0, m-1] \mid x \equiv a_i \pmod{g} \}. $$

---

第二步：贪心判定

要判断能否排成非递减，我们可以贪心地为每个位置选择最小的可行值，且不小于前一个位置的值。

设 $b_i$ 为位置 $i$ 最终选定的值。
贪心过程：

• $b_1$ 取 $S_1$ 中的最小值。
• 对于 $i \ge 2$，取 $S_i$ 中最小的大于等于 $b_{i-1}$ 的值。若不存在，则不可行。

这个贪心是最优的，因为每个位置独立，且尽量压低数值有利于后续。

---

第三步：等价转换

注意 $S_i$ 是模 $g$ 的某个剩余类，其元素可以按大小排序。
设 $r_i = a_i \bmod g$，则 $S_i = \{ r_i, r_i + g, r_i + 2g, \dots \}$。

贪心过程等价于：

• 若 $b_{i-1} \bmod g = r_i$，则 $b_i$ 可以取 $b_{i-1}$ 或更大的同余值（即 $b_{i-1}$ 本身已在 $S_i$ 中）。
• 若 $b_{i-1} \bmod g \ne r_i$，则必须从 $S_i$ 中取最小的数，即 $r_i$。此时若 $r_i < b_{i-1}$，则必须“上移一行”（即加 $g$ 直到 $\ge b_{i-1}$），这会增加“进位”次数。

更直观地，将 $0$ 到 $m-1$ 排成 $g$ 列（按模 $g$ 的余数分组），每组内从小到大排列。
例如 $k=8, m=12$，则 $g=4$，排列如下：

$$\begin{array}{cccc} 8 & 9 & 10 & 11 \\ 4 & 5 & 6 & 7 \\ 0 & 1 & 2 & 3 \end{array} $$

操作相当于在同一列内上下移动（每次加 $k$ 对应向上移动一行）。
贪心过程：我们希望尽可能停留在较低的格子（小的数值）。
当 $a_i$ 的列与前一列的列不同时，必须跳转到该列的最小行（即 $r_i$），若该值小于前一值，则需要向上移动若干行（即加若干次 $g$）。

---

第四步：维护关键量

设 $c$ 为必须向上移动的次数。
当遍历到第 $i$ 个元素时，若 $r_i < r_{i-1}$，则必须向上移动一次（因为要跳到下一列的顶部）。
实际上，$c$ 就是满足 $r_i < r_{i-1}$ 的 $i$ 的个数。

因为每次向上移动一行，数值增加 $g$。
最终 $b_n$ 的值为：

$$b_n = r_n + c \cdot g.$$

由于 $r_n < g$，且 $b_n < m$，所以可行的条件是 $c \cdot g < m$，即 $c < m/g$。

因此，回答查询 $2$ 只需检查：

$$\text{ans} = \left( \text{\# 满足 } (a_i \bmod g) < (a_{i-1} \bmod g) \text{ 的 } i \right) < \frac{m}{g}. $$

---

第五步：处理修改

我们需要快速回答不同 $g$（即 $m$ 的不同因子）的查询。

因为 $m \le 5\times 10^5$，其因子个数 $d(m)$ 最多约 $200$ 左右。
我们可以预先计算 $m$ 的所有因子，并维护每个因子 $d$ 对应的计数：

$$cnt[d] = \sum_{i=2}^n [ (a_i \bmod d) < (a_{i-1} \bmod d) ]. $$

当修改 $a_i$ 时，只会影响与 $a_{i-1}$ 和 $a_{i+1}$ 的比较，因此只需更新 $O(d(m))$ 个 $cnt$ 值。

回答查询时，取 $g = \gcd(k, m)$，检查 $cnt[g] < m/g$ 即可。

---

第六步：算法步骤

1. 预处理 $m$ 的所有因子。
2. 初始化 $cnt[d]$ 为满足条件的位置数。
3. 对于每个查询：
   • 若为 1 i x：更新 $a_i$，并更新 $cnt[d]$ 中涉及 $i-1$ 和 $i$ 的比较。
   • 若为 2 k：计算 $g = \gcd(k, m)$，输出 YES 若 $cnt[g] < m/g$，否则 NO。

---

时间复杂度

• 预处理因子：$O(\sqrt{m})$。
• 每次修改：$O(d(m))$。
• 每次查询：$O(1)$（计算 $\gcd$）。
• 总复杂度：$O((n+q) \cdot d(m))$，满足 $n,q \le 10^5$，$d(m) \le 200$，可行。

---

代码实现

#include <bits/stdc++.h>
using namespace std;

void solve() {
    int n, m, q;
    cin >> n >> m >> q;
    vector<int> a(n + 2);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    
    vector<int> divisors;
    for (int d = 1; d * d <= m; d++) {
        if (m % d == 0) {
            divisors.push_back(d);
            if (d != m / d) {
                divisors.push_back(m / d);
            }
        }
    }
    
    int D = divisors.size();
    vector<int> idx_map(m + 1, -1);
    for (int i = 0; i < D; i++) {
        idx_map[divisors[i]] = i;
    }
    
    vector<int> cnt(D, 0);
    vector<vector<int>> rem(n + 2, vector<int>(D));
    
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < D; j++) {
            rem[i][j] = a[i] % divisors[j];
        }
    }
    
    for (int j = 0; j < D; j++) {
        for (int i = 2; i <= n; i++) {
            if (rem[i][j] < rem[i-1][j]) {
                cnt[j]++;
            }
        }
    }
    
    while (q--) {
        int op;
        cin >> op;
        if (op == 1) {
            int i, x;
            cin >> i >> x;
            for (int j = 0; j < D; j++) {
                int new_rem = x % divisors[j];
                if (i > 1) {
                    if (rem[i][j] < rem[i-1][j]) cnt[j]--;
                    if (new_rem < rem[i-1][j]) cnt[j]++;
                }
                if (i < n) {
                    if (rem[i+1][j] < rem[i][j]) cnt[j]--;
                    if (rem[i+1][j] < new_rem) cnt[j]++;
                }
                rem[i][j] = new_rem;
            }
            a[i] = x;
        } else {
            int k;
            cin >> k;
            int g = __gcd(k, m);
            int idx = idx_map[g];
            cout << (cnt[idx] < m / g ? "YES\n" : "NO\n");
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    
    return 0;
}

---

总结

本题的关键在于：

1. 利用模 $\gcd(k, m)$ 的剩余类确定可达值集合。
2. 将问题转化为贪心过程中“向上移动”次数的统计。
3. 维护 $m$ 的所有因子对应的计数，实现快速修改和查询。