Tìm vị trí đầu tiên có giá trị đủ lớn trên phiên bản
Points
65
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
ds
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.
Community Discussion