Gửi bài giải
Điểm:
1,00 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
256M
Input:
stdin
Output:
stdout
Tác giả:
Dạng bài
Cho mảng ~A~ gồm ~N~ phần tử, giá trị của một đoạn ~(l, r)~ trong mảng là tổng của các cặp ~A_i \times A_j~ với ~l~ ~\le~ ~i~ ~<~ ~j~ ~\le~ ~r~ .
Cho ~Q~ truy vấn, hãy tính và in ra từng giá trị.
Dữ liệu
Dòng đầu tiên chứa hai số ~N, Q~ (~N , Q~ ~\le~ ~10^5~) . Dòng tiếp theo gồm ~N~ số nguyên dương (~A_{i}~ ~\le~ ~5 \times 10^4~). Tiếp theo là gồm ~Q~ dòng, mỗi dòng gồm hai số nguyên dương ~l, r~ (~1~ ~\le~ ~l~ ~<~ ~r~ ~\le~ ~N~).
Kết quả
In ra ~Q~ dòng, mỗi dòng là giá trị đoạn ~(l, r)~ ở truy vấn đấy .
Test ví dụ
Dữ liệu
4 3
1 2 3 4
1 2
1 3
2 3
Kết quả
2
11
6
Bình luận
ý tưởng: ta có thể thấy đc rằng với điều kiện l <= i < j < r. ta có thể rút ra đc đó là:
include <bits/stdc++.h>
using namespace std; int main() { iosbase::syncwith_stdio(false); cin.tie(0), cout.tie(0); int n, q; cin >> n >> q; long long res = 0, ans = 0; int sum = 0, a[n + 1], s = 0; for(int i = 1; i <= n; i++){ cin >> a[i]; } while(q--){ int l, r; cin >> l >> r; for(int i = l; i <= r; i++){ p[i] = p[i-1] + a[i]; sum = p[i]; } for(int i = l; i <= r; i++){ s += a[i]; sum -= s; res = a[i] * sum; sum += s; ans += res; } cout << ans << endl; ans = 0; continue; } return 0; } cíu đúng test đề bai mà vẫn sai hết TvT
Code tại đây