Chuyên đề. Prefix Sum

Cho dãy số nguyên dương gồm \(N\) phần tử \(a_1,a_2,..,a_N\) và số nguyên dương \(K\). Chọn ra \(K\) phần tử liên tiếp sao cho tổng của chúng là lớn nhất. In ra giá trị đó

Input

• Dòng 1: hai số nguyên dương \(N\) và \(K\) \((K \le N \le 10^5)\);
• Dòng 2: gồm \(N\) số nguyên dương \(a_1,a_2,...,a_N\) \((a_i \le 10^9)\)

Output

• In ra đáp án thỏa mãn yêu cầu đề bài.

Example

6 2
2 4 5 2 9 1 

11

Cho dãy số nguyên gồm n phần tử \(a_1,a_2,\cdots,a_n\) \((|a_i| \leq 10^9)\). Cho giá trị \(x\) và \(q\) câu hỏi có dạng \(S(u,v)\). Với \(S(u,v)\) là tổng các giá trị của các phần tử từ \(u\) đến \(v\).

Yêu cầu: Đếm xem trong \(q\) câu hỏi đó có bao câu hỏi có giá trị nhỏ hơn \(x\).

Input

• Dòng đầu tiên chứa ba số nguyên dương \(n,x,q (x \leq 10^9,q \leq 10^5)\).
• Dòng thứ hai chứa \(a_1,a_2,\cdots,a_n (|a_i| \leq 10^9)\).
• \(q\) dòng tiếp theo, mỗi dòng chứa hai số nguyên dương \(u,v (1 \leq u \leq v \leq n)\).

Output

• In ra một số nguyên là số lượng câu hỏi có giá trị nhỏ hơn \(x\)

Scoring

• Subtask \(1\) (\(50\%\) số điểm): \(n \leq 500\)
• Subtask \(2\) (\(30\%\) số điểm): \(n \leq 10^4\)
• Subtask \(3\) (\(30\%\) số điểm): \(n \leq 10^5\)

Example

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

2

Cho một mảng gồm \(n\) số nguyên, nhiệm vụ của bạn là tìm tổng giá trị tối đa của một đoạn con khác rỗng.

Input

• Dòng đầu vào đầu tiên có một số nguyên \(n\): kích thước của mảng.
• Dòng thứ hai có \(n\) số nguyên \(x_1, x_2, \ldots, x_n\): các giá trị của mảng.

Output

• In một số nguyên duy nhất là tổng đoạn con lớn nhất.

Constraints

• \(1 \leq n \leq 2 \cdot 10^5\)
• \(-10^9 \leq x_i \leq 10^9\)

Example

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

9

Cho một số nguyên dương \(n\) và một mảng \(A\) chứa \(n\) số nguyên (có thể âm). Bạn muốn cắt một nhát cắt trên mảng đó để chia mảng đó thành hai đoạn trái và phải, sao cho cả hai đoạn đều có ít nhất một phần tử và tổng các phần tử của hai đoạn bằng nhau.

Đề bài yêu cầu đếm có bao nhiêu cách cắt thỏa mãn điều kiện trên.

Input

• Dòng đầu tiên chứa một số nguyên dương \(n\) \((1 \leq n \leq 2*10^5)\)
• Dòng thứ hai chứa \(n\) số nguyên \(A_i,\) là số thứ \(i\) của mảng \(A (|A_i| \leq 10^9)\)

Output

• Số cách cắt mảng \(A\) cho trước, sao cho tổng của phân đoạn trái và phân đoạn phải sau khi cắt có tổng các phần tử bằng nhau.

Example

4
1 2 2 1

1

6
1 1 1 3 -3 3

2

Cho một mảng gồm \(n\) số nguyên và số nguyên \(t\).

Yêu cầu: Tìm mảng con gồm những phần tử liên tiếp dài nhất sao cho tổng tất cả các phần tử của mảng này không quá \(t\). Và số lượng phần tử của mảng này chính là kết quả cần tìm.

Input

• Dòng thứ nhất chứa hai số nguyên \(n,t(1\le n\le 10^5;1\le t\le 10^9)\)

• Dòng thứ hai chứa \(n\) số nguyên \(a_1,a_2,...,a_n(1\le a_i\le 10^4)\)

Output

• In ra giá trị cần tìm.

Example

4 4
1 2 1 2

3

Lập trình giải bài toán cổ tổng quát: Có tổng số \(n\) tổng số con, \(m\) là tổng số chân. Hãy đưa ra số lượng gà, chó.

Vừa gà vừa chó
Bó lại cho tròn
Ba mươi sáu con    
Một trăm chân chẵn    
Hỏi có mấy con gà, mấy con chó?

Input

• Gồm một dòng ghi hai số nguyên \(n, m\) \((1 \le n,m \le 1000)\).

Output

• Ghi hai số nguyên trên một dòng tương ứng là số lượng gà, số lượng chó.

Example

36 100

22 14

Cho dãy gồm \(N\) số nguyên, hãy in ra các phần tử là số chẵn trong dãy đó.

Input

• Dòng đầu ghi số nguyên \(N\) \((1 \le N \le 10^6)\)

• Dòng thứ hai ghi \(N\) số nguyên cách nhau bởi dấu cách, các số có giá trị tuyệt đối không quá \(10^6\) \((|a_{i}| \le 10^6)\)

Output

Dòng thứ hai ghi các phần tử là số chẵn theo thứ tự xuất hiện trong input, các số trên một dòng và cách nhau bởi dấu cách.

Example

5
1 2 3 4 5 

2 4

Cho một mảng gồm \(n\) số nguyên, nhiệm vụ của bạn là xử lý \(q\) truy vấn có dạng: tổng các phần tử trong đoạn \([a, b]\) là bao nhiêu?

Input

• Dòng đầu tiên là hai số nguyên \(n\) và \(q\): số phần tử và truy vấn
• Dòng thứ hai là \(n\) số nguyên \(x_1, x_2,\ldots, x_n\): các phần tử của mảng
• \(q\) dòng cuối cùng là các truy vấn. Mỗi dòng là hai số nguyên \(a\) và \(b\): tổng các phần tử trong đoạn \([a, b]\) là bao nhiêu?

Constraints

• \(1 \leq n, q \leq 2\cdot 10^5\)
• \(1 \leq x_i \leq 10^9\)
• \(1 \leq a \leq b \leq n\)

Output

• In ra đáp án của mỗi truy vấn

Example

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

11
2
24
4

Trong một kỳ thi, việc sáng tạo bài dễ nhất trong đề thi nhiều khi cũng mất không ít thời gian. Trong đề thi Duyên Hải năm 2021, Ban giám khảo muốn tạo một bài dễ thao tác trên dãy số cho các học sinh khối 10. Bài toán dưới đây đã được sáng tạo và chọn vào đề thi, bài toán này có thể giải được bằng nhiều thuật toán khác nhau.

Cho dãy số nguyên \(a_1, a_2, ..., a_n\), một đoạn \(a_L, a_{L+1},..., a_R (1 \le L \le R \le N)\) được gọi là đoạn đẹp nếu \(L, R\) đều là số nguyên tố. Hãy tìm đoạn đẹp có tổng lớn nhất.

Input

Vào từ thiết bị vào chuẩn theo khuôn dạng:

• Dòng đầu chứa số nguyên dương \(n (n \ge 2)\);
• Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, ..., a_n (|a_i| \le 10^6)\)

Output

• Ghi ra thiết bị ra chuẩn một số nguyên là tổng lớn nhất của đoạn đẹp tìm được.

Scoring

• Subtask \(1\) (\(40\%\) số điểm): \(n \le 100\);
• Subtask \(2\) (\(30\%\) số điểm): \(n \le 3000\);
• Subtask \(3\) (\(30\%\) số điểm): \(n \le 10^6\);

Example

6
9 5 -2 6 -1 1

8

Bạn được cho một dãy số \(a\) gồm \(n\) số nguyên. Nhiệm vụ của bạn là tìm số cặp số \((i,j) \ 1 \leq i \leq j \leq n\) sao cho \(a_i + a_{i+1} + ... + a_j = 0\)

Input

• Dòng đầu tiên chứa số nguyên dương \(n \ (1 \leq n \leq 10^5)\) - là số phần tử của mảng.
• Dòng thứ hai chứa \(n\) số nguyên, số thứ \(i\) là \(a_i\) \(( \mid a_i\mid \leq 10^9)\)

Output

• Số lượng cặp số \((i,j)\) thõa mãn điều kiện trên

Example

4
-3 3 -4 4

3

Cho dãy số nguyên gồm \(N\) phần tử. Tìm:

• Dãy con khác rỗng có tổng các phần tử là lớn nhất. (Các phần tử có thể không liên tiếp)
• Dãy con gồm các phần tử liên tiếp có tổng lớn nhất.

Input

• Gồm nhiều test, dòng đầu tiên là số lượng test \(T\) \((1≤T≤10)\)
• Mỗi bộ test gồm hai dòng:
  • Dòng đầu là số nguyên dương \(N\) là số lượng phần tử của dãy \((1≤N≤10^5)\)
  • Dòng tiếp theo gồm \(N\) số nguyên trong khoảng \([−10^4,10^4]\)

Output

• Với mỗi bộ test, in ra trên một dòng, hai số là hai tổng theo yêu cầu.

Example

2
3
4 4 2
5
3 3 -2 3 -4 

10 10
9 7

Một xâu gọi là xâu nhị phân nếu chỉ chứa hai ký tự \(0\) hoặc \(1\).

Xâu \(v\) gọi là xâu con của \(w\) nếu xâu \(v\) có độ dài khác 0 và gồm các ký tự liên tiếp trong xâu \(w\).

Ví dụ: xâu \(010\) có các xâu con là: \(0, 1, 0, 01, 10, 010\).

Yêu cầu: Cho trước một giá trị \(k\), hãy đếm xem có bao nhiêu xâu con chứa đúng \(k\) ký tự \(1\).

Input

• Dòng \(1\): chứa một số nguyên \(k (0 \leq k \leq 10^6)\).
• Dòng \(2\): chứa một xâu nhị phân có độ dài \(\leq 10^6\).

Output

• Ghi ra một số nguyên duy nhất là kết quả tìm được.

Scoring

• \(len(s)\) là độ dài xâu nhị phân.
• Subtask \(1\) (\(40\%\) số điểm): \(1 \leq k \leq len(s) \leq 500\).
• Subtask \(2\) (\(30\%\) số điểm): \(1000 \leq k \leq len(s) \leq 10000\).
• Subtask \(3\) (\(30\%\) số điểm): \(10^5 \leq k \leq len(s) \leq 10^6\).

Example

2
01010 

4

Cho một dãy số nguyên \(a_1, a_2, a_3, …, a_n\) và một số nguyên \(k\). Một dãy con \(1 \leq i \leq j \leq n\) được gọi là hoàn hảo nếu như \(a_i + a_{i + 1} + a_{i + 2} + … + a_j = k\).

Yêu cầu: Hãy đếm xem có bao nhiêu dãy con hoàn hảo từ dãy đã cho.

Input

• Dòng đầu tiên chứa số \(n \ (n \leq 10^5)\) và \(k \ (|k| \leq 10^4)\) cách nhau bởi dấu cách.
• Dòng tiếp theo chứa \(n\) số nguyên \(a_i \ (|a_i| \leq 10^4)\).

Output

• Một số duy nhất là kết quả tìm được.

Scoring

• Subtask \(1\) (\(50\%\) số điểm): \(n \leq 100\).
• Subtask \(2\) (\(30\%\) số điểm): \(n \leq 5000\).
• Subtask \(3\) (\(20\%\) số điểm): Không có ràng buộc gì thêm.

Example

5 5
1 2 3 4 5 

2

An và Bình là hai anh em.


Ba của An sau một chuyến đi công tác xa nhà trở về, mua cho An và Bình \(N\) gói kẹo, gói thứ \(i\) có \(A_i\) viên kẹo.


Để tránh việc tranh giành kẹo lẫn nhau, ba của An đã thống nhất việc chia kẹo theo cách sau:


- Trước hết, ba của An chọn ra một số nguyên \(k\) (với \(1 \leq k \leq N\))


- An sẽ được chia các gói kẹo từ \(1\) đến \(k\). Phần còn lại (các gói kẹo từ \(k + 1\) đến \(N\)) sẽ được chia cho Bình.

Để tránh sự phân bua giữa hai anh em, ba của An muốn lựa chọn chỉ số \(k\) sao cho chênh lệch giữa tổng số lượng viên kẹo của hai anh em là nhỏ nhất có thể. Hãy giúp ông thực hiện điều này.

Input

• Dòng đầu tiên gồm số nguyên \(N (2 \leq N \leq 200000)\) - số gói kẹo.
• Dòng thứ hai gồm \(N\) số nguyên \(A_1, A_2, ..., A_N (1 \leq A_i \leq 10^9)\) - số viên kẹo trong từng gói kẹo.

Output

• In ra chênh lệch lượng kẹo nhỏ nhất có thể.

Scoring

• Subtask \(1\) (\(50\%\) số điểm): \(N \le 2000\).
• Subtask \(2\) (\(50\%\) số điểm): không có ràng buộc gì thêm.

Example

5
5 1 3 2 6

1

6
4 5 3 6 1 2

3

2
100 100

0

Nguồn: Free Contest

Một công ty xây dựng nọ đang lên kế hoạch cho việc sửa chữa một con đường cao tốc có chiều dài là \(n\) kilomet. Con đường này được đánh số từ \(1\) đến \(n+1\) tại những vị trí cách đều nhau đúng \(1\) kilomet, bắt đầu từ vị trí đầu của con đường. Chi phí sửa chữa cho đoạn \(1\) kilomet từ vị trí \(i\) đến \(i+1\) là \(A_i\) với \(1 \le i \le n\).

Một kiến trúc sư người Ý đảm nhiệm vai trò này và đang khảo sát mức độ hư hại cũng như chi phí để sửa chữa con đường này. Do kinh phí thời điểm hiện tại không đủ để thi công một lúc cả con đường. Anh ấy kế hoạch tính toán để chọn ra đoạn đường phù hợp nhất để sửa chữa đầu tiên. Anh ấy khảo sát con đường bằng cách chọn ra một đoạn từ vị trí \(L\) đến vị trí \(R\) trên con đường và tính xem chi phí sửa chữa trung bình trên \(1\) kilomet của đoạn này là bao nhiêu.

Yêu cầu: Cho \(Q\) câu truy vấn \((L, R)\). Hãy tính chi phí sửa chữa trung bình trên \(1\) kilomet của vị trí \(L\) đến vị trí \(R\).

Input

• Dòng đầu tiên gồm số \(n\).
• Dòng thứ hai gồm \(n\) số nguyên \(A_i\).
• Dòng thứ ba là số \(Q\) – số lượng câu truy vấn.
• Q dòng tiếp theo, mỗi dòng gồm 2 số \(L\) và \(R (L<R)\).

Output

• Gồm \(Q\) dòng tương ứng là kết quả của câu truy vấn thứ \(i\), kết quả được làm tròn đến chữ số thập phân thứ \(6\).

Scoring

• \(0 \le A_i \le 10^9\)
• Subtask \(1\) (\(70\%\) số điểm): \(1 \le q,n \le 10^3\).
• Subtask \(2\) (\(30\%\) số điểm): \(1 \le q,n \le 5*10^4\).

Example

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

2.000000
3.000000
4.500000

Tiền sĩ Hùng là một nhà nghiên cứu về các con số. Đề tài lần này ông được giao nhiệm vụ tìm ra một bài toán để kiểm tra năng lực của các học viên trong phòng thí nghiệm của ông. Nhưng tất cả các học viên của ông đều rất thông minh nên để thử tài họ phải là một bài toán cực khó. Con trai của ông năm nay vào lớp 3. Do ảnh hưởng của bố nên cậu ta cũng rất hứng thú với những con số. Trong khi Hùng đang nát óc nghĩ bài toán thì con trai của ông chỉ vào đống tài liệu về các dãy bit gồm toàn số \(0, 1\) và khoái chí nói rằng: “Ba ơi, đoạn bit này có \(5\) số \(0\) và \(5\) số \(1\) ba ạ. Con rất thích những thứ cân bằng như thế !!”. Cậu con trai vừa dứt lời, Hùng liền nghĩ ngay ra bài toán để thách đố học viên của mình. Quả nhiên sau đó tât cả đều chịu thua trước bài toán hóc búa này. Các bạn hãy giúp các bạn học viên giải quyết bài toán của Tiến sĩ Hùng nhé!!!! Bài toán như sau: “Cho dãy số \(A\) gồm \(N\) phần tử \(0\) hoặc \(1\). Tìm đoạn con liên tiếp dài nhất mà trong đó có số lượng số \(0\) và số lượng số \(1\) là như nhau”.

Input

• Dòng đầu tiên chứa \(1\) số nguyên dương \(N\).
• Dòng thứ hai gồm \(N\) số nguyên dương \(A_{1},A_{2},...,A_{N}\).

Output

• Một dòng ghi một số nguyên duy nhất là kết quả của bài toán.

Constraints

• \(1 \leq n \leq 10^{5}\)
• \(0 \leq A_{i} \leq 1\)

Scoring

• Subtask \(1\) (\(60\%\) số điểm): \(N \leq 10^{3}\).
• Subtask \(2\) (\(40\%\) số điểm): Không có ràng buộc gì thêm.

Example

5
1 1 0 0 1 

4

10
1 0 0 1 1 1 0 1 1 0 

6

4
1 1 1 1 

0

Cho một mảng gồm \(n\) số nguyên dương, nhiệm vụ của bạn là đếm số lượng đoạn con có tổng \(x\).

Input

• Dòng đầu vào đầu tiên có hai số nguyên \(n\) và \(x\): kích thước của mảng và tổng \(x\)
• Dòng tiếp theo có \(n\) số nguyên \(a_1, a_2, \ldots, a_n\): nội dung của mảng
• Các ràng buộc:
  • \(1 \leq n \leq 2\cdot 10^5\)
  • \(1 \leq x, a_i \leq 10^9\)

Output

• In một số nguyên: số lượng đoạn con được yêu cầu

Example

5 7
2 4 1 2 7

3

Bạn được cho thời gian đến và rời đi của \(n\) khách hàng trong một nhà hàng.

Số lượng khách hàng tối đa trong nhà hàng bất cứ lúc nào là bao nhiêu?

Input

• Dòng đầu vào đầu tiên có một số nguyên \(n\): số lượng khách hàng.
• Sau này, có \(n\) dòng mô tả khách hàng. Mỗi dòng có hai số nguyên \(a\) và \(b\): thời gian đến và rời của khách hàng.
• Bạn có thể giả định rằng tất cả thời gian đến và đi là khác nhau.

Constraints

• \(1 \leq n \leq 2 \cdot 10^5\)
• \(1 \leq a < b \leq 10^9\)

Output

• In một số nguyên: số lượng khách hàng tối đa.

Example

3
5 8
2 4
3 9

2

Bạn được một mảng \(A\) gồm \(N\) số nguyên dương.

Bạn sẽ chọn một số phần tử từ mảng \(A\) sao cho giá trị trung bình của các phần tử đã chọn nhỏ hơn \(K\).

Nhiệm vụ của bạn là xác định xem có thể chọn nhiều nhất bao nhiêu phần tử với \(K\) cho trước.

Input

• Dòng đâu tiên chứa số nguyên dương \(N\) \((N \leq 5*10^5)\).
• Dòng 2 chứa \(N\) số nguyên dương \(A_i\) \((A_i \leq 10^9)\).
• Dòng thứ 3 chứa số nguyên \(Q\) \((Q \leq 5\times 10^5)\) - là số câu hỏi.
• \(Q\) dòng tiếp theo, mỗi dòng chứa \(1\) giá tri \(K\) \((K \leq 10^9)\).

Output

• Gồm \(Q\) dòng, mỗi dòng chứa câu trả lời cho mỗi câu hỏi.

Example

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

0
2
4
5
5

Hiếu rất yêu thích số nguyên tố, đồng thời cùng rất yêu thích số \(5\). Hiếu luôn coi các số nguyên tố có tổng các chừ số chia hết cho \(5\) là số đặc biệt. Lần này, thầy giáo đưa cho Hiếu \(2\) số nguyên dương \(L, R\). Hiếu muốn biết trong đoạn \([L, R]\) có bao nhiêu số đặc biệt nên nhờ các bạn trả lời giúp.

Input

• Dòng đầu tiên chứa số nguyên dương \(T\) \((1 \leq T \leq 100)\) là số lượng thử nghiệm.
• \(T\) dòng tiếp theo, mỗi dòng chứa hai số nguyên dương \(L\) và \(R\) \((0 < L \leq R \leq 3 \times 10^{6})\) theo thứ tự, phân tách nhau bởi dấu cách.

Output

• Ghi ra \(T\) dòng, dòng thứ \(i\) ghi một số là số lượng số đặc biệt trong đoạn \([L,R]\) thứ \(i\) tương ứng theo thứ tự trong đầu vào.

Example

2
1 10
4 20 

1
2

Có một dãy các số nguyên \(a_1,a_2,...,a_n\). Ta chia dãy số này thành 2 dãy con như sau:

• Dãy con thứ nhất gồm \(k\) số đầu tiên trong dãy đã cho và tổng các phần tử của dãy con này là \(T_1\).
• Dãy con thứ hai gồm các số còn lại của dãy số đã cho và tổng các phần tử của dãy con này là \(T_2\).

Yêu cầu: Tìm số nguyên dương \(k\) là độ dài của dãy con thứ nhất sao cho \(|T_1−T_2|\) nhỏ nhất.

Chú ý: Nếu có hơn một số \(k\) thỏa mãn thì ghi ra số \(k\) nhỏ nhất.

Input

• Dòng đầu tiên ghi một số nguyên dương \(n\) \((n \leq 1000000)\)
• Dòng thứ hai ghi \(n\) số nguyên \(a_1,a_2,...,a_n\) với \(|ai| \leq 10\) \((1 \leq i \leq n)\), mỗi số cách nhau một dấu cách.

Output

• Ghi ra một số nguyên dương \(k\) thỏa mãn yêu cầu của đề bài.

Example

6
4 7 1 1 4 6 

2

Ký hiệu \(D(n)\) là số lượng ước số của số tự nhiên \(n\), ví dụ: \(D(10)=4\) và \(D(12)=6\). Với \(L\) và \(R\) cho trước \((L\leq R)\), hãy tính tổng \(D(L)+D(L+1)+...+D(R-1)+D(R)\).

Input

• Dòng đầu chứa số nguyên dương \(T\leq 10^6\) là số lượng câu hỏi.

• \(T\) dòng sau, mỗi dòng chứa hai số nguyên dương \(L\) và \(R\) thể hiện một câu hỏi \(\left(1\leq L\leq R\leq 10^6\right)\).

Output

• Gồm \(T\) dòng, mỗi dòng chứa một số nguyên dương là câu trả lời cho câu hỏi tương ứng.

Example

2
1 12
4 5

35
5