406127: GYM102272 D Cánh Đồng Hoa

Cánh đồng hoa ở Amsterdam được chia thành $$$N$$$ ô đất, mỗi ô đất được đánh số từ $$$1$$$ đến $$$N$$$.

Hai người làm vườn chăm chỉ low_ và lantrungseo được giao chăm sóc hoa trên những ô đất này. Vì là những người làm vườn yêu bộ môn giải thuật, đồng thời cũng vì có quá nhiều hoa màu, low_ và lantrungseo đã cùng đưa ra bài toán như sau:

Ban đầu trên ô đất thứ $$$i$$$ có $$$A_i$$$ bông hoa. Mỗi ngày, hai người làm vườn sẽ phải thực hiện một trong hai sự kiện sau theo danh sách cho trước:

"1": Chọn ra hai chỉ số $$$l, r$$$ ($$$1 \le l \le r \le N$$$). Với mỗi $$$i$$$ thuộc đoạn $$$[l, r]$$$, trồng trên ô đất thứ $$$i$$$ số lượng hoa là $$$i-l+1$$$. Ví dụ, nếu $$$N=5$$$ và chọn $$$l=2$$$ và $$$r=4$$$, thì trồng 1 bông trên ô đất 2, 2 bông trên ô đất 3, 3 bông trên ô đất 4.

"2": Hai người làm vườn chán trồng hoa (nên sẽ không trồng thêm bông nào ngày hôm đó). Thay vì đó, low_ đố lantrungseo tính tổng số bông hoa trên các ô đất thuộc đoạn $$$[u, v]$$$ ($$$1 \le u \le v \le N$$$).

Bạn có danh sách các sự kiện diễn ra trong $$$Q$$$ ngày. Hãy giúp lantrungseo trả lời các sự kiện "2".

Dòng đầu chứa $$$T$$$ ($$$1 \le T \le 4$$$) - số bộ test trong file input. Mỗi bộ test sẽ có format như sau:

- Dòng đầu chứa $$$N$$$ ($$$1 \le N \le 10^5$$$) - số ô đất trên cánh đồng hoa.

- Dòng thứ hai chứa $$$N$$$ số: $$$A_1, A_2, ..., A_N$$$. ($$$0 \le A_i \le 10^6$$$) - số bông hoa trên từng cánh đồng.

- Dòng thứ 3 chứa $$$Q$$$ ($$$1 \le Q \le 10^5$$$) - số sự kiện diễn ra trên cánh đồng.

- $$$Q$$$ dòng tiếp theo, đầu mỗi dòng sẽ là một xâu thể hiện dạng sự kiện:

+ "1": Sự kiện trồng thêm hoa. Trên cùng một dòng, sau xâu này sẽ là hai số $$$l, r$$$ cách nhau bởi một dấu cách ($$$1 \le l \le r \le N$$$).

+ "2": Sự kiện tính số lượng hoa. Trên cùng một dòng, sau xâu này sẽ là hai số $$$u, v$$$ cách nhau bởi một dấu cách ($$$1 \le u \le v \le N$$$).

Với mỗi sự kiện "2", in ra một số duy nhất là kết quả của sự kiện.

20% số điểm ứng với $$$N \le 1000, Q \le 1000$$$.

40% số điểm ứng với $$$N \le 10^5, Q \le 10^5$$$. Trong mỗi bộ test, truy vấn "1" cuối cùng sẽ xuất hiện trước truy vấn "2" đầu tiên.

40% số điểm còn lại ứng với giới hạn gốc.

2
5
2 1 3 5 2
6
1 1 3
2 3 5
1 4 5
1 2 5
1 1 1
2 1 4
7
10 5 2 0 8 6 2
7
1 2 5
1 1 6
2 4 7
1 1 3
1 5 5
1 1 5
2 1 7

13
25
38
86

Bộ test thứ nhất:

Ban đầu: $$${2, 1, 3, 5, 2}$$$

Sau ngày đầu tiên: $$${3, 3, 6, 5, 2}$$$

Sau ngày thứ ba: $$${3, 3, 6, 6, 4}$$$

Sau ngày thứ tư: $$${3, 4, 8, 9, 8}$$$

Sau ngày thứ năm: $$${4, 4, 8, 9, 8}$$$