Tìm vị trí đầu tiên có giá trị đủ lớn trên phiên bản

Buổi 30 — Persistent Segment Tree
Points
65
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
ds
Submissions

Cho mảng $a_1,\dots,a_n$ (phiên bản $0$). Các thao tác (mỗi thao tác loại $1$ tạo phiên bản mới có số hiệu tiếp theo):

  • 1 v i x: tạo phiên bản mới từ $v$ bằng cách gán $a_i=x$.
  • 2 v p x: in chỉ số nhỏ nhất $j\ge p$ trong phiên bản $v$ sao cho $a_j\ge x$, hoặc $-1$ nếu không có.
  • 3 v l r: in $\max(a_l,\dots,a_r)$ của phiên bản $v$.
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 loại $2$ và $3$ in một dòng đáp án.

Ví dụ

Input

5 5
0 4 5 -9 2
3 0 4 4
1 0 4 2
3 0 2 2
3 0 2 2
1 1 2 -1

Output

-9
4
4
Giới hạn
  • $1\le n,q\le 10^5$; $|a_i|,|x|\le 10^9$; $1\le p\le n$.
  • Thời gian: 2 giây; bộ nhớ: 256 MB.
Draft saved