LRC_1C - Tổng cặp

Xem dạng PDF
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ả:
wronganswer, Hnhatn
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

Hãy đọc nội quy trước khi bình luận.


  • 5
    duongnguyen0210  đã bình luận lúc 15, Tháng 2, 2024, 14:58 ← sửa 2

    ý 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à:

    • Nếu có l = 1, r = 5 với ta duyệt qua tất cả các cặp i, j thì sẽ có các cặp đó là:{1, 2}, {1, 3}, {1, 4}, {1, 5}, {2, 3}, {2, 4}, {2, 5}, {3, 4}, {3, 5}, {4, 5}
    • => vậy tất cả các cặp i j đều đôi một khác nhau.
    • giờ ta tính tổng của các cặp a[i], a[j] phía trên thì ta có thể rút gọn lại theo một cách tổng quát đó chính là:
    • "a[i] * (prefix[r] - prefix[i])+...+ a[r - 1] * (prefix[r] - prefix[r - 1]"(1)
    • với i thuộc trong đoạn từ (l -> r - 1), tại sao lại là từ l đến r - 1 thì vì nếu lấy luôn thằng i = r thì sẽ không tồn tại cặp hai số. rồi thì bây h ta có thể thử biến đổi cái công thức số (1) phía trên thêm tí ta sẽ có được:
    • "(a[i] * prefix[r]) - (a[i] * prefix[i]) +...+ (a[r - 1] * prefix[r]) - (a[r - 1] * preifx[r - 1])"(2)
    • Rồi oke tới đây ta chỉ việc nhóm các thằng mang dấu trừ phía trước vào một nhóm và mấy thằng mang dấu cộng phía trước vào một nhóm thì lúc này sẽ thành là:
    • (a[i] * prefix[r] +...+ a[r - 1] * prefix[r]) - (a[i] * prefix[i] +...+ a[r - 1] * prefix[r - 1])
    • rồi thì h ở đây ta sẽ biến các cái thằng a[i] * prefix[i] thành b[i] rồi từ đó dựa vào thằng b[i] ta tạo ra mảng prefix_2 mục đích là để tính tổng các các thằng b[i] hay còn gọi là tổng của các cái thằng a[i] * prefix[i] với i thuộc đoạn từ (l -> r - 1)
    • vậy là ta đã có đủ công cụ rồi h nhiệm vụ đơn giản của chúng ta chỉ việc ráp vào công thức thôi, công thức cuối cùng sẽ là:
    • "((prefix1[r - 1] - prefix1[l - 1]) * prefix1[r]) - (prefix2[r - 1] - prefix_2[l - 1])"
    • muốn làm được bài này các bạn cần có một tí kiến thức về prefix_sum cũng như là tính chất của phép nhân, ở trên là ý tưởng của mình dùng để ac bài này với mối thằng l và r các bạn chỉ cần lắp vào cái công thức mình đã xây dựng ở trên là sẽ cho ra kết quả ngay trong độ phức tạo thời gian là o(1) hay nếu tổng quát hơn thì bài này độ phức tạp của nó sẽ là o(max(q, n))>
    • đây là lần đầu tiên mình viết lời giải nên có thể còn mắc sai sót, mong các bạn đọc tham khảo nếu có gì sai sót có thể góp ý cho mình nhé, mình cảm ơn nhiều:-).
    • Nếu thấy hay thì ngại gì k cho mình một vote nào:3
    • code: https://ideone.com/Xgcpt1

  • -4
    tri_88  đã bình luận lúc 26, Tháng 12, 2023, 3:12

    Code tại đây


    • 0
      SigmaGamer  đã bình luận lúc 12, Tháng 7, 2024, 7:19

      cam on ban