区間等差数列加算

2 secs 1024 MB

全てのクエリについて、 $s=0$ であると仮定します。

このとき、 $D_i=A_i-A_{i-1}$ を考えると、クエリ l r t は、「 $i=l+1,l+2,...,r-1$ について $D_i$ に $t$ を、 $D_r$ に $-(r-l-1)\times t$ を加算する」と解釈することができます。これは imos 法を用いることによって高速に処理できます。

続いて、 $s\neq 0, t=0$ の場合を考えます。

このときクエリ l r s は、「 $i=l,l+1,...,r-1$ について $A_i$ に $s$ を加算する」と解釈することができます。これも同様に imos 法を用いて高速に処理できます。

$s\neq 0, t\neq 0$ の場合、クエリ l r s t はクエリ l r s 0 と l r 0 t の 2 種類に分解でき、それぞれ先述のケースに帰着できます。

よって全体 $O(N+Q)$ でこの問題を解くことができました。

実装例

xxxxxxxxxx
 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
​
struct query {
    int l, r;
    ll start, step;
};
​
vector<ll> solve(int N, vector<query> Q) {
    vector<ll> I1(N + 1), I2(N + 1);
​
    for (auto [l, r, start, step] : Q) {
        I1[l + 1] += step;
        I1[r] -= step;
        I1[r] -= step * (r - l - 1);
        I1[r + 1] += step * (r - l - 1);
​
        I2[l] += start;
        I2[r] -= start;
    }
​
    for (int i = 0; i < N; i++) I1[i + 1] += I1[i];
    for (int i = 0; i < N; i++) I2[i + 1] += I2[i];
​
    vector<ll> A(N);
    for (int i = 0; i < N - 1; i++) A[i + 1] = A[i] + I1[i + 1];
    for (int i = 0; i < N; i++) A[i] += I2[i];
​
    return A;
}
​
int main() {
    int N, Q;
    cin >> N >> Q;
    vector<query> queries(Q);
    for (int i = 0; i < Q; i++) {
        cin >> queries[i].l >> queries[i].r >> queries[i].start >> queries[i].step;
    }
​
    auto ans = solve(N, queries);
​
    for (int i = 0; i < N; i++) cout << ans[i] << (i == N - 1 ? '\n' : ' ');
}