Phép tính cần tính:
f(l, r) = 1*A[l] + 2*A[l + 1] + ... + (r - l + 1)*A[r].
Biến đổi dãy thành:
f(l, r) = (l * A[l] + (l + 1) * A[l + 1] + ... + r * A[r]) - ((l - 1) * A[l] + (l - 1) * A[l + 1] + ... + (l - 1) * A[r]).
Viết gọn lại thì:
f(l, r) = (l * A[l] + (l + 1) * A[l + 1] + ... + r * A[r]) + (l - 1) * (A[l] + A[l + 1] + ... + A[r]).
Cách biến đổi như thể có thể dùng tính chất của mảng cộng dồn khi hệ số không cần phụ thuộc vào biến nhập vào mà là chỉ số của mảng.
-> Tạo 2 mảng tổng tiền tố
1. Mảng có thể tính tổng từ l -> r
2. Mảng có thể tính tổng của l*A[l] + (l + 1)*A[l + 1] + ... + r*A[r]
Chú ý: Dù đề bài chỉ ra điều kiện -1e6 <= A[i] <= 1e6 và biến chạy chỉ số trong phép tính với n <= 1e5 nhưng phải để long long để tránh bị tràn số vì những cái này đều nằm trong phép tính có thể cho ra kết quả lớn.
Code mẫu:
#include <bits/stdc++.h>
using namespace std;
const int mx = 1e5;
long long A[mx + 5];
long long T1[mx + 5];
long long T2[mx + 5];
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
int n, q;
cin >> n >> q;
for (int i = 1; i <= n; ++i) cin >> A[i];
T1[0] = 0;
T2[0] = 0;
for (long long i = 1; i <= n; ++i){
T1[i] = T1[i - 1] + A[i];
T2[i] = T2[i - 1] + A[i]*i;
}
while (q--){
long long l, r;
cin >> l >> r;
cout << (T2[r] - T2[l - 1]) - (l - 1)*(T1[r] - T1[l - 1]) << '\n';
}
}
Sherwin
Created at
6 likes