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
Chia Căn hoặc Splay Tree là được, ai chưa học Splay Tree có thể xem thêm tại đây.
khó =((