Ghép đoạn giữa các phiên bản
Points
80
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
ds
Đề 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.
Community Discussion