Mảng bền vững với hoàn tác

Buổi 30 — Persistent Segment Tree
Points
15
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
ds
Submissions
Đề 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.
Draft saved