Hướng dẫn giải của [VTT Q4 Contest 01] Bài 2: Đếm số [CNTNUM]
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
Với mỗi vị trí ~k~ cần biết có bao nhiêu phần tử bằng ~a_k~ ở bên trái và bên phải. Ta chỉ cần biết thứ hạng của ~k~ trong nhóm các vị trí cùng giá trị và kích thước nhóm.
Sub 1: Vét cạn — ~O(n \cdot q)~, dùng khi ~n, q \le 1000~
Mỗi truy vấn duyệt cả phần bên trái và bên phải của ~k~ để đếm. Nếu chỉ nộp sub này: đúng 10/18 test.
Sub 2: Mảng đếm theo giá trị — ~O(n + q)~, dùng khi ~a_i \le 10^6~
Duyệt dãy từ trái sang phải, giữ mảng cntv[v] là số lần đã gặp giá trị ~v~: ngay trước khi cộng, cntv[a_i] chính là số phần tử bằng nhau ở bên trái. Sau khi duyệt hết, cntv là tổng số lần xuất hiện, nên số phần tử bên phải bằng tổng trừ bên trái trừ 1. Nếu chỉ nộp sub này: đúng 15/18 test (3 test còn lại có ~a_i > 10^6~ nên chạy lỗi).
Sub 3: Sắp xếp theo (giá trị, vị trí) — ~O(n \log n)~
Sắp xếp các cặp (giá trị, vị trí); trong mỗi nhóm giá trị bằng nhau các vị trí đã tăng dần, nên chỉ số trong nhóm là số phần tử bên trái, kích thước nhóm giúp suy ra bên phải. Cách này không phụ thuộc cỡ giá trị. Với ~10^6~ truy vấn nên dùng đọc/ghi nhanh. Nếu chỉ nộp sub này: đúng 18/18 test.
Chương trình hoàn chỉnh
main đọc dữ liệu rồi chọn: nhỏ thì sub1, ~a_i \le 10^6~ thì sub2, còn lạ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;
// Ghi kết quả nhanh: gom vào bộ đệm rồi in một lần
static char obuf[1 << 24];
int opos = 0;
void writePair(int x, int y) {
char t[12]; int l;
l = 0; do { t[l++] = '0' + x % 10; x /= 10; } while (x);
while (l) obuf[opos++] = t[--l];
obuf[opos++] = ' ';
l = 0; do { t[l++] = '0' + y % 10; y /= 10; } while (y);
while (l) obuf[opos++] = t[--l];
obuf[opos++] = '\n';
}
int n, q;
int a[1000005], k[1000005];
int before[1000005]; // số vị trí x < i có a[x] = a[i]
int cntv[1000005]; // dùng cho sub2
int mx = 0;
// Sub 1: với mỗi truy vấn duyệt cả dãy — O(n*q)
void sub1() {
for (int t = 1; t <= q; t++) {
int p = k[t], l = 0, r = 0;
for (int i = 1; i < p; i++) if (a[i] == a[p]) l++;
for (int i = p + 1; i <= n; i++) if (a[i] == a[p]) r++;
writePair(l, r);
}
}
// Sub 2: a_i <= 10^6 nên dùng mảng đếm theo giá trị — O(n+q)
void sub2() {
for (int i = 1; i <= n; i++) { before[i] = cntv[a[i]]; cntv[a[i]]++; }
for (int t = 1; t <= q; t++) {
int p = k[t];
writePair(before[p], cntv[a[p]] - before[p] - 1);
}
}
// Sub 3: sắp xếp (giá trị, vị trí), mỗi nhóm bằng nhau đánh thứ hạng — O(n log n)
void sub3() {
vector<pair<int,int>> v(n);
for (int i = 0; i < n; i++) v[i] = {a[i + 1], i + 1};
sort(v.begin(), v.end());
vector<int> tot(n + 1, 0);
for (int i = 0, j; i < n; i = j) {
j = i;
while (j < n && v[j].first == v[i].first) j++;
for (int t = i; t < j; t++) { before[v[t].second] = t - i; tot[v[t].second] = j - i; }
}
for (int t = 1; t <= q; t++) {
int p = k[t];
writePair(before[p], tot[p] - before[p] - 1);
}
}
// Đọc số nguyên nhanh bằng fread (dữ liệu vào lên tới ~2 triệu số)
static char buf[1 << 25];
int readInt() {
static char *p = buf;
while (*p && (*p < '0' || *p > '9')) p++;
int x = 0;
while (*p >= '0' && *p <= '9') x = x * 10 + (*p++ - '0');
return x;
}
int main() {
freopen("CNTNUM.INP", "r", stdin);
freopen("CNTNUM.OUT", "w", stdout);
fread(buf, 1, sizeof(buf) - 1, stdin);
n = readInt(); q = readInt();
for (int i = 1; i <= n; i++) { a[i] = readInt(); mx = max(mx, a[i]); }
for (int t = 1; t <= q; t++) k[t] = readInt();
ios::sync_with_stdio(false); cin.tie(nullptr);
if (n <= 1000 && q <= 1000) sub1();
else if (mx <= 1000000) sub2();
else sub3();
fwrite(obuf, 1, opos, stdout);
}
Bình luận