Truy vấn đa thức (Polynomial Queries)

Nguồn: CSES

Phiên bản: Phước Hưng OJ Extended

Đề bài

Cho mảng $t_1,\ldots,t_n$. Có hai loại thao tác: 1 a b tăng các phần tử trong $[a,b]$ lần lượt thêm $1,2,\ldots,b-a+1$; 2 a b hỏi tổng đoạn $[a,b]$.

Input

Dòng đầu chứa hai số nguyên $n,q$. Dòng thứ hai chứa $n$ phần tử $t_1,t_2,\ldots,t_n$. Mỗi trong $q$ dòng tiếp theo là một thao tác:

• 1 a b: cộng lần lượt $1,2,\ldots,b-a+1$ vào $t_a,t_{a+1},\ldots,t_b$.
• 2 a b: hỏi tổng $t_a+t_{a+1}+\cdots+t_b$.

Output

Mỗi thao tác loại 2 in một dòng là tổng đoạn.

Subtask

• Subtask 1 (20%): $n$ và số thao tác không vượt 30; các điều kiện còn lại giữ như đề đầy đủ.

• Subtask 2 (30%): $n$ và số thao tác không vượt 3000; các điều kiện còn lại giữ như đề đầy đủ.

• Subtask 3 (50%): toàn bộ giới hạn:

• $1\le n,q\le2\cdot10^5$

• $1\le t_i\le10^6$

• $1\le a\le b\le n$

Ví dụ

Input

5 3
4 2 3 1 7
2 1 5
1 1 5
2 1 5

Output

17
32

Giải thích

Ban đầu tổng là $4+2+3+1+7=17$. Sau update 1 1 5, mảng thành [5,4,6,5,12], nên tổng mới là $32$.