Hướng dẫn giải của Cặp vé trúng thưởng
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.
Hướng dẫn giải
Cặp (i, j) trúng thưởng khi hai mã ci, cj đúng là min và max của đoạn ci..cj. Nói cách khác, mọi phần tử trong đoạn nằm trong đoạn [min(ci, cj), max(ci, cj)].
Sub 1: Vét cạn theo đoạn — ~O(n^3)~, dùng khi ~n \le 200~
Với mọi cặp (i, j), i < j, duyệt cả đoạn để kiểm tra điều kiện. Nếu chỉ nộp sub này: đúng 16/20 test (4 test có n lớn chạy quá giờ).
Sub 2: Mở rộng đoạn — ~O(n^2)~, dùng khi ~n \le 2000~
Với mỗi i cố định, mở rộng j sang phải và giữ min, max của đoạn [i..j]. Cặp (i, j) hợp lệ khi min đoạn bằng min(ci, cj) và max đoạn bằng max(ci, cj), kiểm tra được trong O(1). Nếu chỉ nộp sub này: đúng 16/20 test (4 test có n lớn chạy quá giờ).
Sub 3 (đầy đủ): Đếm bằng ngăn xếp và cây Fenwick — ~O(n \log n)~
Đếm riêng các cặp ci \le cj, rồi đếm các cặp ci \ge cj bằng cách đổi dấu dãy. Trường hợp ci \le cj:
- Với mỗi i, gọi nxt(i) là vị trí đầu tiên sau i có giá trị nhỏ hơn ci. Điều kiện j < nxt(i) đảm bảo mọi phần tử trong (i, j] đều \ge ci.
- Gọi pg(j) là vị trí cuối cùng trước j có giá trị lớn hơn cj. Điều kiện pg(j) < i đảm bảo không có phần tử nào lớn hơn cj trong đoạn [i, j).
- Duyệt j tăng dần, dùng cây Fenwick đánh dấu các i đang hợp lệ (i < j, nxt(i) > j). Số cặp của j là số i đang hợp lệ trong khoảng (pg(j), j).
Các cặp có ci = cj được đếm hai lần, nên trừ đi: mỗi đoạn bằng nhau liên tiếp có độ dài L thì có L(L-1)/2 cặp như vậy.
Bẫy: số cặp có thể tới khoảng 2 \cdot 10^{10}, dùng long long.
Nếu chỉ nộp sub này: đúng 20/20 test.
Chương trình hoàn chỉnh
Hàm main đọc n và dãy c. Nếu n \le 200 gọi sub1; nếu n \le 2000 gọi sub2; còn lại gọi sub3. Khi đi thi nên viết như vậy: sub sau có sai hoặc chưa kịp làm thì vẫn ăn điểm sub trước.
#include <bits/stdc++.h>
using namespace std;
int n;
vector<long long> c; // c[1..n]
// Cap (i, j) trung thuong <=> moi phan tu c_i..c_j nam trong doan [lo, hi],
// voi lo = min(c_i, c_j), hi = max(c_i, c_j). Tuc la hai dau doan la min va max cua doan.
bool valid(int i, int j) {
long long lo = min(c[i], c[j]), hi = max(c[i], c[j]);
for (int k = i; k <= j; k++)
if (c[k] < lo || c[k] > hi) return false;
return true;
}
// Sub 1: vet can O(n^3) - thu moi cap (i, j), kiem tra ca doan. Dung khi n <= 200.
void sub1() {
long long cnt = 0;
for (int i = 1; i <= n; i++)
for (int j = i + 1; j <= n; j++)
if (valid(i, j)) cnt++;
cout << cnt << "\n";
}
// Sub 2: O(n^2) - voi moi i, mo rong j, giu min va max cua doan [i..j] de kiem tra O(1).
void sub2() {
long long cnt = 0;
for (int i = 1; i <= n; i++) {
long long mn = c[i], mx = c[i];
for (int j = i + 1; j <= n; j++) {
mn = min(mn, c[j]);
mx = max(mx, c[j]);
if (mn == min(c[i], c[j]) && mx == max(c[i], c[j])) cnt++;
}
}
cout << cnt << "\n";
}
// Dem cac cap (i < j) voi c_i <= c_j va doan [i..j] nam trong [c_i, c_j]. O(n log n).
// Ky thuat: voi cap nhu vay, phan tu j phai la "moc max" tinh tu i (khong co phan tu lon hon
// truoc j trong doan) va j nam truoc phan tu nho hon c_i dau tien sau i.
long long countUp(const vector<long long> &v) {
// nxt[i] = chi so dau tien k > i co v_k < v_i (n+1 neu khong co)
// pg[j] = chi so cuoi cung k < j co v_k > v_j (0 neu khong co)
vector<int> nxt(n + 2, n + 1), pg(n + 2, 0);
vector<int> st;
for (int i = n; i >= 1; i--) {
while (!st.empty() && v[st.back()] >= v[i]) st.pop_back();
nxt[i] = st.empty() ? n + 1 : st.back();
st.push_back(i);
}
st.clear();
for (int j = 1; j <= n; j++) {
while (!st.empty() && v[st.back()] <= v[j]) st.pop_back();
pg[j] = st.empty() ? 0 : st.back();
st.push_back(j);
}
// bucket[k]: cac i co nxt[i] = k (i se khong con hop le khi j >= k)
vector<vector<int>> bucket(n + 2);
for (int i = 1; i <= n; i++)
if (nxt[i] <= n) bucket[nxt[i]].push_back(i);
// Fenwick tree dem cac i dang hop le
vector<int> bit(n + 1, 0);
auto add = [&](int p, int d) {
for (; p <= n; p += p & -p) bit[p] += d;
};
auto sum = [&](int p) {
int s = 0;
for (; p > 0; p -= p & -p) s += bit[p];
return s;
};
long long res = 0;
for (int j = 1; j <= n; j++) {
for (int i : bucket[j]) add(i, -1); // i bi loai vi gap phan tu nho hon truoc j
// i hop le: pg[j] < i < j
res += sum(j - 1) - sum(pg[j]);
add(j, +1); // j tro thanh i hop le cho cac j sau
}
return res;
}
// Sub 3: day du O(n log n). Cap c_i <= c_j dem bang countUp(c), cap c_i >= c_j dem bang countUp(-c).
// Cac cap c_i = c_j duoc dem ca hai lan nen tru di: moi doan con bang nhau dai L co L(L-1)/2 cap.
void sub3() {
long long up = countUp(c);
vector<long long> neg(n + 1);
for (int i = 1; i <= n; i++) neg[i] = -c[i];
long long down = countUp(neg);
long long eq = 0;
for (int i = 1; i <= n;) {
int j = i;
while (j + 1 <= n && c[j + 1] == c[i]) j++;
long long L = j - i + 1;
eq += L * (L - 1) / 2;
i = j + 1;
}
cout << up + down - eq << "\n";
}
int main() {
freopen("TrungThuong.INP", "r", stdin);
freopen("TrungThuong.OUT", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
c.assign(n + 1, 0);
for (int i = 1; i <= n; i++) cin >> c[i];
if (n <= 200) sub1(); // n nho: thu moi cap
else if (n <= 2000) sub2(); // n vua: O(n^2)
else sub3();
return 0;
}
Bình luận