Cho mảng A có N phần tử là các số nguyên đã được sắp xếp theo thứ tự tăng dần. Hãy viết các hàm với độ phức tạp O(logN):

1. Tìm vị trí xuất hiện đầu tiên của phần tử X trong mảng, nếu không có in ra -1

2. Tìm vị trí xuất hiện cuối cùng của phần tử X trong mảng, nếu không có in ra -1

3. Tìm vị trí xuất hiện đầu tiên của phần tử >=X trong mảng, nếu không có in ra -1

4. Tìm vị trí xuất hiện đầu tiên của phần tử >X trong mảng, nếu không có in ra -1

5. Tìm số lần hiện của phần tử X trong mảng sử dụng kết quả trong hàm 1 và 2

Ràng buộc: ~1 \leq N \leq 10^6~; ~0 \leq A[i] \leq 10^6~

Input:

10 1100
10 1000 2172 2921 3400 4185 4639 6096 6244 9102

Output:

-1
-1
2
2
0

Cho mảng a gồm n phăn tử và số nguyên dương k. Đếm số lượng cặp số ai, aj (i != j) có tổng bằng k.

Gợi ý: Sắp xếp mảng tăng dẫn sau đó với mỗi phần tử a[i] trong mảng tìm xem trong đoạn [i + 1, n - 1] có bao nhiêu phần tử có giá trị là k - a[i], bằng cách tìm vị trí đầu tiên và vị trí cuối cùng của phần tử có giá trị là k - a[i] => Số lượng

Định dạng đầu vào: Dòng thứ 1 là số lượng phần tử trong mảng và số nguyên dương k; Dòng thứ 2 là n phần tử trong mảng

Ràng buộc: 2<=п<=10^6; 1<=k<=10^6; 0<=a(i)<=10^6;

Định dạng đầu ra: In ra số lượng cặp số có tổng bằng k

Input:

4 4
2 2 2 2

Output:

6

Cho mảng a gồm n phăn tử và số nguyên dương k. Đếm số lượng cặp số ai, aj (i != j) có tổng nhỏ hơn k.

Định dạng đầu vào: Dòng thứ 1 là số lượng phần tử trong mảng và số nguyên dương k; Dòng thứ 2 là n phần tử trong mảng

Ràng buộc: 2<=п<=10^6; 1<=k<=10^6; 0<=a(i)<=10^6;

Định dạng đầu ra: In ra số lượng cặp số có tổng bằng k

Input:

4 5
2 2 2 2

Output:

6

Cho mảng a gồm n phăn tử và số nguyên dương k. Đếm số lượng cặp số ai, aj (i != j) có tổng lớn hơn k.

Định dạng đầu vào: Dòng thứ 1 là số lượng phần tử trong mảng và số nguyên dương k; Dòng thứ 2 là n phần tử trong mảng

Ràng buộc: 2<=п<=10^6; 1<=k<=10^6; 0<=a(i)<=10^6;

Định dạng đầu ra: In ra số lượng cặp số có tổng bằng k

Input:

4 5
2 3 4 5

Output:

5

Cho một dãy A gồm N số nguyên a1, a2, a3, ..., aN đã được sắp xếp tăng dần. Bạn cần trả lời Q truy vấn sau:

Cho 3 số l, r, x, có bao nhiêu số có giá trị x trong dãy con al, a(l+1), a(l+2), ..., ar?

Đầu vào:

Dòng đầu tiên gồm duy nhất số nguyên N (N <= 10^6) - kích thước mảng.

Dòng thứ hai gồm N số nguyên ai (0 <= ai <= 10^9).

Dòng thứ ba gồm số truy vấn Q (Q <= 10^5) - số truy vấn.

Q dòng tiếp theo mỗi dòng gồm 3 số l,r,x (0 <= l <= r <= n-1).

Đầu ra:

Q dòng cho biết có bao nhiêu số có giá trị x trong dãy con al, a(l+1), a(l+2), ..., ar? ở mỗi truy vấn.

Input:

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

Output:

1
2

Cho một mảng A nguyên gồm N phần tử đã sắp xếp tăng dần, hãy tìm chỉ số của phần tử xuất hiện đầu tiên trong mảng, ví dụ mảng 1, 3, 4, 5, 5, 5, 6, 7. Nếu tìm số 5 thì số 5 xuất hiện đầu tiên sẽ có chỉ số 3, chỉ số này được in ra. Nếu không tìm thấy thì in ra -1

Ràng buộc: ~0 < N \leq 10^6~, ~-10^6 < A[i] \leq 10^6~

Input 01:

8 5
1 3 4 5 5 5 6 7

Output 01:

3

Input 02:

7 -3
-3 -3 -1 4 5 6 7

Output 02:

0

Input 03:

6 10
1 3 4 5 6 7

Output 03:

-1

Cho dãy số tự nhiên gồm N phần tử: 𝑎1, 𝑎2, … an và một số tự nhiên K.

Yêu cầu: Đếm số lượng cặp chỉ số (𝑖, 𝑗) mà 𝑖 < 𝑗 và 𝑎𝑖 + 𝑎𝑗 = 𝐾 trong dãy.

Dữ liệu vào: Đọc dữ liệu vào từ tệp bai3.inp.

• Dòng đầu là hai số nguyên dương 𝑁, 𝐾 (2 ≤ 𝑁 ≤ 3.10^6; 1 ≤ 𝐾 ≤ 10^6).

• Dòng sau là dãy số: 𝑎1, 𝑎2, … 𝑎𝑁 các số đều là số dương và không quá 10^6.

Dữ liệu ra: Ghi kết quả ra tệp bai3.out là số lượng cặp 𝑎𝑖 , 𝑎𝑗 có tổng bằng K.

Input 01:

5 1
1 5 4 1 2

Output 01:

0

Không có cặp 𝑎𝑖 + 𝑎𝑗 = 1

Input 02:

4 6
3 2 3 3

Output 02:

3

Có 3 cặp {𝑎1, 𝑎3}; {𝑎1, 𝑎4}; {𝑎3, 𝑎4} có tổng bằng 6

Cho dãy số tự nhiên gồm N phần tử: 𝑎1, 𝑎2, … 𝑎𝑁 và một số tự nhiên K.

Yêu cầu: Đếm số lượng cặp chỉ số (𝑖, 𝑗) mà 𝑖 < 𝑗 và 𝑎𝑖 + 𝑎𝑗 = 𝐾 trong dãy.

• Dòng đầu là hai số nguyên dương 𝑁, 𝐾 (2 ≤ 𝑁 ≤ 3.10^6; 1 ≤ 𝐾 ≤ 10^6).

• Dòng sau là dãy số: 𝑎1, 𝑎2, … 𝑎𝑁 các số đều không quá 10^6.

Dữ liệu ra: Ghi kết quả ra tệp bai3.out là số lượng cặp 𝑎𝑖 , 𝑎𝑗 có tổng bằng K.

Input 01:

5 1
1 5 4 1 2

Output 01:

0

Không có cặp 𝑎𝑖 + 𝑎𝑗 = 1

Input 02:

4 6
3 2 3 3

Output 02:

3

Có 3 cặp {𝑎1, 𝑎3}; {𝑎1, 𝑎4}; {𝑎3, 𝑎4} có tổng bằng 6

Input 02:

5 6 
3 2 3 3 3

Output 02:

6

Cho mảng A gồm N phần tử và số X. Nhiệm vụ của bạn là tìm cặp phần tử A[i] - A[j] = X.

Nếu tồn tại A[i] - A[j] = X đưa ra 1, ngược lại đưa ra -1.

Input Format: Dòng thứ nhất là cặp số N, X; Dòng tiếp theo là N số A(i] là các phần tử của mảng A.

Ràng buộc: ~1 ≤ N ≤ 10^5~; ~1 ≤ X, A[i] ≤ 10^{5}~.

Input 01:

5 4
1 2 3 4 5

Output 01:

1

Giải thích: Cặp số có hiệu bằng 4 là 5 và 1

Input 02:

5 5
1 2 3 4 5

Output 02:

-1