Author: lllyouo
Date: 20250822
tag: 差分
link:

问题描述

对于长度为 $n(1\le n\le {10}^6)$ 初始全为 $0$ 的数组 $a$，有 $m(1\le m\le {10}^6)$ 个操作，每次操作给区间 $[L,R]$ 中的每个位置 $i$ 加上 $(i-L+1{)}^2$。求最终数组 $a$。

分析

考察知识点：差分和多项式展开

对于一次操作 $[L,R]$，设 $len=R-L+1$，对于位置 $i$ ($L\le i\le R$)，增加值为：

$$(i-L+1{)}^2=(i-(L-1){)}^2=i^2-2(L-1)i+(L-1{)}^2$$

所以这次操作可以分解为：

1. 给区间 $[L,R]$ 的每个位置加上 $i^2$
2. 给区间 $[L,R]$ 的每个位置减去 $2(L-1)i$
3. 给区间 $[L,R]$ 的每个位置加上 $(L-1{)}^2$

使用三个差分数组：

• d0：记录常数项的差分
• d1：记录一次项系数的差分
• d2：记录二次项系数的差分

对于操作 $[L,R]$：

1. 二次项部分：区间 $[L,R]$ 加 $1$（系数为 $1$）
2. 一次项部分：区间 $[L,R]$ 加 $-2(L-1)$（系数为 $-2(L-1)$）
3. 常数项部分：区间 $[L,R]$ 加 $(L-1{)}^2$

最后通过积分还原原数组：

$$a_i=d{2}_i\cdot i^2+d{1}_i\cdot i+d{0}_i$$

参考代码

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

typedef long long ll;
const int N = 1000005, MOD = 998244353;

ll d0[N], d1[N], d2[N];

void add(int l, int r, ll val0, ll val1, ll val2) {
    d0[l] = (d0[l] + val0) % MOD;
    d0[r + 1] = (d0[r + 1] - val0 + MOD) % MOD;

    d1[l] = (d1[l] + val1) % MOD;
    d1[r + 1] = (d1[r + 1] - val1 + MOD) % MOD;

    d2[l] = (d2[l] + val2) % MOD;
    d2[r + 1] = (d2[r + 1] - val2 + MOD) % MOD;
}

int main() {
    int n, m;
    scanf("%d%d", &n, &m);

    for (int i = 0; i < m; i++) {
        int L, R;
        scanf("%d%d", &L, &R);
        int len = R - L + 1;
        ll c = L - 1; // c = L-1

        // 分解为: i^2 - 2c*i + c^2
        add(L, R, (c * c) % MOD, (-2 * c % MOD + MOD) % MOD, 1);
    }

    // 计算前缀和
    for (int i = 1; i <= n; i++) {
        d0[i] = (d0[i] + d0[i - 1]) % MOD;
        d1[i] = (d1[i] + d1[i - 1]) % MOD;
        d2[i] = (d2[i] + d2[i - 1]) % MOD;
    }

    // 计算最终结果: a_i = d2[i] * i^2 + d1[i] * i + d0[i]
    for (int i = 1; i <= n; i++) {
        ll t = (d2[i] * i % MOD * i % MOD + d1[i] * i % MOD + d0[i]) % MOD;
        printf("%lld ", t);
    }

    return 0;
}