Hướng dẫn giải của Duyên hải Bắc Bộ 2026 - Dãy số
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Tác giả:
Subtask 1: ~N = 3~
Nhận thấy, tồn tại duy nhất một bộ là (~a_1, a_2, a_3~). Do đó, ta sẽ chỉ cần kiểm tra:
- Nếu ~a_1 \leq a_2 \geq a_3~ thì ta in ra ~1~.
- Với những trường hợp ngược lại thì ta in ra ~0~.
ĐPT: ~O~(~1~)
Subtask 2: ~N \leq 300~
Ở subtask này, ta sẽ duyệt bộ ba (~i, j, k~) với điều kiện đúng như những gì đề bài bảo.
ĐPT: ~O~ (~N^3~)
Subtask 3: ~N \leq 3000~
Ý tưởng: Ta sẽ chọn phần tử ~j~ ở giữa, rồi đếm số lượng ~i < j~ và số lượng ~k > j~ sao cho:
- ~a_i \leq a_j \geq a_k~ hoặc
- ~a_i \geq a_j \leq a_k~
Gọi:
- ~L_l~ là số phần tử bên trái ~\leq a_j~
- ~L_g~ là số phần tử bên trái ~\geq a_j~
- ~R_l~ là số phần tử bên phải ~\leq a_j~
- ~R_g~ là số phần tử bên phải ~\geq a_j~
Khi này, số bộ thỏa mãn:
- ~a_i \leq a_j \geq a_k~ sẽ là ~L_l \times R_l~
- ~a_i \geq a_j \leq a_k~ sẽ là ~L_g \times R_g~
Tuy nhiên, với ~i = j = k~, các bộ có thể bị đếm trùng, do đó sau khi cộng hai trường hợp thỏa mãn vào, ta sẽ trừ khi đi số bộ ~a_i = a_j = a_k~
ĐPT: ~O~ (~N^2~).
ans = 0
for j in range(n):
L_l = L_g = L_e = 0
for i in range(j):
if a[i] <= a[j]: L_l += 1
if a[i] >= a[j]: L_g += 1
if a[i] == a[j]: L_e += 1
R_l = R_g = R_e = 0
for k in range(j+1, n):
if a[k] <= a[j]: R_l += 1
if a[k] >= a[j]: R_g += 1
if a[k] == a[j]: R_e += 1
ans += L_l * R_l + L_g * R_g - L_e * R_e
print(ans)
Subtask 4: ~N \leq 3 \times 10^5~
Dựa từ ý tưởng Subtask 3, ta nhận ra hoàn toàn có thể tối ưu bước đếm bằng cách sử dụng Fenwick Tree (BIT).
ĐPT: ~O~ (~N~ ~log~ ~N~)
import sys
n = int(sys.stdin.readline())
a = list(map(int, sys.stdin.readline().split()))
b = sorted(set(a))
m = len(b)
d = {b[i]: i + 1 for i in range(m)}
t = [0] * (m + 2)
id = [0] * n
for i in range(n):
x = d[a[i]]
id[i] = x
t[x] += 1
p = [0] * (m + 2)
for i in range(1, m + 1):
p[i] = p[i - 1] + t[i]
bit = [0] * (m + 2)
def upd(i):
while i <= m:
bit[i] += 1
i += i & -i
def get(i):
s = 0
while i > 0:
s += bit[i]
i -= i & -i
return s
ans = 0
seen = 0
for i in range(n):
x = id[i]
# left
ll = get(x)
lt = get(x - 1)
eq = ll - lt
lg = seen - lt
# total
tl = p[x]
tg = n - p[x - 1]
# right
rl = tl - ll - 1
rg = tg - lg - 1
re = t[x] - eq - 1
ans += ll * rl + lg * rg - eq * re
upd(x)
seen += 1
print(ans)
Bình luận