求分析复杂度

在统计答案的部分（区间加等差数列），我本意是先暴力加，再改成一阶差分，最后改为二阶差分，这样一步步来。

暴力加（注释掉的）只能过 Sub1 和 Sub3。改成一阶差分后（下面的代码），循环还是二维的，我觉得复杂度没变，但是直接过了，而且速度和二阶差分相差并不大。

所以我想问一问，暴力加改成一阶差分的这一步是否有复杂度上的优化，还是说是常数问题 / 数据问题？

一阶差分的代码：

CPP

for (int i = 1;i <= n;i++) {
    if (l[i] == -1) continue;
    int p = min(i - l[i], r[i] - i);
    int q = max(i - l[i], r[i] - i);
    // for (int j = 1;j <= p;j++) c[j - 1] += j * a[i];
    for (int j = 1;j <= p;j++) c[j - 1] += a[i], c[p] -= a[i];
    // for (int j = p + 1;j <= q;j++) c[j - 1] += p * a[i];
    c[p] += p * a[i], c[q] -= p * a[i];
    // for (int j = q + 1;j <= r[i] - l[i] - 1;j++) c[j - 1] += (r[i] - l[i] - j) * a[i];
    for (int j = q + 1;j <= r[i] - l[i] - 1;j++) c[q] += a[i], c[r[i] - l[i] - (j - q)] -= a[i];
}
for (int i = n + 1;i <= n + n;i++) {
    if (l[i] >= n) continue;
    int p = min(n - l[i], r[i] - i);
    int q = max(n - l[i], r[i] - i);
    // for (int j = 1;j <= p;j++) c[j - 1 + i - n] += j * a[i];
    for (int j = 1;j <= p;j++) c[j - 1 + i - n] += a[i], c[p] -= a[i];
    // for (int j = p + 1;j <= q;j++) c[j - 1 + i - n] += p * a[i];
    c[p + i - n] += p * a[i], c[q + i - n] -= p * a[i];
    // for (int j = q + 1;j <= r[i] - l[i] - 1;j++) c[j - 1 + i - n] += (r[i] - l[i] - j) * a[i];
    for (int j = q + 1;j <= r[i] - l[i] - 1;j++) c[q + i - n] += a[i], c[r[i] - l[i] - (j - q) + i - n] -= a[i];
}
for (int i = 1;i <= n + n;i++) c[i] += c[i - 1];
for (int i = 1;i <= n;i++)
    cout << c[i] << "\n";

讨论操作

回复

相关推荐

求分析复杂度