Tác giả:
Reviewer:
Hiệu đính:
Để hiểu được bài viết, độc giả nên kiến thức về các phần sau:
Chen, DanQi D&C (CDQ D&C) là kĩ thuật tối ưu bằng chia để trị thường được áp dụng trong các bài toán có dạng tương tự bài toán sau:
Cho tập điểm ba chiều . Với mỗi điểm , đếm số điểm sao cho .
Bài toán trên có thể được giải bằng CDQ D&C với độ phức tạp với là số điểm.
Giả sử ta giảm số chiều của bài toán trên xuống còn chiều, lúc này bài toán này có thể giải bằng thuật toán Sweep Line. Cụ thể, ta sắp xếp tập điểm theo chiều đầu tiên, sau đó duyệt tập điểm rồi cập nhật và lấy đáp án bằng một số cấu trúc dữ liệu như Segment Tree, Fenwick Tree.
Khi tăng số chiều của bài toán lên , ta có thể dễ dàng xử lý bằng cách tăng chiều của Segment Tree/Fenwick Tree lên thành chiều để giải trong độ phức tạp . Tuy nhiên, hệ số thời gian chạy của thuật toán này đôi lúc không đủ tốt, kèm theo độ phức tạp không gian lớn. Lúc này ta có thể áp dụng CDQ D&C để giải bài toán cũng trong nhưng có thời gian chạy và độ phức tạp không gian tốt hơn.
Các bước giải bằng CDQ trên tập điểm chiều có dạng như sau:
Khi đã sắp xếp tập theo chiều , việc tính phần đóng góp của đoạn cho đoạn lúc này được đơn giản hóa xuống bài toán gần giống bài toán hai chiều. Để tối ưu thuật toán "Kết hợp", sau khi thực hiện hàm chia để trị trên đoạn , ta cần đảm bảo đoạn được sắp xếp lại theo chiều (xem phần dưới).
Đầu tiên, ta sắp xếp theo chiều . Với mọi vị trí , ta có . Khi thực hiện dnc(l, r), ta gọi bài toán con dnc(l, m) và dnc(m + 1, r).
Khi này, đoạn và đã được sắp xếp theo . Do thao tác sắp xếp đoạn và được thực hiện độc lập, nên mỗi phần tử trong đoạn vẫn có chiều lớn hơn hoặc bằng mọi phần tử trong đoạn .
Trong bài viết, các chiều , , chỉ mang tính tượng trưng. Nói cách khác, khi làm các bài sử dụng CDQ, ta thường sắp xếp các chiều có khoảng lớn để ưu tiên chiều có kích thước bé nhất cho cấu trúc dữ liệu.
Để tính được phần đóng góp của đoạn cho đoạn , ta sẽ duyệt qua cả đoạn tương tự Merge Sort theo chiều kết hợp cùng cấu trúc dữ liệu (ví dụ như Segment Tree). Cụ thể, ta so sánh hai phần tử đứng đầu hai đoạn và ưu tiên duyệt phần tử có chiều nhỏ hơn.
Khi duyệt qua phần tử thuộc , ta sẽ tiến hành cập nhật lên cấu trúc dữ liệu. Khi duyệt qua phần tử thuộc đoạn , ta sẽ cập nhật đáp án cho phần tử này dựa theo cấu trúc dữ liệu.
Do ta chỉ cần tính đóng góp của đoạn cho đoạn và chiều đã được sort từ ban đầu, chiều đã được sort qua việc thực hiện hàm dnc() trên đoạn, khi này từ chiều ta đã có thể rút gọn còn chiều .
Trước hết, ta khai báo kiểu dữ liệu:
struct point {
int x, y, z, i;
// Ta lưu lại i là vị trí cập nhật các điểm
};
struct cmp {
bool operator() (point a, point b) {
if (a.x != b.x) return a.x > b.x;
if (a.y != b.y) return a.y < b.y;
if (a.z != b.z) return a.z < b.z;
return a.i < b.i;
}
};
Hàm so sánh trên vô cùng quan trọng. Độc giả nên chú ý về thứ tự sắp xếp của các phần tử cần dùng trong bài, đặc biệt trường hợp hai phần tử có thứ tự bằng nhau. Cụ thể
Việc cài đặt hàm so sánh không đúng có thể tạo ra lỗi rất khó debug.
Hàm dnc(l,r) thường có dạng như sau (cài đặt ngắn hơn ở phía dưới):
vector<point> v;
void dnc(int l, int r) {
if (l == r) return;
int m = (l + r) >> 1;
int lptr = l, rptr = m + 1;
dnc(l, m); dnc(m + 1, r); // Thực hiện trên 2 khoảng
vector<point> tmp; // Mảng lưu lại đoạn [l..r] sau khi sort theo y
vector<int> revert; // Mảng lưu lại những vị trí đã cập nhật để đảo ngược sau khi kết thúc phần Kết hợp
while (lptr <= m && rptr <= r) {
if (v[lptr].y > v[rptr].y) {
// Cập nhật ctdl
revert.push_back(v[lptr].z);
tmp.push_back(v[lptr++]);
}
else {
// Truy vấn ctdl
tmp.push_back(v[rptr++]);
}
}
while (lptr <= m) {
tmp.push_back(v[lptr++]);
}
while (rptr <= r) {
// Truy vấn ctdl
tmp.push_back(v[rptr++]);
}
// Cập nhật lại phần vừa sort
for (int i = l; i <= r; i++) v[i] = tmp[i-l];
// Đảo ngược phần đã cập nhật để reset lại ctdl
for (int i : revert) {
// ...
}
}
Để ngắn gọn hơn ta có thể viết hàm dnc(l,r) như sau:
void dnc(int l, int r) {
if (l == r) return;
int m = (l + r) >> 1;
int lptr = l, rptr = m + 1;
dnc(l, m); dnc(m + 1, r); // Thực hiện trên 2 khoảng
vector<point> tmp; // Mảng lưu lại đoạn [l..r] sau khi sort theo y
vector<int> revert; // Mảng lưu lại những vị trí đã cập nhật để đảo ngược sau khi kết thúc phần Kết hợp
for (int rptr = m+1; rptr <= r; rptr++) {
for (; lptr <= m && v[lptr].y <= a[rptr].y; lptr++) {
// Cập nhật ctdl
revert.push_back(v[lptr].z);
tmp.push_back(v[lptr]);
}
// Truy vấn ctdl
tmp.push_back(v[rptr]);
}
// lptr có thể khác m, nhưng ta không cần cập nhật nữa vì không còn truy vấn
for (; lptr <= m; lptr++) {
tmp.push_back(v[lptr]); // Không cần cập nhật ctdl do không còn truy vấn
}
// Đảo ngược phần đã cập nhật để reset lại ctdl
for (int i : revert) {
// ...
}
}
Cho điểm có dạng . Đếm số điểm mà tồn tại điểm sao cho .
Giới hạn: .
Bài toán này ngược lại với ví dụ, thay vì đếm số điểm ở bên trong thì ta sẽ đếm số điểm ở phía ngoài của điểm. Ta sẽ giải như sau:
struct point { int x, y, z, i; };
struct cmp {
bool operator() (point a, point b) {
return a.x > b.x;
// Ở bài toán này, ta có thể thấy do phép so sánh là <,
// việc thực hiện sort cho y, z và i không quan trọng
// nếu ta đã sort đúng cho x.
}
};
for (int i = 1; i <= n; i++) {
v.push_back({x[i], y[i], z[i], i});
sortX.push_back(x[i]); sortY.push_back(y[i]); sortZ.push_back(z[i]);
}
sort(sortX.begin(),sortX.end());
sort(sortY.begin(),sortY.end());
sort(sortZ.begin(),sortZ.end());
for (point& u : v) {
u.x = lower_bound(sortX.begin(),sortX.end(),u.x) - sortX.begin() + 1;
u.y = lower_bound(sortY.begin(),sortY.end(),u.y) - sortY.begin() + 1;
u.z = lower_bound(sortZ.begin(),sortZ.end(),u.z) - sortZ.begin() + 1;
}
dnc(), ta sẽ thực hiện như sau:const maxN = 1e5 + 5;
// TEMPLATE Fenwick Tree
// luu y day la fenwick tree nguoc, ham get se lay tong tu (u -> maxn)
long long bit[maxN];
void upd(ll u, ll v) {
while (u) {
bit[u] += v;
u -= (u&(-u));
}
}
ll get(ll u) {
ll sum = 0;
while (u < mxn) {
sum += bit[u];
u += (u&(-u));
}
return sum;
}
bool ans[maxN];
vector<point> v;
void dnc(int l, int r) {
if (l == r) return;
int m = (l + r) >> 1;
int lptr = l, rptr = m + 1;
dnc(l, m); dnc(m + 1, r);
vector<point> tmp;
vector<int> revert;
while (lptr <= m && rptr <= r) {
if (v[lptr].y > v[rptr].y) {
upd(v[lptr].z,1); // Cập nhật lên Fenwick Tree
revert.push_back(v[lptr].z); // Lưu lại vị trí vừa cập nhật để đảo ngược
tmp.push_back(v[lptr++]); // Vị trí mới sau khi Merge Sort
}
else {
ans[v[rptr].i] |= get(v[rptr].z + 1); // Kiểm tra xem có phần tử nào thỏa mãn không
tmp.push_back(v[rptr++]);
}
}
while (lptr <= m) {
tmp.push_back(v[lptr++]);
}
while (rptr <= r) {
ans[v[rptr].i] |= get(v[rptr].z + 1);
tmp.push_back(v[rptr++]);
}
for (int i = l; i <= r; i++) v[i] = tmp[i-l];
for (int i : revert) upd(i,-1);
}
ans[] có giá trị bằng là kết thúc bài toán.Có học sinh, học sinh thứ đạt điểm môn Toán học, điểm môn Tin học. Giáo sư và sẽ đánh giá xem một học sinh qua hay trượt môn.
Với giáo sư , giáo sư yêu cầu điểm môn Toán, điểm môn Tin.
Với giáo sư , giáo sư yêu cầu điểm tổng Toán và Tin.
Một học sinh được đánh giá là đạt khi được cả giáo sư cho qua môn.
Cho truy vấn, mỗi truy vấn cho , yêu cầu tính xem có bao nhiêu học sinh đạt.
Giới hạn: .
Thực tế thì bài toán này không khác bài toán trên quá nhiều, với mỗi học sinh, ta chỉ cần lưu lần lượt là điểm môn Toán, điểm môn Tin, tổng điểm môn.
Bài toán này chia ra làm loại điểm, điểm học sinh và điểm yêu cầu của giáo sư, do đó ta sẽ thêm biến nữa là để biết đâu là điểm của học sinh, đâu là điểm của giáo sư.
Ta sẽ giải bài toán này như sau:
Trước hết, ta khai báo một số kiểu dữ liệu cần thiết:
struct point {long long x, y, z, v, i;};
// v = 1 là điểm của học sinh
// v = 0 là điểm yêu cầu của giáo sư
struct cmp {
bool operator() (point a, point b) {
if (a.x != b.x) return a.x > b.x;
return a.v > b.v;
// Đây là thứ cần lưu ý đã được nói ở phía trên,
// việc ta sort ưu tiên theo v để đảm bảo rằng khi
// xét đến một giáo sư thì ta đã xét hết tất cả những điểm
// của học sinh để tránh sót những điểm thỏa mà chưa được
// xét tới do phép so sánh được sử dụng trong bài là <=
}
};
Do , ta sẽ thực hiện nén số để dễ dàng sử dụng Fenwick Tree hơn:
vector<long long> sortX, sortY, sortZ;
for (int i = 0; i < n; i++) {
int a, b; cin >> a >> b;
v.push_back({a,b,a+b,1,i});
sortX.push_back(a); sortY.push_back(b); sortZ.push_back(a+b);
}
for (int i = n; i < n+mm; i++) {
long long a, b, c; cin >> a >> b >> c;
v.push_back({a,b,c,0,i});
sortX.push_back(a); sortY.push_back(b); sortZ.push_back(c);
}
sort(sortX.begin(),sortX.end());
sort(sortY.begin(),sortY.end());
sort(sortZ.begin(),sortZ.end());
for (point& i : v) {
i.x = lower_bound(sortX.begin(),sortX.end(),i.x)-sortX.begin()+1;
i.y = lower_bound(sortY.begin(),sortY.end(),i.y)-sortY.begin()+1;
i.z = lower_bound(sortZ.begin(),sortZ.end(),i.z)-sortZ.begin()+1;
}
Cuối cùng ta thực hiện CDQ tương tự như bài trên:
// fenwick tree duoc su dung trong bai la fenwick tree nguoc,
// ham get lay tong tu (u->mxn)
vector<point> v;
long long n, mm, ans[mxn];
void cdq(int l, int r) {
if (l+1 == r) return;
int m = (r+l)>>1;
cdq(l,m); cdq(m,r);
int lptr = l, rptr = m;
vector<pair<int, int>> record;
vector<point> tmp;
while (lptr < m && rptr < r) {
if (v[lptr].y >= v[rptr].y) {
bit.upd(v[lptr].z,v[lptr].v);
record.push_back({v[lptr].z,v[lptr].v});
tmp.push_back(v[lptr++]);
}
else {
ans[v[rptr].i] += bit.get(v[rptr].z);
tmp.push_back(v[rptr++]);
}
}
while (lptr < m) tmp.push_back(v[lptr++]);
while (rptr < r) {
ans[v[rptr].i] += bit.get(v[rptr].z);
tmp.push_back(v[rptr++]);
}
for (int i = l; i < r; i++) v[i] = tmp[i-l];
for (pair<int, int> i : record) bit.upd(i.fi,-i.se);
record.clear(); tmp.clear();
}
Độ phức tạp: .
Bài toán đặc biệt ở việc sắp xếp sai thứ tự ưu tiên của các điểm sẽ gây lỗi rất khó debug.
Cho cây đỉnh, các cạnh của cây có trọng số, đếm số đường đi từ đến sao cho độ dài đường đi từ đến , tổng trọng số trên đường đi .
Giới hạn: .
Bài toán này có sử dụng thuật toán Centroid Decomposition, khuyến khích độc giả đọc trước khi tiếp tục bài viết.
Nếu biết về thuật toán Centroid Decomposition, ta dễ dàng nhận thấy rằng chiều mà ta cần xét sẽ lần lượt là độ dài từ đến centroid và tổng trọng số từ đến centroid. Vậy chiều thứ của bài toán này là gì?
Khi xét một centroid (trọng tâm), ta cần đảm bảo rằng các đường đi sẽ đi qua centroid này. Lúc này với mỗi điểm, ta cần xem xem điểm đó có lựa chọn các điểm mà không xuất hiện cùng subtree (cây con) với nó không (root (gốc) là centroid đang xét).
Lúc này, ta thấy chiều còn lại chính là chiều thời gian - thời điểm/thứ tự của root của subtree mà điểm được thêm vào.
Với một số bài toán, việc thêm chiều là thời gian cũng khá dễ gặp. Khi gặp một bài toán mà cảm giác sẽ dùng đến CDQ và cần sắp xếp theo thứ tự nào đó, ta thường sẽ chuyển về bài toán CDQ thông thường với chiều thời gian.
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
const int mxn = 1e5+7;
int n, l, w, l_i[mxn];
long long w_i[mxn];
vector<vector<pair<int,int>>> g(mxn);
int sz[mxn];
bool del[mxn];
// template tìm centroid và kích thước subtree
void dfs_sz(int u, int v) {} // kích thước
int dfs_ctr(int u, int v, int szx) {} // tìm centroid
// điểm và sort dùng trong CDQ
struct point {
int x, y, z, v, i;
point() {x = -mod;}
point(int xx, long long yy, int zz, int vv, int ii) {
x = xx; y = yy; z = zz; v = vv; i = ii;
}
};
struct cmp {
bool operator() (point a, point b) {
if (a.x != b.x) return a.x < b.x;
return a.v > b.v;
}
};
// template BIT / Fenwick Tree
int bit[mxn];
long long ans[2];
void upd(int u, int v) {
while (u < mxn) {
bit[u] += v;
u += (u&(-u));
}
}
int get(int u) {
int sum = 0;
while (u) {
sum += bit[u];
u -= (u&(-u));
}
return sum;
}
// template CDQ
vector<point> v;
void cdq(int l_l, int r) {
if (l_l == r) return;
int m = (r+l_l)>>1; int a = l_l, b = m+1;
cdq(l_l,m); cdq(m+1,r);
vector<point> tmp; vector<pair<int,int>> revert;
while (a <= m && b <= r) {
if (v[a].y <= v[b].y) {
if (v[a].v) {
upd(v[a].z,v[a].v);
revert.push_back({v[a].z,v[a].v});
}
tmp.push_back(v[a++]);
}
else {
if (v[b].i) ans[v[b].i] += get(v[b].z-1);
tmp.push_back(v[b++]);
}
}
while (a <= m) tmp.push_back(v[a++]);
while (b <= r) {
if (v[b].i) ans[v[b].i] += get(v[b].z-1);
tmp.push_back(v[b++]);
}
for (int i = l_l; i <= r; i++) v[i] = tmp[i-l_l];
for (pair<int,int> i : revert) upd(i.fi,-i.se);
}
// hàm dfs để tính độ dài và tổng trọng số từ gốc đến 1 đỉnh
void dfs_l_w(int u, int vv) {
for (pair<int,int> i : g[u]) {
if (i.fi != vv && !del[i.fi]) {
l_i[i.fi] = l_i[u]+1;
w_i[i.fi] = w_i[u]+i.se;
dfs_l_w(i.fi,u);
}
}
}
// hàm thêm 1 subtree khi Centroid Decomposition
void add(int u, int vv, int time) {
if (l_i[u] <= l && w_i[u] <= w) {
ans[1]++; // thêm điểm vào CDQ
v.push_back({l_i[u],w_i[u],time,1,0}); // điểm này để các điểm khác đếm
v.push_back({l-l_i[u],w-w_i[u],time,0,1}); // điểm này dùng để đếm các điểm khác
}
for (pair<int,int> i : g[u]) {
if (i.fi != vv && !del[i.fi]) {
add(i.fi,u,time);
}
}
}
// hàm cập nhật đáp án khi Centroid Decomposition
void upd(int u) {
l_i[u] = w_i[u] = 0;
dfs_l_w(u,u);
v.clear(); v = {point()};
int cnt = 2;
// for qua các subtree có cạnh nối trực tiếp với centroid đang xét
for (pair<int,int> i : g[u]) {
if (!del[i.fi]) {
add(i.fi,u,cnt);
cnt++;
}
}
if (v.size() == 1) return;
sort(v.begin(),v.end(),cmp()); // sort theo 1 chiều để thực hiện CDQ
cdq(1,(int)v.size()-1);
}
// hàm thực hiện Centroid Decomposition
void solve(int u) {
dfs_sz(u,u);
int n_root = dfs_ctr(u,u,sz[u]);
upd(n_root);
del[n_root] = 1;
for (pair<int,int> i : g[n_root]) {
if (!del[i.fi]) solve(i.fi);
}
}
signed main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n >> l >> w;
for (int i = 2; i <= n; i++) {
int a, b;
cin >> a >> b;
g[a].push_back({i,b});
g[i].push_back({a,b});
}
solve(1);
cout << ans[1];
}
Độ phức tạp: .
Ta cần tính dãy sao cho nhưng ta sẽ chỉ biết được và sau khi ta tính được .
Ta có thể viết bài toán này lại thành với hệ số bậc của và sẽ được biết sau khi ta tính xong hệ số bậc của .
Để tính với và ta đã biết giá trị của với , ta cần tính sự đóng góp của cặp thỏa mãn:
Từ đây, ta có thể thấy với mỗi , giá trị sẽ nằm trong khoảng .
Tương tự, với mỗi , giá trị sẽ nằm trong khoảng .
Lúc này ta có thể áp dụng CDQ để tính toán.
Ta cần đi từ đến . Ở mỗi bước, ta sẽ tăng chiều lên đơn vị, chiều sẽ thành (nếu ta sử dụng jetpack) hoặc (nếu ta không sử dụng jetpack). Ngoài ra, ta sẽ chỉ có trong tối đa bước liên tục. Hỏi có bao nhiêu cách đi thỏa mãn.
Gọi là số cách di chuyển từ đến . Nếu điểm hạ cánh trước đó là , ta sẽ có cách để đi từ đến và không hạ cánh ở giữa đường nếu chẵn, ngoài ra ta sẽ không có cách để đi từ đến . Lúc này ta định nghĩa:
và
Ta có thể thấy lúc này ta có thể tính từ các giá trị và với .
Gọi , , lần lượt là hàm sinh cho , và . Khi này ta có thể viết lại biểu thức trên thành:
Do chia hết cho , lúc này bài toán có thể chuyển về:
Vậy ta đã có thể áp dụng được CDQ Convolution để hoàn thành bài toán.
Đếm số cây nhị phân đầy đủ với lá sao cho với mỗi đỉnh có con, số lá ở cây con bên trái không hơn số lá ở cây con bên phải quá .
Gọi là số cây thỏa mãn có lá, ta dễ thấy rằng:
Với trường hợp cơ sở là và , ta có thể viết lại thành:
Lấy là hàm sinh của và là hàm sinh của .
Khi này ta có liên hệ lặp lại là:
Viết lại theo hàm sinh:
tương đương với:
Ta có thể thấy chia hết cho vì và biết được hệ số bậc của khi ta có thể lấy hệ số bậc của từ định nghĩa của .
Qua đây, ta có thể áp dụng CDQ Convolution để hoàn thành bài toán.
Ta có thể thấy các ví dụ đều có thể có phía phải của phương trình đều có thể biến đổi theo cách giống với tích chập. Tuy vậy, trên thực tế có rất nhiều hàm mà việc này gần như không thể thực hiện. Ví dụ các trường hợp sau trong điều kiện tương tự bài toán nền tảng (hệ số của sẽ có sau khi có hệ số của ):
Các hàm trên là khá phổ thông trong các chuỗi lũy thừa hình thức (formal power series) (độc giả có thể đọc thêm tại đây). Ta có thể viết lại chúng theo dạng tích chập để có thể áp dụng CDQ. Tuy vậy, ta sẽ cần thực hiện một số bước khá "adhoc" cho từng hàm. Việc này là khá bất tiện nên ta cần tìm một hướng giải chung cho các bài toán.
Ta có: với là các hàm có thể đạo hàm được (differentiable).
Khi này ta có thể viết lại theo cách giống với thuật toán Newton:
Ta có thể thấy công thức này có thể dùng được với mọi . Ta có thể thấy rằng với là hệ số đầu tiên của , khi này có thể chia hết cho . Nói theo cách khác:
Ở công thức này, ta vẫn không biết về , thế nhưng lúc này không còn là đối số của nữa. Do đó phía bên phải lúc này là một hàm tuyến tính của . Lúc này ta đã có thể chuyển thành với để có thể áp dụng CDQ Convolution.