CDQ Divide and Conquer

Trội ba chiều

Sắp các điểm theo $(a, b, c)$. Hàm cdq(l, r):

1. Gọi cdq(l, mid) và cdq(mid + 1, r); sau đó mỗi nửa đã được sắp theo $b$ (ghép như sắp xếp trộn).
2. Ghép hai nửa theo $b$. Gặp phần tử trái thì cộng vào Fenwick tại vị trí $c$; gặp phần tử phải thì hỏi tổng tiền tố tới $c$ của nó. Mọi phần tử trái có $a$ không lớn hơn mọi phần tử phải, nên điều kiện còn lại đúng là $b_j \le b_i$ và $c_j \le c_i$.
3. Xóa các phần tử trái khỏi Fenwick bằng cách cộng ngược, không xóa cả mảng.

Mỗi tầng tốn $O(n \log k)$, có $\log n$ tầng: $O(n \log n \log k)$.

Điểm trùng nhau. Hai điểm bằng nhau ở cả ba tọa độ trội lẫn nhau, nhưng CDQ chỉ đếm từ trái sang phải. Gộp các điểm trùng thành một phần tử có trọng số cnt, cộng cnt vào Fenwick; kết quả của một nhóm là số đếm được cộng cnt - 1 (các bản sao khác trong nhóm). Sau khi gộp, nếu $a_j = a_i$ với $j$ trái, $i$ phải thì $(b_j, c_j)$ đứng trước $(b_i, c_i)$ theo thứ tự từ điển, nên phần tử phải không thể trội phần tử trái và không cặp nào bị bỏ sót.

Hình dưới là bản hai chiều cho dễ thấy: điểm đã sắp theo $a$, mỗi lần ghép thì nửa trái (xanh dương) đóng góp cho nửa phải (xanh lá).

Ví dụPhổ Thống Trị Ba Chiều

Đề. $n \le 10^5$ điểm $(a_i, b_i, c_i)$ với tọa độ tới $k \le 2 \cdot 10^5$. Với mỗi $i$, $f_i$ là số $j \ne i$ có cả ba tọa độ không lớn hơn. In số điểm có $f = d$ với mỗi $d = 0..n-1$.

Lời giải. Sắp các điểm theo $(a, b, c)$ và gộp các điểm trùng nhau thành một bản kèm số bản sao cnt. Khi đó nếu $j$ có cả ba tọa độ không lớn hơn $i$ và hai điểm khác nhau, thì $j$ đứng trước $i$ theo thứ tự từ điển, nên chỉ cần đếm các điểm đứng trước. CDQ chia đôi dãy: cặp nằm trong cùng một nửa do đệ quy lo; cặp ($j$ ở nửa trái, $i$ ở nửa phải) đã chắc $a_j \le a_i$, chỉ còn so $b$ và $c$: quét theo $b$, Fenwick theo $c$.

Bước 1: gộp điểm trùng. Sau khi sắp, điểm giống hệt điểm trước thì tăng cnt, ngược lại mở một bản mới. Không gộp thì hai bản sao của cùng một điểm có thể rơi vào hai nửa, và bản đứng sau sẽ không được tính cho bản đứng trước.

for (int i = 1; i <= n; i++) {
    if (m && tmp[i].a == p[m].a && tmp[i].b == p[m].b && tmp[i].c == p[m].c) p[m].cnt++;
    else p[++m] = tmp[i], p[m].cnt = 1, p[m].res = 0;
}

Bước 2: ghép hai nửa. Gọi hai nửa trước; khi trả về, mỗi nửa đã được sắp lại theo $b$ (nhờ bước trộn ở cuối hàm), nên quét được như trộn hai dãy. Với mỗi j ở nửa phải, đưa vào Fenwick mọi i ở nửa trái có $b_i \le b_j$, mỗi điểm cộng cnt của nó tại vị trí $c$. get(p[j].c) là số điểm trái có $b$ và $c$ đều không lớn hơn.

int i = l, t = l;
for (int j = mid + 1; j <= r; j++) {
    while (i <= mid && p[i].b <= p[j].b) add(p[i].c, p[i].cnt), tmp[t++] = p[i++];
    p[j].res += get(p[j].c);
    tmp[t++] = p[j];
}

Bước 3: hoàn tác và trộn. Trừ lại đúng các điểm đã cộng, không xóa cả mảng Fenwick. tmp là kết quả trộn hai nửa theo $b$, chép lại vào p[l..r].

for (int x = l; x < i; x++) add(p[x].c, -p[x].cnt);
while (i <= mid) tmp[t++] = p[i++];
for (int x = l; x <= r; x++) p[x] = tmp[x];

Bước 4: kết quả. Một điểm có res điểm khác nằm dưới nó, cộng cnt - 1 bản sao của chính nó. Cả nhóm bản sao có cùng $f$, nên cộng cnt vào ans tại chỉ số đó.

for (int i = 1; i <= m; i++) ans[p[i].res + p[i].cnt - 1] += p[i].cnt;

#include <bits/stdc++.h>
using namespace std;
#define ll long long

const int N = 1e5 + 5, K = 2e5 + 5;
struct P {
    int a, b, c, cnt, res;
};
int n, k, m, bit[K], ans[N];
P p[N], tmp[N];

bool cmp(P x, P y) {
    if (x.a != y.a) return x.a < y.a;
    if (x.b != y.b) return x.b < y.b;
    return x.c < y.c;
}

void add(int i, int v) {
    for (; i <= k; i += i & -i) bit[i] += v;
}

int get(int i) {
    int s = 0;
    for (; i; i -= i & -i) s += bit[i];
    return s;
}

void cdq(int l, int r) {
    if (l == r) return;
    int mid = (l + r) / 2;
    cdq(l, mid);
    cdq(mid + 1, r);
    int i = l, t = l;
    for (int j = mid + 1; j <= r; j++) {
        while (i <= mid && p[i].b <= p[j].b) add(p[i].c, p[i].cnt), tmp[t++] = p[i++];
        p[j].res += get(p[j].c);
        tmp[t++] = p[j];
    }
    for (int x = l; x < i; x++) add(p[x].c, -p[x].cnt);
    while (i <= mid) tmp[t++] = p[i++];
    for (int x = l; x <= r; x++) p[x] = tmp[x];
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> k;
    for (int i = 1; i <= n; i++) cin >> tmp[i].a >> tmp[i].b >> tmp[i].c;
    sort(tmp + 1, tmp + n + 1, cmp);
    for (int i = 1; i <= n; i++) {
        if (m && tmp[i].a == p[m].a && tmp[i].b == p[m].b && tmp[i].c == p[m].c) p[m].cnt++;
        else p[++m] = tmp[i], p[m].cnt = 1, p[m].res = 0;
    }
    cdq(1, m);
    for (int i = 1; i <= m; i++) ans[p[i].res + p[i].cnt - 1] += p[i].cnt;
    for (int d = 0; d < n; d++) cout << ans[d] << '\n';
}

ChạyInput5 3
1 1 1
1 1 1
2 2 2
2 1 3
3 3 3

Output0
2
2
0
1

Mỗi tầng đệ quy $O(n \log k)$, có $\log n$ tầng: $O(n \log n \log k)$. Một chi tiết nhỏ nhưng quyết định tốc độ là cách dọn Fenwick sau mỗi lần ghép:

Hoàn tác đúng những ô đã cộng nhanh hơn xóa cả Fenwick khoảng 35 lần, vì Fenwick lớn mà mỗi lần ghép chỉ đụng vài ô. Quy tắc: dọn cấu trúc bằng đúng những thao tác đã làm, đừng memset trong đệ quy.

Thời gian làm chiều

Bài có cập nhật và truy vấn xen kẽ: truy vấn chỉ chịu ảnh hưởng của các cập nhật xảy ra trước. Coi chỉ số thao tác là tọa độ thứ nhất; dãy thao tác vốn đã sắp theo nó. Ở mỗi lần ghép, cập nhật nửa trái tác động lên truy vấn nửa phải, và bài còn lại là bài tĩnh: điểm có trọng số, hỏi tổng trong vùng.

Truy vấn hình chữ nhật tách thành bốn truy vấn góc $(x, y)$ có dấu theo bao hàm loại trừ, mỗi góc hỏi tổng các điểm có $x' \le x$, $y' \le y$. Khi ghép theo $x$, cập nhật cùng $x$ phải đứng trước truy vấn. Fenwick theo $y$ có thể dài bằng cạnh bảng mà không cần nén, miễn mỗi lần chỉ hoàn tác những ô vừa cộng.

Ví dụTổng Trên Bảng Động

Đề. Bảng $w \times w$, $w \le 2 \cdot 10^6$. Tới $1.6 \cdot 10^5$ lệnh cộng giá trị vào một ô và $10^4$ lệnh hỏi tổng hình chữ nhật, xen kẽ theo thời gian, kết thúc bằng lệnh 3.

Lời giải. Tổng hình chữ nhật $[x_1, x_2] \times [y_1, y_2]$ bằng tổng bốn góc có dấu: $S(x_2, y_2) - S(x_1 - 1, y_2) - S(x_2, y_1 - 1) + S(x_1 - 1, y_1 - 1)$, với $S(x, y)$ là tổng các ô có tọa độ không lớn hơn. Mỗi lệnh hỏi thành bốn truy vấn góc. Dãy thao tác đã sắp theo thời gian, chính là chiều thứ nhất của CDQ: lệnh cộng ở nửa trái tác động lên truy vấn ở nửa phải. Trong một lần ghép, bài còn lại là bài tĩnh hai chiều: quét theo $x$, hỏi Fenwick theo $y$.

Bước 1: tách lệnh hỏi thành bốn góc. type = 0 là lệnh cộng v vào ô $(x, y)$; type = 1 là một góc của truy vấn id, với v là dấu $\pm 1$.

q++;
op[++m] = {x2, y2, 1, q, 1};
op[++m] = {x1 - 1, y2, 1, q, -1};
op[++m] = {x2, y1 - 1, 1, q, -1};
op[++m] = {x1 - 1, y1 - 1, 1, q, 1};

Bước 2: ghép. Khung như ví dụ trước. Chỉ lệnh cộng được thêm vào Fenwick (và được hoàn tác); góc hỏi chỉ đọc. Điều kiện op[i].x <= op[j].x lấy cả $x$ bằng nhau, đúng nghĩa “không lớn hơn” của $S$.

for (int j = mid + 1; j <= r; j++) {
    while (i <= mid && op[i].x <= op[j].x) {
        if (op[i].type == 0) add(op[i].y, op[i].v);
        tmp[t++] = op[i++];
    }
    if (op[j].type == 1) ans[op[j].id] += op[j].v * get(op[j].y);
    tmp[t++] = op[j];
}

Góc có $x_1 - 1 = 0$ hay $y_1 - 1 = 0$: không lệnh cộng nào có $x \le 0$, và get(0) trả 0, nên góc ấy đóng góp 0 như mong muốn. Fenwick dài $w$ tới $2 \cdot 10^6$ mà không cần nén, vì mỗi lần ghép chỉ hoàn tác đúng các ô đã cộng.

#include <bits/stdc++.h>
using namespace std;
#define ll long long

const int M = 2e5 + 5, W = 2e6 + 5;
struct Op {
    int x, y, type, id;
    ll v;
};
int w, m, q;
ll bit[W], ans[M];
Op op[M], tmp[M];

void add(int i, ll v) {
    for (; i <= w; i += i & -i) bit[i] += v;
}

ll get(int i) {
    ll s = 0;
    for (; i > 0; i -= i & -i) s += bit[i];
    return s;
}

void cdq(int l, int r) {
    if (l == r) return;
    int mid = (l + r) / 2;
    cdq(l, mid);
    cdq(mid + 1, r);
    int i = l, t = l;
    for (int j = mid + 1; j <= r; j++) {
        while (i <= mid && op[i].x <= op[j].x) {
            if (op[i].type == 0) add(op[i].y, op[i].v);
            tmp[t++] = op[i++];
        }
        if (op[j].type == 1) ans[op[j].id] += op[j].v * get(op[j].y);
        tmp[t++] = op[j];
    }
    for (int x = l; x < i; x++)
        if (op[x].type == 0) add(op[x].y, -op[x].v);
    while (i <= mid) tmp[t++] = op[i++];
    for (int x = l; x <= r; x++) op[x] = tmp[x];
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int type;
    cin >> type >> w;
    while (cin >> type && type != 3) {
        if (type == 1) {
            int x, y;
            ll a;
            cin >> x >> y >> a;
            op[++m] = {x, y, 0, 0, a};
        } else {
            int x1, y1, x2, y2;
            cin >> x1 >> y1 >> x2 >> y2;
            q++;
            op[++m] = {x2, y2, 1, q, 1};
            op[++m] = {x1 - 1, y2, 1, q, -1};
            op[++m] = {x2, y1 - 1, 1, q, -1};
            op[++m] = {x1 - 1, y1 - 1, 1, q, 1};
        }
    }
    if (m) cdq(1, m);
    for (int i = 1; i <= q; i++) cout << ans[i] << '\n';
}

ChạyInput0 5
1 2 2 3
1 4 3 5
2 1 1 3 3
1 3 3 2
2 2 2 4 3
3

Output3
10

Độ phức tạp: $O(m \log m \log w)$ với $m$ là tổng số lệnh và góc.

Thời điểm xóa

Bài xóa dần phần tử và hỏi số nghịch thế trước mỗi lần xóa: đáp án trước lần xóa thứ $k$ bằng tổng nghịch thế ban đầu trừ đi số nghịch thế đã mất ở $k - 1$ lần xóa đầu. Xóa phần tử $e$ làm mất các cặp nghịch thế giữa $e$ và những phần tử còn lại lúc đó, tức những phần tử bị xóa sau $e$ hoặc không bao giờ bị xóa.

Mỗi phần tử có ba tọa độ: thời điểm xóa $t$ (không bị xóa thì $t = m + 1$), vị trí $p$, giá trị $v$. Sắp theo $t$ giảm dần, với mỗi $e$ đếm các phần tử đứng trước (bị xóa muộn hơn) có $p < p_e, v > v_e$ hoặc $p > p_e, v < v_e$. Hai trường hợp là hai lượt quét trong cùng một lần ghép: $p$ tăng cho trường hợp đầu, $p$ giảm cho trường hợp sau.

Ví dụNghịch Thế Khi Xóa

Đề. Hoán vị độ dài $n \le 10^5$, xóa lần lượt $m \le 5 \cdot 10^4$ giá trị. In số nghịch thế ngay trước mỗi lần xóa.

Lời giải. Gọi $t_e$ là thời điểm xóa phần tử $e$ ($m + 1$ nếu không bị xóa). Lần xóa $e$ làm mất đúng các cặp nghịch thế giữa $e$ và những phần tử còn lại lúc đó, tức các phần tử có $t > t_e$. Sắp phần tử theo $t$ giảm dần, đếm cho mỗi $e$ số phần tử đứng trước nó tạo nghịch thế với nó: vị trí nhỏ hơn mà giá trị lớn hơn, hoặc vị trí lớn hơn mà giá trị nhỏ hơn. Đó là bài đếm cặp ba chiều $(t, p, v)$, giải bằng CDQ như ví dụ đầu.

Bước 1: nghịch thế ban đầu. Fenwick đếm total, rồi trừ lại để Fenwick về 0. where[v] là vị trí của giá trị $v$, dùng để ghi tim cho phần tử bị xóa. Sau đó id sắp theo thời điểm xóa giảm dần; phần tử không bị xóa đứng đầu, và chúng không bao giờ cần lost.

total += i - 1 - get(a[i]);
add(a[i], 1);

Bước 2: lượt thứ nhất của ghép. Hai nửa đã sắp theo vị trí. Quét j ở nửa phải theo vị trí tăng, đưa vào Fenwick các phần tử trái có vị trí nhỏ hơn. (i - l) - get(a[id[j]]) là số phần tử đó có giá trị lớn hơn.

for (int j = mid + 1; j <= r; j++) {
    while (i <= mid && pos[id[i]] < pos[id[j]]) add(a[id[i]], 1), i++;
    lost[id[j]] += (i - l) - get(a[id[j]]);
}

Bước 3: lượt thứ hai. Quét ngược, đưa vào các phần tử trái có vị trí lớn hơn; get(a[id[j]] - 1) đếm những phần tử có giá trị nhỏ hơn. Sau mỗi lượt hoàn tác Fenwick, rồi merge hai nửa theo vị trí để tầng trên quét được.

for (int j = r; j > mid; j--) {
    while (i >= l && pos[id[i]] > pos[id[j]]) add(a[id[i]], 1), i--;
    lost[id[j]] += get(a[id[j]] - 1);
}

Bước 4: in. Trước lần xóa thứ $k$ in total, rồi trừ lost của phần tử vừa xóa.

for (int k = 1; k <= m; k++) {
    cout << total << '\n';
    total -= lost[where[del[k]]];
}

#include <bits/stdc++.h>
using namespace std;
#define ll long long

const int N = 1e5 + 5;
int n, m, a[N], pos[N], tim[N], id[N], tmp[N], bit[N];
ll lost[N];

void add(int i, int v) {
    for (; i <= n; i += i & -i) bit[i] += v;
}

int get(int i) {
    int s = 0;
    for (; i; i -= i & -i) s += bit[i];
    return s;
}

bool byTime(int x, int y) {
    return tim[x] > tim[y];
}

bool byPos(int x, int y) {
    return pos[x] < pos[y];
}

void cdq(int l, int r) {
    if (l == r) return;
    int mid = (l + r) / 2;
    cdq(l, mid);
    cdq(mid + 1, r);
    int i = l;
    for (int j = mid + 1; j <= r; j++) {
        while (i <= mid && pos[id[i]] < pos[id[j]]) add(a[id[i]], 1), i++;
        lost[id[j]] += (i - l) - get(a[id[j]]);
    }
    for (int x = l; x < i; x++) add(a[id[x]], -1);
    i = mid;
    for (int j = r; j > mid; j--) {
        while (i >= l && pos[id[i]] > pos[id[j]]) add(a[id[i]], 1), i--;
        lost[id[j]] += get(a[id[j]] - 1);
    }
    for (int x = mid; x > i; x--) add(a[id[x]], -1);
    merge(id + l, id + mid + 1, id + mid + 1, id + r + 1, tmp + l, byPos);
    for (int x = l; x <= r; x++) id[x] = tmp[x];
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> m;
    ll total = 0;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        pos[i] = i, tim[i] = m + 1, id[i] = i;
        total += i - 1 - get(a[i]);
        add(a[i], 1);
    }
    for (int i = 1; i <= n; i++) add(a[i], -1);
    vector<int> where(n + 1), del(m + 1);
    for (int i = 1; i <= n; i++) where[a[i]] = i;
    for (int k = 1; k <= m; k++) {
        cin >> del[k];
        tim[where[del[k]]] = k;
    }
    stable_sort(id + 1, id + n + 1, byTime);
    cdq(1, n);
    for (int k = 1; k <= m; k++) {
        cout << total << '\n';
        total -= lost[where[del[k]]];
    }
}

ChạyInput5 3
3 1 5 2 4
5
1
3

Output4
2
1

Độ phức tạp: $O(n \log^2 n)$.

CDQ cho DP

Khi $dp_i$ phụ thuộc mọi $j$ đứng trước thỏa vài bất đẳng thức (chuỗi dài nhất nhiều chiều), thứ tự gọi phải đổi: cdq(l, mid) xong hẳn, chuyển đóng góp từ nửa trái sang nửa phải, rồi mới gọi cdq(mid + 1, r). Lúc chuyển, mọi $dp_j$ của nửa trái đã cuối cùng; nửa phải nhận thêm đóng góp trước khi tự đệ quy.

Nửa phải còn phải đệ quy theo thứ tự tọa độ đầu, nên không được trộn mảng gốc theo tọa độ thứ hai. Sắp hai danh sách chỉ số riêng cho lần chuyển, mỗi tầng $O(n \log n)$, tổng $O(n \log^2 n)$. Fenwick lưu cặp (độ dài tốt nhất, số cách) và ghép bằng “lấy độ dài lớn hơn, bằng nhau thì cộng số cách”.

Ví dụChuỗi Điểm Ba Chiều

Đề. $T \le 3$ test, mỗi test $N \le 10^5$ điểm ba chiều khác nhau. Tìm độ dài lớn nhất của chuỗi có cả ba tọa độ không giảm, và số tập điểm đạt độ dài đó theo mô-đun $2^{30}$.

Lời giải. $len_i$ là độ dài chuỗi dài nhất kết thúc ở điểm $i$, $cnt_i$ là số chuỗi đạt độ dài đó. Sắp theo $(x, y, z)$; các điểm khác nhau nên bước trước $j$ của $i$ (cả ba tọa độ không lớn hơn) luôn đứng trước $i$. CDQ cho quy hoạch động phải đổi thứ tự gọi: xử lý xong hẳn nửa trái, chuyển đóng góp từ nửa trái sang nửa phải, rồi mới đệ quy nửa phải. Lúc chuyển, mọi $len_j$ bên trái đã cuối cùng, nên giá trị truyền đi là đúng.

Bước 1: Fenwick giữ cặp. Mỗi ô giữ (độ dài tốt nhất, số cách), gộp theo luật “độ dài lớn hơn thì thay, bằng nhau thì cộng số cách”. Phép gộp này kết hợp và giao hoán, nên dùng được trong Fenwick. & MASK là lấy dư cho $2^{30}$. clear đặt lại đúng các ô đã đụng.

void upd(int p, int l, ll c) {
    for (; p <= m; p += p & -p) {
        if (l > bl[p]) bl[p] = l, bc[p] = c;
        else if (l == bl[p]) bc[p] = (bc[p] + c) & MASK;
    }
}

Bước 2: thứ tự gọi. cdq(l, mid) trước. Rồi chép chỉ số hai nửa vào L, R và sắp theo $y$; không sắp thẳng ord, vì nửa phải còn phải đệ quy theo thứ tự $(x, y, z)$.

cdq(l, mid);
vector<int> L(ord + l, ord + mid + 1), R(ord + mid + 1, ord + r + 1);
sort(L.begin(), L.end(), byY);
sort(R.begin(), R.end(), byY);

Bước 3: chuyển đóng góp. Quét R theo $y$ tăng, đưa vào Fenwick các điểm trái có $y$ không lớn hơn, rồi hỏi tiền tố tới $z_j$ (đã nén): được bước trước tốt nhất ở nửa trái.

for (int j : R) {
    while (i < (int)L.size() && y[L[i]] <= y[j]) upd(z[L[i]], len[L[i]], cnt[L[i]]), i++;
    int bestL;
    ll bestC;
    ask(z[j], bestL, bestC);
    if (bestL + 1 > len[j]) len[j] = bestL + 1, cnt[j] = bestC;
    else if (bestL + 1 == len[j]) cnt[j] = (cnt[j] + bestC) & MASK;
}
for (int k = 0; k < i; k++) clear(z[L[k]]);
cdq(mid + 1, r);

Cuối cùng mới cdq(mid + 1, r): các điểm nửa phải đã nhận đủ đóng góp từ nửa trái trước khi truyền tiếp cho nhau.

#include <bits/stdc++.h>
using namespace std;
#define ll long long

const int N = 1e5 + 5;
const ll MASK = (1 << 30) - 1;
int n, m, x[N], y[N], z[N], ord[N], len[N], bl[N];
ll cnt[N], bc[N];

bool byXYZ(int i, int j) {
    if (x[i] != x[j]) return x[i] < x[j];
    if (y[i] != y[j]) return y[i] < y[j];
    return z[i] < z[j];
}

bool byY(int i, int j) {
    return y[i] < y[j];
}

void upd(int p, int l, ll c) {
    for (; p <= m; p += p & -p) {
        if (l > bl[p]) bl[p] = l, bc[p] = c;
        else if (l == bl[p]) bc[p] = (bc[p] + c) & MASK;
    }
}

void ask(int p, int &l, ll &c) {
    l = 0, c = 0;
    for (; p; p -= p & -p) {
        if (bl[p] > l) l = bl[p], c = bc[p];
        else if (bl[p] == l) c = (c + bc[p]) & MASK;
    }
}

void clear(int p) {
    for (; p <= m; p += p & -p) bl[p] = 0, bc[p] = 0;
}

void cdq(int l, int r) {
    if (l == r) return;
    int mid = (l + r) / 2;
    cdq(l, mid);
    vector<int> L(ord + l, ord + mid + 1), R(ord + mid + 1, ord + r + 1);
    sort(L.begin(), L.end(), byY);
    sort(R.begin(), R.end(), byY);
    int i = 0;
    for (int j : R) {
        while (i < (int)L.size() && y[L[i]] <= y[j]) upd(z[L[i]], len[L[i]], cnt[L[i]]), i++;
        int bestL;
        ll bestC;
        ask(z[j], bestL, bestC);
        if (bestL + 1 > len[j]) len[j] = bestL + 1, cnt[j] = bestC;
        else if (bestL + 1 == len[j]) cnt[j] = (cnt[j] + bestC) & MASK;
    }
    for (int k = 0; k < i; k++) clear(z[L[k]]);
    cdq(mid + 1, r);
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int T;
    cin >> T;
    while (T--) {
        cin >> n;
        vector<int> zs;
        for (int i = 1; i <= n; i++) cin >> x[i] >> y[i] >> z[i], zs.push_back(z[i]), ord[i] = i;
        sort(zs.begin(), zs.end());
        zs.erase(unique(zs.begin(), zs.end()), zs.end());
        m = zs.size();
        for (int i = 1; i <= n; i++) {
            z[i] = lower_bound(zs.begin(), zs.end(), z[i]) - zs.begin() + 1;
            len[i] = 1, cnt[i] = 1;
        }
        sort(ord + 1, ord + n + 1, byXYZ);
        cdq(1, n);
        int best = 0;
        ll ways = 0;
        for (int i = 1; i <= n; i++) {
            if (len[i] > best) best = len[i], ways = cnt[i];
            else if (len[i] == best) ways = (ways + cnt[i]) & MASK;
        }
        cout << best << ' ' << ways << '\n';
    }
}

ChạyInput1
4
1 1 1
2 2 2
2 3 1
3 3 3

Output3 2

Độ phức tạp: mỗi tầng sắp hai danh sách và dùng Fenwick, đều $O(n \log n)$: tổng $O(n \log^2 n)$.