Reversals and Sums

View as PDF
Submit solution
Points: 0.50 (partial)
Time limit: 1.0s
Memory limit: 512M
Input: stdin
Output: stdout
Problem type
Allowed languages
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Cho dãy ~a~ có ~n~ phần tử, hãy thực hiện các truy vấn sau:

  • ~1\ l\ r~: Đảo ngược đoạn phần tử ~[l, r]~ của dãy ~a~.
  • ~2\ l\ r~: Tính tổng các giá trị của đoạn ~[l, r]~ của dãy ~a~.

Input

  • Dòng đầu tiên chứa hai số nguyên dương ~n~ và ~m~ ~(1 \le n \le 2 \cdot 10^5, 1 \le m \le 10^5)~— kích thước và số lượng truy vấn.
  • Dòng tiếp theo chứa ~n~ số nguyên không âm ~a_1, a_2, a_3, \dots, a_n~ ~(0 \le a_i \le 10^9)~.
  • ~m~ dòng tiếp theo chứa những truy vấn có dạng ~t~, ~l~ và ~r~ ~(1 \le t \le 2, 1 \le l \le r \le n)~.

Output

In ra đáp án cho mỗi truy vấn ~t=2~.

Sample Input 1

8 3
2 1 3 4 5 3 4 4
2 2 4
1 3 6
2 2 4

Sample Output 1

8
9

Notes

  • Mảng ~a~ ban đầu là ~\{2, 1, 3, 4, 5, 3, 4, 4\}~.
  • Truy vấn ~1~ hỏi tổng phần tử trong đoạn ~[2, 4]~ bằng ~8~.
  • Mảng ~a~ sau khi thực hiện truy vấn ~2~ là ~\{2, 1, 3, 5, 4, 3, 4, 4\}~.
  • Truy vấn ~3~ hỏi tổng phần tử trong đoạn ~[2, 4]~ bằng ~9~.

Comments

Please read the guidelines before commenting.


  • 9
    pppssslc  commented on July 10, 2025, 2:22 p.m. ← edit 2

    My solve:

    Chia căn

    • Mỗi block sẽ sử dụng ~1~ deque để lưu các phần tử.
    • Đối với truy vấn đảo ngược đoạn ~[l, r]~:
    • Đối với phần lẻ ra ở 2 đầu, ta sẽ tách 2 đoạn đó ra khỏi block.
    • Ta đảo ngược đoạn như bình thường.
    • Nếu sau nhiều truy vấn, số lượng block quá lớn thì ta sẽ build lại các block. (số block lớn hơn ~3\sqrt n~)

    ĐPT: ~O(n\sqrt n)~


  • 4
    m1nkpk4nn  commented on June 20, 2025, 10:08 a.m. ← edited

    Chia Căn hoặc Splay Tree là được, ai chưa học Splay Tree có thể xem thêm tại đây.


    • 0
      phanmd  commented on July 9, 2025, 2:50 p.m.

      Thanks bạn


  • -6
    vndkhoi  commented on March 27, 2025, 6:46 a.m.

    This comment is hidden due to too much negative feedback. Show it anyway.