Ban đầu bạn có một mảng A gồm N số 0. Bạn nhận được Q phép cập nhật (L, R, V) (tăng A[L...R] lên V đơn vị). Sau khi thực hiện tất cả Q phép cập nhật, hãy tìm giá trị lớn nhất trong mảng A cuối cùng.

Input:

Dòng đầu tiên chứa N và Q (1 <= N, Q <= 10^5).

Q dòng tiếp theo, mỗi dòng chứa L, R, V (1 <= L <= R <= N, -10^9 <= V <= 10^9).

Output:

In ra giá trị lớn nhất trong mảng A sau khi cập nhật.

Ví dụ 1:

Input:

5 3
1 3 10
2 4 5
3 5 2

Output:

17

(Giải thích: Mảng A cuối cùng là [10, 15, 17, 7, 2]. Số lớn nhất là 17.)

Cho một mảng A gồm N số nguyên. Hãy tìm một chỉ số i (1 <= i < N) để "chia" mảng thành hai phần: phần 1 (từ 1 đến i) và phần 2 (từ i+1 đến N). Hãy tìm chỉ số i sao cho chênh lệch (giá trị tuyệt đối của hiệu) giữa tổng phần 1 và tổng phần 2 là nhỏ nhất. In ra giá trị chênh lệch nhỏ nhất đó.

Input:

Dòng đầu tiên chứa N (2 <= N <= 10^5).

Dòng thứ hai chứa N số A[i] (-1000 <= A[i] <= 1000).

Output:

In ra chênh lệch nhỏ nhất tìm được.

Ví dụ 1:

Input:

5
1 2 3 4 5

Output:

3

(Giải thích: i=1: |(1) - (2+3+4+5)| = |1 - 14| = 13 i=2: |(1+2) - (3+4+5)| = |3 - 12| = 9 i=3: |(1+2+3) - (4+5)| = |6 - 9| = 3 i=4: |(1+2+3+4) - (5)| = |10 - 5| = 5 Chênh lệch nhỏ nhất là 3.)

Cho một mảng A gồm N số nguyên. Hãy đếm xem có bao nhiêu đoạn con liên tiếp A[L...R] (1 <= L <= R <= N) có tổng bằng 0.

Gợi ý: P[R] - P[L-1] = 0 nghĩa là P[R] = P[L-1]. Hãy đếm số lần các giá trị bằng nhau xuất hiện trong mảng cộng dồn P (bao gồm cả P[0]=0).

Input:

Dòng đầu tiên chứa N (1 <= N <= 10^5).

Dòng thứ hai chứa N số A[i] (-10^6 <= A[i] <= 10^6).

Output:

In ra số lượng đoạn con có tổng bằng 0.

Ví dụ 1:

Input:

6
1 3 -2 -1 4 -5

Output:

2

(Giải thích: Đoạn A[2...4] = (3) + (-2) + (-1) = 0 Đoạn A[3...4] = (-2) + (-1) + (4) + (-5) = -4 (Lỗi test) Mảng P: [0, 1, 4, 2, 1, 5, 0] P[0]=0, P[6]=0 -> cặp (0, 6) -> Đoạn A[1...6] P[1]=1, P[4]=1 -> cặp (1, 4) -> Đoạn A[2...4] Có 2 đoạn.)

Cho một mảng A gồm N số nguyên và một số K. Đếm số lượng đoạn con A[L...R] có tổng chia hết cho K.

Gợi ý: (P[R] - P[L-1]) % K == 0 nghĩa là P[R] % K == P[L-1] % K. Hãy xây dựng mảng P, sau đó tính số dư của từng P[i] cho K. Đếm số lần các số dư bằng nhau xuất hiện. (Lưu ý xử lý số âm khi chia lấy dư).

Input:

Dòng đầu tiên chứa N và K (1 <= N <= 10^5, 2 <= K <= 10^5).

Dòng thứ hai chứa N số A[i] (-10^9 <= A[i] <= 10^9).

Output:

In ra số lượng đoạn con hợp lệ.

Input:

5 3
4 1 2 3 2

Output:

4

Cho một mảng A gồm N số nguyên dương và một số K. Tìm đoạn con A[L...R] có độ dài (R-L+1) lớn nhất sao cho tổng của đoạn đó không vượt quá K.

Input:

Dòng đầu tiên chứa N và K (1 <= N <= 10^5, 1 <= K <= 10^9).

Dòng thứ hai chứa N số A[i] (1 <= A[i] <= 10^4).

Output:

In ra độ dài lớn nhất tìm được. Nếu không có đoạn nào, in 0.

Ví dụ:

Input:

8 20
1 3 5 1 2 4 1 9

Output:

7

(Giải thích: Đoạn A[1...7] = 1+3+5+1+2+4+1 = 17 (<= 20). Đây là đoạn dài nhất (dài 7).)

Cho một mảng A gồm N số nguyên dương và một số K. Tìm đoạn con A[L...R] có độ dài (R-L+1) ngắn nhất sao cho tổng của đoạn đó lớn hơn hoặc bằng K.

Input:

Dòng đầu tiên chứa N và K (1 <= N <= 10^5, 1 <= K <= 10^9).

Dòng thứ hai chứa N số A[i] (1 <= A[i] <= 10^4).

Output:

In ra độ dài ngắn nhất tìm được. Nếu không có đoạn nào, in -1.

Ví dụ 1:

Input:

8 10
1 3 5 1 2 4 1 9

Output:

2

(Giải thích: A[1...4] = 10 (dài 4). A[2...4] = 10 (dài 3). A[7...8] = 1+9 = 10 (dài 2). A[8...8] = 9 (< 10). Đoạn ngắn nhất có tổng >= 10 là [1, 9] (dài 2).)

Cho một mảng A. Tìm một chỉ số i (1 <= i <= N) sao cho tổng của các phần tử từ 1 đến i bằng tổng của các phần tử từ i đến N. (Lưu ý: A[i] được tính trong cả hai tổng). A[1] + ... + A[i] = A[i] + ... + A[N]. Nếu có nhiều chỉ số i thỏa mãn, in ra chỉ số i nhỏ nhất. Nếu không có, in -1.

Gợi ý: P[i] = S[i] (với P là prefix sum, S là suffix sum).

Input:

Dòng đầu tiên chứa N (1 <= N <= 10^5).

Dòng thứ hai chứa N số A[i] (1 <= A[i] <= 1000).

Output:

In ra chỉ số i nhỏ nhất thỏa mãn, hoặc -1.

Ví dụ:

Input:

7
1 2 3 6 3 2 1

Output:

4

(Giải thích: i=4. Tổng trái: A[1..4] = 1+2+3+6 = 12 Tổng phải: A[4..7] = 6+3+2+1 = 12 Hai tổng bằng nhau tại i=4.)

Cho một mảng A gồm N số nguyên dương. Tìm chỉ số i (1 <= i < N) sao cho trung bình cộng của đoạn A[1...i] bằng trung bình cộng của đoạn A[i+1...N]. Nếu có nhiều chỉ số, in ra i nhỏ nhất. Nếu không có, in -1.

Gợi ý: Sum(1..i) / i == Sum(i+1..N) / (N-i) P[i] / i == (Total - P[i]) / (N - i) P[i] * (N - i) == (Total - P[i]) * i (Giải phương trình này)

Input:

Dòng đầu tiên chứa N (2 <= N <= 10^5).

Dòng thứ hai chứa N số A[i] (1 <= A[i] <= 1000).

Output:

In ra chỉ số i nhỏ nhất thỏa mãn, hoặc -1.

Ví dụ:

Input:

5
1 5 2 2 5

Output:

2

(Giải thích: Total = 15, N=5. i=1: P[1]=1. 1(5-1) == (15-1)1 -> 4 == 14 (Sai) i=2: P[2]=6. 6(5-2) == (15-6)2 -> 63 == 92 -> 18 == 18 (Đúng!) Trung bình (1, 5) là 3. Trung bình (2, 2, 5) là 9/3 = 3.)

Cho một mảng A gồm N số nguyên và Q truy vấn. Mỗi truy vấn gồm 3 số (L, R, X). Với mỗi truy vấn, hãy đếm xem số X xuất hiện bao nhiêu lần trong đoạn A[L...R].

Gợi ý:

Cách 1 (Nếu N*Q nhỏ): Dùng O(N) cho mỗi truy vấn.

Cách 2 (Nếu N, Q lớn, nhưng giá trị A[i] nhỏ): Xây dựng mảng cộng dồn cho từng giá trị. P[X][i] = số lần X xuất hiện trong A[1...i].

Cách 3 (Nếu N, Q lớn, A[i] lớn): Dùng map<int, vector<int>> lưu các vị trí.

Ràng buộc (dùng cách 2):

1 <= N, Q <= 10^5

1 <= A[i] <= 100 (Giá trị A[i] nhỏ)

Input:

Dòng đầu tiên chứa N.

Dòng thứ hai chứa N số A[i] (1 <= A[i] <= 100).

Dòng thứ ba chứa Q.

Q dòng tiếp theo, mỗi dòng chứa L, R, X (1 <= L <= R <= N, 1 <= X <= 100).

Output:

In Q dòng, mỗi dòng là kết quả cho 1 truy vấn.

Ví dụ:

Input:

10
1 2 3 1 2 3 1 2 3 1
3
1 10 1
3 8 2
5 5 5

Output:

4
2
0

Cho một mảng A gồm N số nguyên (có thể âm). Tìm đoạn con A[L...R] có tổng lớn nhất.

Gợi ý (Dùng mảng cộng dồn): Tong(L..R) = P[R] - P[L-1]. Ta cần tìm max(P[R] - P[L-1]) với L <= R. Khi duyệt R từ 1 đến N, ta cần tìm P[L-1] nhỏ nhất (với L-1 < R). Hãy duy trì một biến minprefix (là P[L-1] nhỏ nhất đã gặp) khi duyệt. KetQua = max(KetQua, P[R] - minprefix)

Input:

Dòng đầu tiên chứa N (1 <= N <= 10^5).

Dòng thứ hai chứa N số A[i] (-10^9 <= A[i] <= 10^9).

Output:

In ra tổng lớn nhất.

Ví dụ:

Input:

8
-1 2 4 -3 5 2 -5 2

Output:

10

Cho mảng A (N số) và số K. Tìm hai đoạn con không giao nhau và đều có độ dài K sao cho tổng của chúng là lớn nhất. (Tức là tìm i, j sao cho [i, i+K-1] và [j, j+K-1] không giao nhau, và Tong(i...i+K-1) + Tong(j...j+K-1) là lớn nhất).

Gợi ý:

Dùng mảng cộng dồn tính TongK[i] = tổng của đoạn K phần tử kết thúc tại i.

Xây dựng mảng MaxLeft[i] = tổng K lớn nhất trong đoạn [1, i].

Xây dựng mảng MaxRight[i] = tổng K lớn nhất trong đoạn [i, N].

Duyệt i từ 1 đến N-K. Kết quả = max(MaxLeft[i] + MaxRight[i+K]).

Input:

Dòng đầu tiên chứa N và K (2*K <= N <= 10^5).

Dòng thứ hai chứa N số A[i] (1 <= A[i] <= 1000).

Output:

In ra tổng lớn nhất của hai đoạn K.

Ví dụ:

Input:

8 2
1 5 2 4 8 1 3 2

Output:

19

Giải thích:

Đầu vào: N = 8, K = 2 Mảng A: [1, 5, 2, 4, 8, 1, 3, 2]

Liệt kê tất cả các đoạn con (dài 2) và tổng của chúng:

Đoạn 1 (vị trí 1, 2): [1, 5] ➜ Tổng = 6

Đoạn 2 (vị trí 2, 3): [5, 2] ➜ Tổng = 7

Đoạn 3 (vị trí 3, 4): [2, 4] ➜ Tổng = 6

Đoạn 4 (vị trí 4, 5): [4, 8] ➜ Tổng = 12

Đoạn 5 (vị trí 5, 6): [8, 1] ➜ Tổng = 9

Đoạn 6 (vị trí 6, 7): [1, 3] ➜ Tổng = 4

Đoạn 7 (vị trí 7, 8): [3, 2] ➜ Tổng = 5

Tìm cặp tốt nhất không giao nhau:

Đoạn tốt nhất (Lớn nhất): Đoạn [4, 8] (vị trí 4, 5) có tổng là 12.

Đoạn tốt nhất còn lại (Không giao):

Vì ta đã chọn đoạn ở vị trí 4 và 5, chúng ta không được chọn bất kỳ đoạn nào khác chạm vào vị trí 4 hoặc 5.

Ta phải loại:

[2, 4] (vì chạm vị trí 4)

[8, 1] (vì chạm vị trí 5)

Các lựa chọn còn lại của chúng ta là:

[1, 5] (Tổng 6)

[5, 2] (Tổng 7)

[1, 3] (Tổng 4)

[3, 2] (Tổng 5)

Trong số này, đoạn tốt nhất là [5, 2] với tổng là 7.

Kết quả: Tổng của hai đoạn tốt nhất không giao nhau là: 12 + 7 = 19.