P4231. 三步必殺

等差數列差分問題

給定一個數組 $[0, 0, 0, 0, 0, 0, 0, 0, 0]$ ，每次操作會給五個個數字(l, r, s, e, d)，
代表開頭，結尾，首項，末項，以及差。
假如給定 $(2, 6, 4, 16, 3)$ ，就從位置 2 開始，每次往後加數字。

轉換成用變數表示：$[0, 0, s, s+d, s+2d, s+3d, e, 0]$ 那麼，假如對這組數字做差分，會變成甚麼樣子？

• 一次差分：$[0, 0, s, d, d, d, d, -e, 0]$
• 再次差分：$[0,0,s,d-s,0,0,0,-e-d, e]$

也就是說，想要得到答案，只需要創建一個二次差分的數組，做兩次前綴和，就能得到目標數組。

程式碼

#include <iostream>
#include <climits>
using namespace std;

const int MX = 1e7+5;
long long diff[MX]{};

void set(int l, int r, int s, int e, int d) { // 更新二重差分數組
    diff[l] += s;
    diff[l + 1] += d - s;
    diff[r + 1] -= d + e;
    diff[r + 2] += e;
}

void build(int n) { // 做兩次前綴和
    for(int i = 0; i < 2; ++i) {
        for(int j = 1; j <= n; ++j) {
            diff[j] += diff[j - 1];
        }
    }
}
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m; // 1e7, 3e5
    int l, r, s, e;
    for(int i = 0; i < m; i++) {
        cin >> l >> r >> s >> e;
        set(l, r, s, e, (e - s)/(r - l));
    }   
    build(n);
    long long mx = LLONG_MIN, xor_value = 0;
    for(int i = 1; i <= n; ++i) {
        mx = max(mx, diff[i]);
        xor_value ^= diff[i];
    }
    cout << xor_value << " " << mx;
}

複雜度分析

• 時間複雜度：$O(n)$
• 空間複雜度：$O(n)$