Mảng bền vững với hoàn tác
Points
15
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
ds
Đề bài
Cho mảng $a_1,\dots,a_n$. Có $q$ thao tác đánh số từ $1$. Gọi $T_k$ là trạng thái mảng sau thao tác thứ $k$ ($T_0$ là mảng ban đầu); trạng thái hiện tại ban đầu là $T_0$.
S i x: gán $a_i=x$ trên trạng thái hiện tại.G i: in ra $a_i$ của trạng thái hiện tại (trạng thái không đổi).R t: quay lại trạng thái $T_t$, với $0\le t<k$ ($k$ là số thứ tự của thao tác này).
Dữ liệu vào
Dòng đầu: $n,q$. Dòng hai: $n$ số nguyên. Sau đó $q$ dòng thao tác.
Dữ liệu ra
Với mỗi thao tác G in một dòng là giá trị.
Ví dụ
Input
5 5
-2 -3 0 -8 4
S 2 -100566100
S 2 195413583
S 5 607808564
G 3
S 1 -125710945
Output
0
Giới hạn
- $1\le n,q\le 10^5$; $|a_i|,|x|\le 10^9$.
- Thời gian: 2 giây; bộ nhớ: 256 MB.
Community Discussion