Cho một mảng gồm n số nguyên, nhiệm vụ của bạn là đếm số mảng con (dãy con các phần tử liên tiếp) mà tổng các giá trị chia hết cho n.

Đầu vào: Dòng nhập đầu tiên có số nguyên n: kích thước của mảng. Dòng tiếp theo có n số nguyên a1, a2,..., an: nội dung của mảng.

Ràng buộc: 1≤n≤2.10^5; 1≤ai≤10^9

Input 01:

5
2 3 2 5 1

Output 01:

4

Input 02:

5
8 2 3 1 7

Output 02:

2

Cho mắng A[] gồm N phần tử và số nguyên dương K nhiệm vụ của bạn là tìm dãy con liên tiếp dài nhất có tổng chia hết cho K.

Định dạng đầu vào: Dòng thứ nhất gồm N, K; Dòng thứ 2 gồm các phần tử trong mảng A[].

Ràng buộc: 1<=K<=N<=10^6; -10^6<=A[i]<=10^6;

Định dạng đầu vào: In ra dãy con dài nhất hoặc in ra -1 nếu không tồn tại dãy con chia hết cho K.

Input:

12 2
-4 1 4 -4 4 4 -3 4 2 -4 2 4

Output:

12

Đề bài: Cho một mảng A gồm N số nguyên. Hãy tìm một chỉ số i (1 < i < N) sao cho tổng các phần tử bên trái i (từ A[1] đến A[i - 1]) bằng tổng các phần tử bên phải i (từ A[i + 1] đến A[N]). Nếu có nhiều chỉ số thỏa mẫn, in ra chỉ số nhỏ nhất. Nếu không có chỉ số nào thỏa mãn, in ra -1.

Input:

• Dòng đầu tiên chứa số nguyên N.

• Dòng thứ hai chứa N số nguyên Ai.

Output:

• In ra chỉ số i nhỏ nhất thỏa mãn, hoặc -1 nếu không tồn tại.

Ràng buộc:

3 < N <10^5

-1000 ≤ Ai ≤ 1000

Ví dụ:

Input:

6
1 7 3 6 5 6

Output:

4

(Giải thích: A[1]+A[2]+A[3] = 1+7+3 = 11. A[5]+A[6] = 5+6 = 11. Chỉ số 4 thỏa mãn)

Cho một mảng A gồm N số nguyên và Q truy vấn. Mỗi truy vấn gồm hai số L và R. Với mỗi truy vấn, hãy tính giá trị của biểu thức A[L] - A[L+1] + A[L+2] - A[L+3] + ... trong đoạn [L, R].

Input:

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

Dòng thứ hai chứa N số nguyên A[i].

Dòng thứ ba chứa số nguyên Q.

Q dòng tiếp theo, mỗi dòng chứa hai số nguyên L và R.

Output:

Với mỗi truy vấn, in ra kết quả tính được trên một dòng.

Ràng buộc:

1 <= N <= 10^5

1 <= Q <= 10^5

-1000 <= A[i] <= 1000

1 <= L <= R <= N

Ví dụ:

Input:

8
1 2 3 4 5 6 7 8
3
1 8
2 5
3 7

Output:

-4
-2
5

Giải thích 1: 1-2+3-4+5-6+7-8 = -4.

Giải thích 2: 2-3+4-5 = -2.

Giải thích 3: 3-4+5-6+7 = 5.

Cho một mảng A gồm N số nguyên và Q truy vấn. Mỗi truy vấn gồm hai số L và R. Với mỗi truy vấn, hãy đếm xem có bao nhiêu số 0 trong đoạn từ A[L] đến A[R].

Input:

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

Dòng thứ hai chứa N số nguyên A[i].

Dòng thứ ba chứa số nguyên Q.

Q dòng tiếp theo, mỗi dòng chứa hai số nguyên L và R.

Output:

Với mỗi truy vấn, in ra số lượng số 0 tìm được.

Ràng buộc:

1 <= N <= 10^5

1 <= Q <= 10^5

-1000 <= A[i] <= 1000

1 <= L <= R <= N

Ví dụ:

Input:

10
1 0 2 0 0 5 0 8 9 0
3
1 5
2 7
6 10

Output:

3
4
2

Cho một mảng A gồm N số nguyên và một số nguyên K. Tìm một đoạn con liên tiếp gồm đúng K phần tử có tổng lớn nhất. In ra tổng lớn nhất đó.

Input:

Dòng đầu tiên chứa hai số nguyên N và K.

Dòng thứ hai chứa N số nguyên A[i].

Output:

In ra một số nguyên duy nhất là tổng lớn nhất tìm được.

Ràng buộc:

1 <= K <= N <= 10^5

-1000 <= A[i] <= 1000

Ví dụ:

Input:

8 3
1 5 2 4 8 1 3 2

Output:

14

(Giải thích: Đoạn [2, 4, 8] có tổng là 14, là lớn nhất trong các đoạn con có độ dài 3.)

Cho một mảng A gồm N số nguyên và một số nguyên K. Hãy kiểm tra xem có tồn tại một đoạn con liên tiếp A[L...R] (1 <= L <= R <= N) có tổng bằng K hay không. Nếu có, in ra "YES", ngược lại in ra "NO".

Input:

Dòng đầu tiên chứa hai số nguyên N và K.

Dòng thứ hai chứa N số nguyên A[i].

Output:

In ra "YES" nếu tồn tại đoạn con có tổng bằng K, ngược lại in ra "NO".

Ràng buộc:

1 <= N <= 2000

-10^9 <= K <= 10^9

-10^6 <= A[i] <= 10^6

Ví dụ:

Input:

7 10
1 3 5 2 4 1 9

Output:

YES

(Giải thích: A[2...4] = 3+5+2 = 10.)

Cho một mảng A gồm N số nguyên. Hãy tạo và in ra mảng cộng dồn ngược S (mảng hậu tố) của mảng A, trong đó S[i] là tổng của các phần tử từ i đến N (tức là S[i] = A[i] + A[i+1] + ... + A[N]).

Input:

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

Dòng thứ hai chứa N số nguyên A[i].

Output:

In ra N số nguyên là các phần tử của mảng cộng dồn ngược S, cách nhau bởi dấu cách.

Ràng buộc:

1 <= N <= 10^5

-1000 <= A[i] <= 1000

Ví dụ:

Input:

5
1 3 5 2 4

Output:

15 14 11 6 4

Cho một mảng A gồm N số nguyên và Q truy vấn. Mỗi truy vấn gồm 4 số L1, R1, L2, R2. Với mỗi truy vấn, hãy so sánh tổng của đoạn A[L1...R1] (đoạn 1) và A[L2...R2] (đoạn 2).

In ra "DOAN 1" nếu tổng đoạn 1 lớn hơn.

In ra "DOAN 2" nếu tổng đoạn 2 lớn hơn.

In ra "BANG NHAU" nếu hai tổng bằng nhau.

Input:

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

Dòng thứ hai chứa N số nguyên A[i].

Dòng thứ ba chứa số nguyên Q.

Q dòng tiếp theo, mỗi dòng chứa 4 số nguyên L1, R1, L2, R2.

Output:

Với mỗi truy vấn, in ra kết quả so sánh trên một dòng.

Ràng buộc:

1 <= N <= 10^5

1 <= Q <= 10^5

-1000 <= A[i] <= 1000

1 <= L1 <= R1 <= N

1 <= L2 <= R2 <= N

Ví dụ:

Input:

8
1 2 3 4 5 6 7 8
3
1 3 4 5
1 4 6 7
1 1 3 3

Output:

DOAN 2
DOAN 2
DOAN 2

(Giải thích 1: 1+2+3=6. 4+5=9. Giải thích 2: 1+2+3+4=10. 6+7=13. Giải thích 3: 1. 3.)

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, mỗi phép cập nhật gồm 3 số L, R, V, yêu cầu tăng tất cả các phần tử từ A[L] đến A[R] lên V đơn vị. Sau khi thực hiện tất cả Q phép cập nhật, hãy in ra mảng A cuối cùng.

Input:

Dòng đầu tiên chứa hai số nguyên N và Q.

Q dòng tiếp theo, mỗi dòng chứa ba số nguyên L, R, V.

Output:

In ra N số nguyên là các phần tử của mảng A cuối cùng, cách nhau bởi dấu cách.

Ràng buộc:

1 <= N <= 10^5

1 <= Q <= 10^5

1 <= L <= R <= N

-1000 <= V <= 1000

Ví dụ:

Input:

5 3
1 3 10
2 4 5
3 5 2

Output:

10 15 17 7 2

(Giải thích: Ban đầu: [0, 0, 0, 0, 0] Sau (1 3 10): [10, 10, 10, 0, 0] Sau (2 4 5): [10, 15, 15, 5, 0] Sau (3 5 2): [10, 15, 17, 7, 2])

Cho mảng A gồm N phần tử, mảng B gồm M phần tử. Bạn sẽ thực hiện N - M + 1 thao tác, trong đó thao tác thứ i diễn ra như sau:

Xét các phần tử Ai, A(i+1), ..., A(i+M-1) và tăng chúng lần lượt lên B1, B2, ..., BM (Hay nói cách khác, Ai+j-1 sẽ được tăng lên Bj).

Bạn cần in ra dãy A sau khi thực hiện hết các thao tác.

Đầu vào:

Dòng đầu tiên gồm hai số nguyên dương N và M (1 <= M <= N <= 10^5)

Dòng thứ hai gồm N số nguyên dương miêu tả dãy A (Ai <= 10^9)

Dòng thứ ba gồm M số nguyên dương miêu tả dãy B (Bi <= 10^9)

Đầu ra:

In ra dãy A sau khi thực hiện các thao tác.

Input:

3 2
5 1 3
1 2

Output:

6 4 5