Ghép đoạn giữa các phiên bản

Buổi 30 — Persistent Segment Tree
Points
80
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
ds
Submissions
Đề bài

Bạn nhận được $N$ chiếc đĩa nhựa theo thứ tự, chiếc đĩa thứ $i$ có bán kính $R_i$. Bạn phải xếp lần lượt từng chiếc đĩa vào các chồng đĩa. Một chiếc đĩa chỉ có thể đặt lên trên một chồng nếu bán kính của nó nhỏ hơn hẳn bán kính của chiếc đĩa đang nằm trên đỉnh chồng đó; nếu không, bạn có thể tạo một chồng mới. Hãy tìm số lượng chồng đĩa ít nhất có thể.

Dữ liệu vào
  • Dòng đầu chứa số nguyên $N$.
  • Dòng thứ hai chứa $N$ số nguyên $R_1, R_2, \dots, R_N$.
Dữ liệu ra

Một số nguyên duy nhất là số chồng đĩa ít nhất.

Ví dụ
Đề bài

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$ và $3$ tạo phiên bản mới có số hiệu tiếp theo):

  • 1 v i x: phiên bản mới = phiên bản $v$ với $a_i$ tăng thêm $x$.
  • 2 v l r: in tổng $a_l+\dots+a_r$ của phiên bản $v$.
  • 3 u v l r: phiên bản mới giống phiên bản $u$ ở mọi vị trí ngoài $[l,r]$, còn các vị trí trong $[l,r]$ lấy giá trị từ 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. Mọi phiên bản được nhắc tới đều đã tồn tại.

Dữ liệu ra

Với mỗi thao tác loại $2$ in tổng.

Ví dụ

Input

5 5
3 -8 -6 -7 8
1 0 3 391676836
2 1 1 4
1 0 4 989986684
1 1 3 -54108904
3 0 2 2 4
Input Output
5
3 8 2 1 5
2
Giới hạn

    Output

391676818
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.
  • $1 \le N \le 2 \cdot 10^5$.
  • $1 \le R_i \le 10^9$.
  • Draft saved