Ams QG 24-7-23
RMQSecond
Nộp bàiPoint: 100
Cho dãy ~a~ nguyên dương gồm ~n~ phần tử.
Có ~q~ truy vấn, mỗi truy vấn có dạng ~l_i,r_i~ ~(l_i < r_i)~, hãy in ra tổng của số lớn nhất và số lớn thứ hai trong đoạn ~[l_i,r_i]~.
Input
- Dòng đầu tiên chứa số nguyên dương ~n~ là số phần tử của dãy.
- Dòng thứ hai gồm ~n~ số nguyên dương miêu tả dãy ~a~.
- Dòng thứ ba gồm số nguyên dương ~q~.
- ~q~ dòng sau, mỗi dòng gồm ~2~ số nguyên dương ~l_i,r_i~ miêu tả truy vấn.
Constraints
- ~2 \le n \le 3*10^5~
- ~1 \le a_i \le 10^9~
Subtask:
- Subtask ~1~ (~50\%~ số điểm): ~n \le 2000~
- Subtask ~2~ (~50\%~ số điểm): ~n \le 3*10^{5}~
Output
- Với mỗi truy vấn, in ra kết quả cần tính.
Sample Input 1
5
1 4 2 3 5
3
1 2
1 5
3 5
Sample Output 1
5
9
8
GCDSeq
Nộp bàiPoint: 100
Bạn được cho một dãy số nguyên ~a~ gồm ~n~ phần tử ~a_0,a_2,...,a_{n-1}~.
Mỗi bước, dãy ~a~ sẽ thay đổi thành một dãy độ dài ~n~ khác - coi là dãy ~b~, với phần tử ~b_i = gcd(a_i,a_{(i+1)\%n})~.
Giả sử nếu ~a = [16,24,10,5]~, sau một bước sẽ thành ~ b=[gcd(16,24), gcd(24,10), gcd(10,5), gcd(5,16)]=[8,2,5,1]~. Như vậy, sau một bước, dãy ~a = [16,24,10,5]~ sẽ trở thành ~a = [8,2,5,1]~.
Hãy tìm số bước ít nhất sao cho dãy ~a~ bằng nhau.
Input
Dòng đầu vào đầu tiên chứa số nguyên ~n~.
Dòng tiếp theo có ~n~ số nguyên ~a_0, a_1, ..., a_{n-1} ~.
Constraints
- ~1 \le n \le 2*10^5~.
- ~1 \le a_i \le 10^6~.
Subtask
- Subtask ~1~ ~(30\%)~: ~n \le 2000~.
- Subtask ~2~ ~(70\%)~: Không có điều kiện gì thêm.
Output
- Gồm một số nguyên duy nhất là số bước để dãy ~a~ bằng nhau.
Sample Input 1:
4
16 24 10 5
Sample Output 1:
3
Sample Input 2:
4
42 42 42 42
Sample Output 2:
0
QLCA
Nộp bàiPoint: 100
Cho một cây ~n~ nút và ta định nghĩa nút ~1~ là gốc của cây.
Bây giờ ta có ~q~ truy vấn, mỗi truy vấn có dạng: ~l_i,r_i~ ~(1 \le l_i \le r_i \le n)~.
Yêu cầu: Ứng với mỗi truy vấn, ta in ra LCA của tất cả các nút từ ~l_i~ đến ~r_i~.
Input
Dòng đầu vào đầu tiên chứa số nguyên ~n~ - thể hiện số nút của cây.
~n-1~ dòng tiếp theo: mỗi dòng gồm ~2~ số nguyên ~x,y~ - thể hiện cạnh nối giữa hai đỉnh ~x~ và ~y~.
Dòng tiếp theo, chứa số ~q~ thể hiện số lượng truy vấn.
~q~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~l_i,r_i~ ~(1 \le l_i \le r_i\le n)~.
Constraints
- ~1 \le n \le 3*10^5~.
Subtask
- Subtask ~1~ ~(50\%)~: ~n \le 2000~.
- Subtask ~2~ ~(50\%)~: Không có điều kiện gì thêm.
Output
- Ứng với mỗi truy vấn, in ra đáp án cần tìm.
Sample Input 1:
5
1 4
2 5
3 5
2 4
2
2 4
1 3
Sample Output 1:
4
1
Shopping
Nộp bàiPoint: 100
Trong dịp lễ giáng sinh, siêu thị ~ABC~ có chính sách giảm giá ~n~ mặt hàng. Các mặt hàng được trưng bày theo thứ tự từ trái qua phải với mức giá ưu đãi là ~p_i~, với số lượng không giới hạn với mỗi loại mặt hàng. Có ~m~ khách hàng thân thiết vô cùng yêu thích chương trình giảm giá này, người thứ ~i~ mang tới số tiền là ~t_i~ và sẽ đi từ vị trí ~l_i~ tới vị trí ~r_i~. Tại mỗi vị trí, người này sẽ cố gắng mua nhiều nhất số hàng có thể tới khi không còn đủ tiền mua.
Yêu cầu: Hãy xác định số tiền còn lại của từng người sau khi mua hàng.
Input
- Dòng đầu tiên chứa số nguyên dương ~n, m~
- Dòng thứ hai chứa ~n~ số, số thứ ~i~ là ~p_i~ mô tả giá tiền của mặt hàng thứ ~i~
- ~m~ dòng tiếp theo, dòng thứ ~i~ chứa ~3~ số nguyên ~t_i,l_i,r_i~ xác định số tiền và khoảng cách di chuyển của người thứ ~i~.
Constraints
- ~1 \le n,m \le 2*10^5~
- ~1 \le p_i,t_i \le 10^{18}~
Subtask
- Subtask ~1~ ~(50\%)~: ~1 \le n,m \le 5000; 1 \le p_i, t_i \le 10^9~
- Subtask ~2~ ~(50\%)~: Không có ràng buộc gì thêm
Sample Input 1
5 3
5 3 2 4 6
8 5 5
107 1 4
7 3 5
Sample Output 1
2
0
1
SimpSeq
Nộp bàiPoint: 100
Một dãy số ~(b_1, b_2, ..., b_m)~ được gọi là có thể tối giản nếu tồn tại một phần tử *~x~ thỏa mãn:*
~x~ là duy nhất trong dãy.
Mọi phần tử ~b_1, b_2, ..., b_m~ đều chia hết cho ~x~.
Cho dãy ~a~ gồm ~n~ phần tử ~a_1, a_2, ..., a_n~, hãy đếm số cặp chỉ số ~(l, r)~ sao cho dãy ~a_l, a_{l+1}, ..., a_r~ là dãy có thể tối giản. ~(1 \le l < r \le n)~.
Input
Dòng đầu tiên gồm số nguyên dương ~n~.
Dòng thứ hai gồm ~n~ số nguyên dương ~a_1, a_2, ..., a_n~ .
Constraints
- ~1 \le n \le 3 * 10^5~.
- ~1 \le a_i \le 10^9~.
Subtask
- Subtask ~1~ ~(50\%)~: ~1 \le n \le 1000~
- Subtask ~2~ ~(50\%)~: Không có ràng buộc gì thêm
Output
- Gồm một dòng duy nhất là số dãy tìm được.
Sample Input 1
5
4 3 6 4 2
Sample Output 1
3
Notes
- Các đoạn thỏa mãn là ~[2, 3], [4, 5], [3, 5]~.
Chia dãy
Nộp bàiPoint: 100
Cho dãy ~a_1, a_2, \dots, a_n~ gồm ~n~ số nguyên. Bạn cần trả lời ~q~ truy vấn, mỗi truy vấn gồm hai số nguyên ~l~, ~r~. Với mỗi truy vấn bạn cần đếm xem, có bao nhiêu cách chia dãy ~a_l, a_{l+1}, \dots, a_r~ thành hai phần khác rỗng sao cho mỗi phần gồm các phần tử đứng liên tiếp và đôi một phân biệt.
Input
Dòng đầu chứa hai số nguyên ~n~, ~q~ (~1 \le n, q \le 5 \times 10^5~).
Dòng thứ hai chứa ~n~ số nguyên ~a_1, a_2, \dots, a_n~ (~1 \le a_i \le 10^9~).
~q~ dòng tiếp theo, dòng thứ ~i~ chứa hai số nguyên ~l_i~, ~r_i~ (~1 \le l_i \le r_i \le n~) mô tả truy vấn thứ ~i~.
Output
In ra ~q~ dòng, dòng thứ ~i~ gồm một số nguyên là kết quả cho truy vấn thứ ~i~.
Scoring
- Subtask ~1~ (~40\%~ số điểm): ~n, q \le 1000~.
- Subtask ~2~ (~30\%~ số điểm): ~a_i \le 10~.
- Subtask ~3~ (~30\%~ số điểm): Không có ràng buộc gì thêm.
Example
Input 1
5 3
1 3 1 2 2
1 5
1 2
3 5
Output 1
0
1
1
Input 2
6 4
1 3 4 6 3 5
1 2
3 6
2 5
4 4
Output 2
1
3
3
0