Mảng A ban đầu toàn 0. Sau Q thao tác cập nhật [L, R] tăng thêm 1. Hãy đếm xem trong mảng kết quả, có bao nhiêu phần tử có giá trị đúng bằng K.

Input:

Dòng 1: N, Q, K.

Q dòng tiếp: L, R (mặc định V=1).

Output:

Số lượng phần tử có giá trị bằng K.

Test Case 1:

Input:

6 3 2
1 4
3 6
2 5

Output:

2

Test Case 2:

Input:

5 2 1
1 2
4 5

Output:

4

(Mảng: 1 1 0 1 1. Có 4 số 1)

Đây là bài toán ngược. Cho mảng hiệu D (Difference Array) của một mảng A (với D[i] = A[i] - A[i-1], quy ước A[0]=0). Hãy khôi phục và in ra mảng A.

Input:

Dòng 1: N.

Dòng 2: N số nguyên là mảng D.

Output:

Mảng A.

Test Case 1:

Input:

5
2 1 2 -3 1

Output:

2 3 5 2 3

Test Case 2:

Input:

4
1 1 1 1

Output:

1 2 3 4

Một nhà hàng mở cửa từ thời điểm 1 đến N. Có Q vị khách, khách thứ i đến vào thời điểm L và rời đi vào thời điểm R. Hãy tìm thời điểm có nhiều khách ngồi trong nhà hàng nhất.

Input:

Dòng 1: N, Q.

Q dòng: L, R.

Output:

Số lượng khách lớn nhất tại một thời điểm.

Test Case 1:

Input:

10 3
1 5
4 8
2 6

Output:

3

(Tại thời điểm 4 và 5 có cả 3 khách)

Test Case 2:

Input:

5 2
1 2
4 5

Output:

1

Mảng A ban đầu toàn 0. Sau Q cập nhật [L, R] tăng V. Tính tổng các phần tử tại vị trí chẵn (2, 4, 6...) của mảng A.

Input:

Dòng 1: N, Q.

Q dòng: L, R, V.

Output:

Tổng các phần tử vị trí chẵn.

Test Case 1:

Input:

5 2
1 3 1
3 5 2

Output:

3

(Mảng: 1 1 3 2 2. Vị trí chẵn là A[2]=1, A[4]=2. Tổng = 3)

Test Case 2:

Input:

4 1
1 4 10

Output:

20

Có N khu vườn. Có Q vòi phun nước. Vòi thứ i tưới cho đoạn [L, R] với lượng nước là V. Tuy nhiên, có K khu vườn bị hỏng hệ thống thoát nước (biết chỉ số), nên lượng nước tại các khu này bị giảm đi một nửa (làm tròn xuống). Tính tổng lượng nước của cả nông trại.

Input:

Dòng 1: N, Q, K.

Q dòng: L, R, V.

Dòng cuối: K chỉ số khu vườn bị hỏng.

Output:

Tổng lượng nước.

Test Case 1:

Input:

5 1 1
1 5 10
3

Output:

45

(Mảng nước: 10 10 10 10 10. Khu 3 bị hỏng -> 10 10 5 10 10. Tổng 45)

Test Case 2:

Input:

4 1 2
1 4 10
1 2

Output:

30

(Mảng: 5 5 10 10)

Cho ma trận N x N toàn 0. Thực hiện Q truy vấn: Cộng V vào hình chữ nhật có góc trên trái (x1, y1) và góc dưới phải (x2, y2). In ra giá trị tại ô (x, y) bất kỳ cuối cùng.

Gợi ý:

D[x1][y1] += V

D[x1][y2+1] -= V

D[x2+1][y1] -= V

D[x2+1][y2+1] += V

Sau đó cộng dồn 2 chiều.

Input:

Dòng 1: N, Q.

Q dòng: x1, y1, x2, y2, V.

Dòng cuối: x, y (tọa độ cần in).

Output:

Giá trị tại A[x][y].

Test Case 1:

Input:

5 2
1 1 3 3 1
2 2 4 4 2
3 3

Output:

3

(Ô (3,3) thuộc cả 2 hình chữ nhật nên 1+2=3)

Test Case 2:

Input:

5 1
1 1 2 2 10
3 3

Output:

0

Mảng A ban đầu toàn 0. Sau Q truy vấn cập nhật [L, R] tăng V. Hãy in ra:

Giá trị lớn nhất của mảng (MaxVal).

Số lượng phần tử đạt giá trị MaxVal đó.

Input:

Dòng 1: N, Q.

Q dòng: L, R, V.

Output:

Hai số: MaxVal và Count.

Test Case 1:

Input:

5 3
1 3 2
3 5 2
2 4 1

Output:

5 1

(Mảng: 2 3 5 3 2. Max là 5, xuất hiện 1 lần)

Test Case 2:

Input:

5 2
1 4 1
2 5 1

Output:

2 3

(Mảng: 1 2 2 2 1. Max là 2, xuất hiện 3 lần)

Cho một ma trận số nguyên A có kích thước M × N (gồm M hàng và N cột). Các hàng được đánh số từ 1 đến M, các cột được đánh số từ 1 đến N.

Có Q truy vấn. Mỗi truy vấn cung cấp một tọa độ giao điểm (r, c) nằm trong ma trận (1 ≤ r < M, 1 ≤ c < N). Điểm giao cắt này sẽ chia ma trận ban đầu thành 4 hình chữ nhật con riêng biệt:

1. Góc Trên-Trái (Top-Left): Các ô từ hàng 1 đến hàng r, từ cột 1 đến cột c.

2. Góc Trên-Phải (Top-Right): Các ô từ hàng 1 đến hàng r, từ cột c + 1 đến cột N.

3. Góc Dưới-Trái (Bottom-Left): Các ô từ hàng r + 1 đến hàng M, từ cột 1 đến cột c.

4. Góc Dưới-Phải (Bottom-Right): Các ô từ hàng r + 1 đến hàng M, từ cột c + 1 đến cột N

Yêu cầu: Với mỗi truy vấn, hãy tính và in ra tổng các phần tử của 4 hình chữ nhật con nói trên.

Input:

• Dòng đầu tiên chứa 3 số nguyên M, N, Q (2 ≤ M, N ≤ 1000, 1 ≤ Q ≤ 100,000).

• M dòng tiếp theo, mỗi dòng chứa N số nguyên biểu diễn ma trận A. Giá trị các phần tử | Ai,j| ≤ 1000.

• Q dòng tiếp theo, mỗi dòng chứa 2 số nguyên r, c (1 ≤ r < M, 1 ≤ c < N) biểu thị vị trí cắt.

Output:

• Gồm Q dòng tương ứng với Q truy vấn.

• Mỗi dòng in ra 4 số nguyên lần lượt là tổng của: Trên-Trái, Trên-Phải, Dưới-Trái, Dưới-Phải. Các số cách nhau bởi dấu cách. Giới hạn:

• Thời gian (Time Limit): 1 giây.

• Bộ nhớ (Memory Limit): 256 MB.

• Lưu ý: Thuật toán có đô phức tạp O(M x N) cho mỗi truy vấn sẽ bị quá thời gian (TLE).

Ví dụ:

Input:

4 4 2
1 1 2 2
1 1 2 2
3 3 4 4
3 3 4 4
2 2
1 3

Output:

4 8 12 16
4 2 24 10

Giải thích ví dụ:

Truy vấn 1 (r=2, c=2):

• Trên-Trái: (1,1) đến (2,2) gồm {1,1,1,1} - Tổng = 4.

• Trên-Phải: (1,3) đến (2,4) gồm {2,2,2,2} -> Tổng = 8.

• Dưới-Trái: (3,1) đến (4,2) gồm {3,3,3,3} -> Tổng = 12.

• Dưới-Phải: (3,3) đến (4,4) gồm {4,4,4,4} -> Tổng = 16.

Mô tả: Cho mảng A các số dương. Một thao tác chọn đoạn [L, R] và giảm tất cả đi 1. Tìm số thao tác ít nhất để toàn bộ mảng bằng 0.

Input:

• Dòng 1: N (1 ≤ N ≤ 10^5).

• Dòng 2: A; (0 ≤ Ai ≤ 10^9).

Output: Số thao tác tối thiểu.

Ví dụ:

Input:

5
1 2 2 1 0

Output:

2

Cho một ma trận A kích thước N × M gồm các số nguyên không âm. Hãy đếm số lượng hình chữ nhật con (submatrix) có tổng các phần tử đúng bằng K.

Input:

• Dòng 1: Ba số nguyên N, M, K (1 ≤ N,M ≤ 500,0 ≤ K ≤ 10°).

• N dòng tiếp theo: Mỗi dòng chứa M số nguyên biểu diễn ma trận A (0 ≤ Ai,j ≤ 1000).

Output:

• Một số nguyên duy nhất là số lượng hình chữ nhật con thỏa mãn.

Ví dụ:

Input:

2 2 2
1 1
1 1

Output:

4

Cho một ma trận nhị phân A kích thước N x M chỉ chứa các số 0 và 1. Hãy tìm kích thước cạnh của hình vuông lớn nhất trong ma trận mà chỉ chứa toàn số 1.

Input:

• Dòng 1: Hai số nguyên N, M (1 ≤ N, M ≤ 2000).

• N dòng tiếp theo: Mỗi dòng chứa M số nguyên (chỉ 0 hoặc 1) biểu diễn ma trận A.

Output:

• Một số nguyên duy nhất là độ dài cạnh của hình vuông lớn nhất tìm được.

Vi dụ:

Input:

3 3
0 1 1
1 1 1
0 1 1

Output:

2

Giải thích: