Biến đổi dãy (TS10 QT 2023)

Điểm: 1300 (thành phần)

Thời gian: 1.0s

Bộ nhớ: 256M

Input: CAU4.INP

Output: CAU4.OUT

Tác giả:

Sunlight

Dạng bài

Cho dãy số gồm $n$ số nguyên $a_1,a_2,\dots,a_n$ . Xuất phát từ dãy ban đầu và thực hiện $q$ lần thuộc một trong hai loại phép toán sau trên các dãy thu được:

Thay phần tử thứ $i$ của dãy bằng $x$
Dịch dãy sang phải $k$ vị trí, nếu dãy hiện tại là $a_1,a_2,\dots,a_n$ thì sau khi dịch sẽ là dãy $a_{n-k+1},a_{n-k+2},\dots,a_n,a_1,a_2,\dots,a_{n-k}$

Yêu cầu: Sau mỗi lần thực hiện phép toán loại 1, hãy tính tổng giá trị các phần tử của dãy thu được

Input, Output và Subtasks

Input: (CAU4.INP)

Dòng thứ nhất gồm số nguyên dương $n$ ( $2\le n\le 10^5$ )
Dòng thứ hai ghi $n$ số nguyên, các số ghi cách nhau dấu cách là giá trị của các số hạng của dãy $a_1,a_2,\dots,a_n$ ( $|a_i|\le 10^9$ )
Dòng thứ ba ghi số nguyên dương $q$ ( $q\le q\le 10^5$ ) là số phép toán cần thực hiện
$q$ dòng tiếp theo, mỗi dòng mô tả một phép toán, các giá trị ghi cách nhau dấu cách:
- $1\ i\ x$ là phép toán loại 1 ( $1\le i\le n,|x|\le 10^9$ )
- $2\ k$ là phép toán loại 2 ( $1\le k\le n$ )

Output: (CAU4.OUT)

Tương ứng với mỗi phép toán loại 1, ghi ra một số nguyên trên một dòng là tổng các số hạng của dãy sau khi thực hiện phép toán, thứ tự các kết quả theo đúng thứ tự các phép toán loại 1 trong tệp dữ liệu vào. Biết rằng kết quả không vượt quá $10^{18}$

Subtasks

Subtask 1 ( $20\%$ ): $2\le n\le 1000$ và chỉ gồm phép toán loại 1
Subtask 2 ( $40\%$ ): $2\le n\le 1000$
Subtask 3 ( $40\%$ ): Không có ràng buộc gì thêm

Sample

Input (CAU4.INP)

Output (CAU4.OUT)

14
3

Note

Dãy ban đầu: $[4,1,2,5]$
Sau phép toán thứ nhất: $[2,5,4,1]$
Sau phép toán thứ hai: $[2,7,4,1]$ , có tổng bằng $14$
Sau phép toán thứ ba: $[1,2,7,4]$
Sau phép toán thứ tư: $[1,2,-4,4]$ , có tổng bằng $3$

Bình luận

Không có bình luận nào.