Sequence queries

View as PDF

Submit solution

Points: 1.80 (partial)
Time limit: 1.0s
Memory limit: 512M
Input: stdin
Output: stdout

Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Cho một dãy số và các loại truy vấn sau:

  • 1 ~A~ ~B~ ~X~: gán các phần từ thứ ~A~ đến thứ ~B~ trong dãy bằng ~X~.
  • 2 ~A~ ~B~ ~X~: cộng phần tử thứ ~A~ cho ~X~, thứ ~A~ + 1 cho ~2X~,..., thứ ~B~ cho ~(B - A + 1) \times X~.
  • 3 ~C~ ~X~: chèn ~X~ vào trước phần tử thứ ~C~ của dãy hiện thời.
  • 4 ~A~ ~B~: tính tổng từ phần tử thứ ~A~ đến thứ ~B~.

Input

  • Dòng đầu ghi hai số nguyên ~N~ và ~Q~, số phần tử của dãy ban đầu và số truy vấn ~(1 \leq N, Q \leq 10^5)~.
  • Dòng tiếp theo mô tả dãy số. Mỗi số không vượt quá ~10^5~.
  • ~Q~ dòng tiếp theo mô tả các truy vấn theo định dạng như trong đề bài. Trong mọi truy vấn, ~0 \leq X \leq 100~, ~1 \leq A \leq B \leq~ độ dài dãy hiện thời, ~1 \leq C \leq~ (độ dãy dãy hiện thời + 1).

Output

  • In ra trên từng dòng câu trả lời cho mỗi truy vấn loại 4.

Sample Input 1

5 5 
1 2 3 4 5 
1 5 5 0 
4 4 5 
4 5 5 
2 1 5 1 
4 1 5

Sample Output 1

4
0
25

Sample Input 2

1 7 
100 
3 1 17 
3 2 27 
3 4 37 
4 1 1 
4 2 2 
4 3 3 
4 4 4

Sample Output 2

17
27
100
37

Comments

Please read the guidelines before commenting.


There are no comments at the moment.