Reversals and Sums

Xem dạng PDF
Gửi bài giải
Điểm: 0,50 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 512M
Input: stdin
Output: stdout
Dạng bài
Ngôn ngữ cho phép
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~.

Bình luận

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


  • 9
    pppssslc  đã bình luận lúc 10, Tháng 7, 2025, 14:22 ← sửa 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  đã bình luận lúc 20, Tháng 6, 2025, 10:08 ← chỉnh sửa

    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  đã bình luận lúc 9, Tháng 7, 2025, 14:50

      Thanks bạn


  • -6
    vndkhoi  đã bình luận lúc 27, Tháng 3, 2025, 6:46

    Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.