题目理解

我们有 $n$ 个位置，初始为 $0$。
执行 $k$ 次操作，每次操作 $(a, \ell, d)$ 表示在位置 $a, a+d, a+2d, \dots, a+(\ell-1)d$ 各加 $1$。
最后输出每个位置的总数。

---

问题转化

设最终数组为 $c_1, c_2, \ldots, c_n$，其中： [ c_i = \sum_{j=1}^k [\text{操作 }j\text{ 覆盖了位置 }i] ]

对于每个操作 $(a, \ell, d)$，它覆盖的位置集合是： [ {a, a+d, a+2d, \ldots, a+(\ell-1)d} ]

---

直接暴力做法

最直接的方法是：

for (int i = 0; i < l; i++)
    a[x + i * d]++;

这样一次操作复杂度是 $O(\ell)$，最坏情况 $\ell$ 可能接近 $n$，$k$ 次操作可能 $O(nk)$，会超时。

---

优化思路：阈值分治

关键观察：如果 $d$ 很大，那么 $\ell$ 会很小（因为 $a + (\ell-1)d \le n$），所以 $\ell \le \frac{n}{d}$。
因此对于 $d$ 很大的情况，直接循环加是可以的，因为 $\ell$ 很小。

问题在于 $d$ 很小的情况，例如 $d=1$，$\ell$ 可能很大，直接循环会超时。

---

差分数组技巧

对于 $d$ 较小的情况，我们可以用"按模分类的差分数组"来优化。

设 $s[d][j]$ 表示在模 $d$ 的剩余类中，起始位置 $j$ 的差分标记。
对于一次操作 $(a, \ell, d)$，如果 $d \le B$，我们就在 $s[d][a]$ 加 $1$，在 $s[d][a + \ell \cdot d]$ 减 $1$。

之后，对于每个 $d$，我们按模 $d$ 的剩余类分别做前缀和：

for (int r = 0; r < d; r++) {
    for (int j = r; j <= n; j += d) {
        if (j >= d) s[d][j] += s[d][j - d];
        a[j] += s[d][j];
    }
}

这样对于每个 $d$，复杂度是 $O(n)$，总复杂度 $O(B \cdot n)$。

---

阈值选择与复杂度分析

我们取阈值 $B$，当 $d \le B$ 时用差分法，当 $d > B$ 时直接循环。

直接循环的复杂度分析：
对于 $d > B$，$\ell \le \frac{n}{d} < \frac{n}{B}$，所以总操作次数 $k \cdot \frac{n}{B}$。

因此总复杂度为： [ O\left(B \cdot n + k \cdot \frac{n}{B}\right) ] 取 $B \approx \sqrt{k}$ 或 $\sqrt{n}$ 可以平衡。这里代码取 $B = 300$，因为 $n,k \le 10^5$，这样 $B \cdot n \approx 3\times 10^7$，可以接受。

---

代码实现详解

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

const int N = 1e5 + 1e3 + 7, B = 300;  // N 略大于 n 最大值，B 是阈值

int n, k;
int a[N];  // 最终答案数组
int s[B + 1][N];  // s[d][j] 用于 d <= B 的差分标记

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> k;

    while (k--) {
        int x, l, d;
        cin >> x >> l >> d;

        if (d <= B) {
            // 使用差分标记：在起始位置加1，在结束位置的下一个位置减1
            s[d][x]++;
            if (x + l * d <= n)
                s[d][x + l * d]--;
        } else {
            // 直接循环加：因为d大时l小
            for (int i = 0; i < l; i++)
                a[x + i * d]++;
        }
    }

    // 对每个 d <= B，按剩余类做前缀和
    for (int d = 1; d <= B; d++) {
        for (int r = 0; r < d; r++) {  // 枚举每个剩余类
            for (int j = r; j <= n; j += d) {  // 在同一个剩余类中做前缀和
                if (j >= d) 
                    s[d][j] += s[d][j - d];
                a[j] += s[d][j];
            }
        }
    }

    // 输出结果
    for (int i = 1; i <= n; i++)
        cout << a[i] << " \n"[i == n];
}

---

算法正确性分析

小 $d$ 情况：
对于每个 $d \le B$，我们使用差分数组 $s[d]$。操作 $(a, \ell, d)$ 在 $s[d][a]$ 处 $+1$，在 $s[d][a+\ell d]$ 处 $-1$。
当按剩余类做前缀和时，对于每个剩余类 $r$，$s[d][r], s[d][r+d], s[d][r+2d], \ldots$ 会正确累加，使得从位置 $a$ 到 $a+(\ell-1)d$ 的每个位置都 $+1$。

大 $d$ 情况：
由于 $\ell \le \frac{n}{d} < \frac{n}{B}$，直接循环的代价是可接受的。

---

算法标签

• 阈值分治：根据 $d$ 的大小采用不同策略
• 差分数组：对小的 $d$ 使用模意义下的差分
• 直接枚举：对大的 $d$ 直接循环
• 数论：利用模运算性质优化

---

时间复杂度

• 小 $d$ 部分：$O(B \cdot n)$
• 大 $d$ 部分：$O(k \cdot \frac{n}{B})$
• 总复杂度：$O(B \cdot n + k \cdot \frac{n}{B})$，取 $B = \sqrt{k}$ 时为 $O(n\sqrt{k})$

对于 $n,k \le 10^5$，这是可以接受的。

---

总结

本题通过阈值分治巧妙解决了等差数列区间加问题：

对稀疏访问（大 $d$）采用直接枚举

对密集访问（小 $d$）采用差分技巧

这种思想在解决类似"根据参数特征选择不同算法"的问题时非常有用，是算法竞赛中的经典优化模式。