Sub 1 : ~N, M \le 1000~ :

• Ta duyệt lần lượt qua các vị trí ~i = 1, 2, 3, ..., n-m+1~. Với mỗi vị trí i, ta tiến hành cập nhật: ~A_{i+k} = A_{i+k} + B_{1+k}~ ~(0 \le k < m)~
• ĐPT: ~O(n*m)~

Sub 2 : ~B_i = 1~ :

• Vì ~B_i = 1~ nên số lượng ~A_i~ tăng lên chính bằng số lượng số lượng thao tác thực hiên lên ~A_i~
• Dễ thấy, ~A_i~ chịu ảnh hưởng bới các thao tác từ ~max(1, i-m+1)~ đến ~min(i, n-m+1)~ nên ~A_i = A_i + min(i, n-m+1) - max(1, i-m+1) + 1~
• ĐPT: O(n)

Sub 3 : Không có ràng buộc gì thêm:

• Nhận thấy mỗi thao tác i sẽ tăng toàn bộ đoạn ~[i, i + n - m]~ thêm ~B_i~.
• Gọi ~D_i~ là lượng được cộng vào ~A_i~ sau các thao tác,đặt ~C~ là mảng hiệu của ~D~, theo tính chất của mảng hiệu, mỗi thao tác sẽ được đổi thành ~C_i = C_i + b_i~ và ~C_{i+n-m+1} = C_{i+n-m+1} - b_i~
• Theo tính chất mảng hiệu, ta có ~C_i = \sum_{j=1}^{i} D_j~. Cuối cùng ta có ~A_i = A_i + C_i~.
• ĐPT: ~O(n)~

Code mẫu:

#include "bits/stdc++.h"

using namespace std;

#define ln "\n"
#define fast_cin()                  \
  ios_base::sync_with_stdio(false); \
  cin.tie(NULL)
#define out(file) freopen(file, "w", stdout)
#define in(file) freopen(file, "r", stdin)
#define int long long
int MOD = 1e9 + 7;
const int N = 1e5 + 7;
int n, m, a[N], b[N], c[N];

signed main() {
    fast_cin();
    cin >> n >> m;
    for(int i = 1; i <= n; i++) cin >> a[i];
    for(int i = 1; i <= m; i++) cin >> b[i];    
    for(int i = 1; i <= m; i++) {
        c[i] += b[i];
        c[i+n-m+1] -= b[i];
    }
    int cur = 0;
    for(int i = 1; i <= n; i++) {
        cur += c[i];
        cout << a[i] + cur << ' ';
    }
}