nquery


Submit solution

Points: 5 (partial)
Time limit: 2.0s
Memory limit: 977M

Author:
Problem types

Cho một dãy số nguyên có các phần tử a1,a2,...,an. Hàm f(i,j) với 1ijn được định nghĩa như sau:

 f(i,j)=u=ijv=ujt=uvat  Ví dụ: Với dãy số 1, 4, 3, 2, ta có:

  • f(1,4)=1+4+3+2+(1+4)+(4+3)+(3+2)+(1+4+3)+(4+3+2)+(1+4+3+2)=54
  • f(2,3)=4+3+(4+3)=14

Yêu cầu: Cho dãy số A gồm n phần tử và n truy vấn, mỗi truy vấn có dạng như sau:

  • C i v: Thêm phần tử giá trị v vào vị trí i với 1in
  • R i j: Tính f(i,j), với 1ijn, kết quả chia dư 109+7
  • U i v: Thay phần tử giá trị v vào vị trí i với 1in
  • D i: Xóa phần tử ở vị trí i với 1in

Đầu vào

Dòng đầu là một số nguyên dương n

Dòng tiếp theo gồm n số nguyên ai

Trong n dòng cuối cùng, mỗi dòng chứa một truy vấn CRUD

Đầu ra

Với mỗi truy vấn dạng R, in ra kết quả truy vấn chia dư cho 109+7

Giới hạn

Tất cả các test, 0ai109, trong đó:

20%: n1000, đa dạng truy vấn

20%: n105, có truy vấn R và truy vấn U, trong đó truy vấn R luôn là R 1 n

20%: n105, có các truy vấn CUD và chỉ có 1 truy vấn R 1 n ở cuối cùng

20%: n105, có các truy vấn RUD

20%: n105, có đa dạng các loại truy vấn

Ví dụ

Đầu vào

Copy
4
1 8 2 7
C 2 4
U 3 3
D 5
R 1 4

Đầu ra

Copy
54

Giải thích

Copy
Sau truy vấn 1, dãy số trở thành: 1 4 8 2 7
Sau truy vấn 2, dãy số trở thành: 1 4 3 2 7
Sau truy vấn 3, dãy số trở thành: 1 4 3 2
Truy vấn thứ 4, in ra kết quả f(1,4) = 54 (đã tính ở trên đề bài)

Comments

There are no comments at the moment.