Cỗ máy thời gian

Điểm: 2400 (OI)

Giới hạn thời gian: 1.0s

Giới hạn bộ nhớ: 1G

Input: stdin

Output: stdout

Tác giả:

TaThanHungbc

Nguồn bài:

tạ

Dạng bài

Ngôn ngữ cho phép

Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, ObjC, OCaml, Pascal, Perl, PHP, Pike, Prolog, PyPy, Python, Racket, Ruby, Rust, Scala, Scheme, ~~Scratch~~, Sed, ~~Swift~~, TCL, Turing, VB, Zig

Ông Q (heygnauq sau này) là một nhà du hành thời gian vĩ đại, sở hữu cho mình một cỗ máy thời gian toàn năng có thể thay đổi cả tương lai. Tuy nhiên, ông vẫn gặp khó khăn với công việc, bị deadline dí như bao người khác.

Công việc của ông Q là hiệu chỉnh một dãy $A$ gồm $n$ số nguyên ban đầu thành một dãy hoàn hảo nhất để ổng được thăng quan tiến chức. Vì thời gian gấp rút nên khi điều chỉnh đến khi nào thấy dãy no hope quá thì ông Q sẽ dùng cỗ máy thời gian quay về một thời điểm mà ông đã từng trải qua khi đang hiệu chỉnh (có thể bao gồm những dòng thời gian song song khác) để có thể chạy kịp deadline với một dãy $A$ hoàn hảo nhất có thể.

Vì dãy số $A$ có thể rất dài nên ông Q không thể kiểm tra và tính toán hết được, ông ta chỉ có thể nhờ bạn thực hiện truy vấn điều chỉnh dãy số hoặc kiểm tra một đoạn trên đó. Ngoài ra, bạn còn phải giúp ổng du hành thời gian đến thời điểm sau một truy vấn bất kì đã trải qua trước đó.

$Input$

Dòng đầu tiên gồm 2 số nguyên $n$ và $q$ lần lượt là số phần tử của dãy $A$ (các phần tử được đánh số từ $1$ tới $n$ ) và số truy vấn.
Dòng tiếp theo chứa $n$ số nguyên lần lượt là $n$ phần tử của dãy $A$ .
$q$ dòng tiếp theo, dòng thứ $i$ chứa thông tin của truy vấn thứ $i$ , một truy vấn có thể là:
- $C l r s$ $(1 \leq l \leq r \leq n)$ : hiệu chỉnh tăng các phần tử từ $A_{l}$ đến $A_{r}$ lên $s$ đơn vị.
- $S l r$ $(1 \leq l \leq r \leq n)$ : tính tổng của dãy con từ $A_{l}$ đến $A_{r}$ .
- $B t$ : du hành thời gian đến thời điểm sau truy vấn thứ $t$ (dữ liệu đảm bảo truy vấn này không thể quay về một truy vấn dạng $B$ khác).

$Output$

Với mỗi truy vấn dạng $S$ , in ra một số nguyên duy nhất là tổng của dãy con $(l, r)$ trên một dòng, vì kết quả có thể lớn nên hãy in ra phần dư khi chia cho $10^{9} + 7$ .

$Sample input$

Copy

7 6
1 1 1 1 1 1 1
C 2 6 1
C 3 5 1
B 0
S 2 7
B 2
S 2 5

$Sample output$

Copy

6
11

$Constraint$

$1 \leq n \leq 10^{5}$ .
$1 \leq q \leq {5.10}^{4}$ .
$1 \leq s, A_{i} \leq 1000$ .

$Subtask$

Subtask $1 (10 %)$ : Không có truy vấn dạng $B$ và $n \leq 1000$ , $q \leq 500$ .
Subtask $2 (20 %)$ : Không có truy vấn dạng $B$ .
Subtask $3 (30 %)$ : $l = r$ trong tất cả truy vấn dạng $C$ .
Subtask $4 (40 %)$ : Không có giới hạn gì thêm.

$Notes$

Ban đầu ông Q có dãy $A = (1, 1, 1, 1, 1, 1, 1)$ .
Sau truy vấn $1$ , dãy trở thành $(1, 2, 2, 2, 2, 2, 1)$ .
Sau truy vấn $2$ , dãy trở thành $(1, 2, 3, 3, 3, 2, 1)$ .
Truy vấn $3$ yêu cầu ta du hành thời gian đến thời điểm ban đầu, khi dãy $A$ là $(1, 1, 1, 1, 1, 1, 1)$ .
Truy vấn $4$ yêu cầu in ra tổng của dãy con từ $A_{2}$ tới $A_{7}$ : $1 + 1 + 1 + 1 + 1 + 1 = 6 (mod 10^{9} + 7)$ .
Truy vấn $5$ yêu cầu ta du hành về thời điểm sau truy vấn $2$ , tức là dãy $(1, 2, 3, 3, 3, 2, 1)$ .
Truy vấn cuối cùng yêu cầu in ra tổng của dãy con từ $A_{2}$ tới $A_{5}$ : $2 + 3 + 3 + 3 = 11 (mod 10^{9} + 7)$ .

Bình luận

Hãy đọc nội quy trước khi bình luận.

-7

minhtriet17032008 đã bình luận 9:25:35 sa, 30/08/2024

Xin sol

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

-4

pinkpenguin05122008a đã bình luận 8:32:07 sa, 03/09/2024

‎‎