Cho một xâu s chỉ gồm các kí tự '. Và '#', có độ dài n (2 <= n <= 10^5). Cho m truy vẫn dạng l[i], r(i] (1 <= l[i] < r[i] <= n). Bạn cần tính kết quả của truy vấn là số lượng các giá trị k (l[i] <= k < r[i]) thỏa mãn s[k] = s[k + 1].

Định dạng đầu vào:

Dòng đầu tiên là xâu s.

Dòng thứ 2 là số nguyên m - số truy vấn.

m dòng tiếp theo, dòng thứ i chứa 2 số nguyên l[i] và r[i].

Định dạng đầu ra: Gồm m dòng là kết quả của m truy vấn.

Input 01:

......
4
3 4
2 3
1 6
2 6

Output 01:

1
1
5
4

Input 02:

#..###
5
1 3
5 6
1 5
3 6
3 4

Output 02:

1
1
2
2
0

Cho một dãy số nguyên dương a, đếm số lượng dãy con liên tiếp có tổng chia hết cho d

Hai dãy con được gọi là khác nhau nếu ít nhất một trong hai điểm đầu hoặc điểm cuối hay dãy con đó trong dãy gốc là khác nhau.

Ví dụ:

• Với d = 4, dãy (2, 1, 2, 1, 4, 1) có 4 dãy con thỏa mãn là (1, 2, 1), (1, 2, 1, 4), (4), (2, 1, 4, 1)

• Với d = 2, dãy (1, 1, 1, 1) có 4 dãy con thỏa mãn

Đầu vào:

Dòng đầu tiên là số t - số lượng test (t ≤ 100)

t nhóm dòng tiếp theo, mỗi nhóm dòng tương ứng với một yêu cầu:

• Dòng đầu là hai số nguyên dương d và n (d ≤ 10^6, n ≤ 5 * 10^4)

• Dòng thứ hai chứa n số nguyên dương biểu diễn dãy số

Đầu ra:

t dòng là kết quả của các test theo thứ tự

Input:

1
2 4
1 1 1 1

Output:

4

Giải thích: Các cặp (i, j) sau thỏả mãn: (1, 2), (2, 3), (3, 4), (1, 4)

Nhà máy dầu ~A~ vừa mời một kỹ sư ~E~ đến lắp đặt một dàn máy bơm dầu tự động hiện đại bậc nhất Đông Nam Á. Trên băng chuyền có ~n~ thùng dầu rỗng, được đánh số từ ~1~ đến ~n~. Mỗi giây, một đầu bơm sẽ thực hiện bơm dầu vào một đoạn liên tiếp các thùng, từ thùng dầu thứ i đến thùng dầu thứ j ~(1 ≤ i ≤ j ≤ n)~, mỗi thùng trong đoạn này sẽ được bơm thêm ~k~ lít dầu.

Sau ~m~ giây bơm, hãy xác định lượng dầu có trong từng thùng.

Dữ liệu vào:

Dòng đầu tiên chứa một số nguyên t — số lượng test case.

Với mỗi test case:

Dòng đầu tiên chứa hai số nguyên n và m — số thùng dầu và số giây bơm.

Tiếp theo là m dòng, mỗi dòng chứa ba số nguyên i, j, k, nghĩa là trong giây này, máy bơm sẽ bơm thêm k lít dầu vào tất cả các thùng từ i đến j.

Dữ liệu ra:

Với mỗi test case, in ra một dòng gồm ~n~ số nguyên, trong đó số thứ ~x~ là lượng dầu có trong thùng dầu thứ ~x~ sau khi thực hiện xong tất cả các lần bơm.

Ví dụ :

Input:

1
3 1
1 3 5

Output:

5 5 5

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, mỗi truy vấn yêu cầu tính tổng các giá trị trong đoạn từ chỉ số ~a~ đến ~b~.

Đầu vào:

Dòng đầu tiên chứa hai số nguyên ~n~ và ~q~: số lượng phần tử trong mảng và số lượng truy vấn.

Dòng thứ hai chứa ~n~ số nguyên ~x₁, x₂, ..., xₙ~: là các giá trị trong mảng.

Mỗi dòng trong số ~q~ dòng tiếp theo chứa hai số nguyên ~a~ và ~b~: yêu cầu tính tổng các phần tử từ vị trí a đến b (tính cả hai đầu).

Đầu ra:

Với mỗi truy vấn, in ra một dòng chứa tổng các phần tử từ vị trí a đến b.

Ràng buộc:

~1 \le n,q \le 2 \cdot 10^5~

~1 \le x_i \le 10^9~

~1 \le a \le b \le n~

Ví dụ :

Input:

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

Output:

11
2
24
4

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. 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 xâu S gồm các chữ cái in thường, tìm xâu con liên tiếp ngắn nhất chứa đầy đủ các ký tự của S và in ra. Ví dụ xâu S = "abcaaaabcda" thì xâu con "bcda" là xâu con nhỏ nhất chứa đầy đủ các ký tự của S.

Ràng buộc: ~0 < len(S) \leq 10^6~

Input:

abcaaadabcda

Output:

bcda

Giải thích: Xâu con ngắn nhất chứa đầy đủ các ký tự của S là xâu bcda

Cho mảng A gồm N số nguyên và số nguyên S, nhiệm vụ của bạn là đếm xem có bao nhiêu mảng con các phần tử liên tiếp trong mảng mà tổng không vượt quá S.

Định dạng đầu vào:

Dòng đầu tiền là N và S

Dòng thứ 2 là N số trong máng A[]

Ràng buộc:

1<=N<=10^6

1<=A(i]<=10^6

1<=S<=10^9

Định dạng đầu ra: In ra số lượng mảng con thỏa mãn

Input:

8 5
3 1 4 3 5 8 3 1

Output:

10

Giải thích: Có 10 mảng con thỏa mãn là: [3], [3, 1], [1], [1, 4], [4], [3] (ở vị trí index 3), [5], [3] (ở vị trí index 6), [3, 1], [1]

Cho mảng A gồm N số nguyễn và số nguyên S, nhiệm vụ của bạn là đếm xem có bao nhiêu mảng con các phần tử liên tiếp trong mảng mà tổng lớn hơn hoặc bằng S

Định dạng đầu vào:

• Dòng đầu tiền là N và S

• Dòng thứ 2 là N số trong mảng A[]

Ràng buộc:

• 1<=N<=10^6

• 1<=A(i]<=10^6

• 1<=S<=10^9

Định dạng đầu ra: In ra số lượng mảng con thoa mãn

Input:

8 3
3 1 4 3 5 8 3 1

Output:

34

Cho mảng A[] gồm N phần tử đã được sắp xếp và số nguyên dương K, nhiệm vụ của bạn là tìm số lượng phần tử lớn nhất trong mảng sao cho độ chênh lệch giữa 2 phần tử bất kì trong tập hợp bạn chọn ra không vượt quá K.

Định dạng đầu vào: Dòng thứ nhất gồm N và 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; 0<=А[i]<=10^6.

Định dạng đầu ra: In ra đáp án của bài toán

Input:

5 3
1 2 3 3 4

Output:

5

Cho mảng A gồm n số nguyên.

Bạn phải thay đổi ít nhất bao nhiêu số để mảng A chỉ gồm các số nguyên liên tiếp?

Đầu vào:

Dòng đầu tiên gồm số nguyên n.

Dòng thứ hai gồm n số nguyên Ai.

Đầu ra: n ra số lượng số nguyên ít nhất phải thay.

Ràng buộc:

1 <= n <= 10^5

1 <= Ai <= 10^9

Input:

3
4 10 5

Output:

1

Giải thích: thay 10 bằng 6

Cho 2 xâu S và T, tìm xâu con ngắn nhất của S chứa đầy đủ và đúng thứ tự các ký tự trong T.

Ràng buộc: ~1 \leq len(T), len(S) \leq 10^3~

S, T chứa các ký tự in thường

In ra độ dài xâu con nhỏ nhất thỏa mãn, nếu không có xâu nào thỏa mãn in ra NOT FOUND

Input 01:

hoccohocnngnghehnc
hcn

Output 01:

4

Input 02:

hoccohocnngnghehnc
hwn

Output 02:

NOT FOUND