题目链接：HDU 4742

RD 很擅长弹珠游戏。最近他发现了一种 $\text{3D}$ 弹珠游戏，一共有 $n$ 个求，每个球可以看作一个点。一开始 RD 扔出一个球使它击中另一个球，被击中的球会移动并可能击中另一个球，如此循环下去。但是一旦一个球击中了另一个球，它就会消失。

RD 可以控制每个球的移动方向，但是有一个限制：如果球 $A$ 的坐标为 $(x_1,y_1,z_1)$，球 $B$ 的坐标为 $(x_2,y_2,z_2)$，那么球 $A$ 能击中球 $B$ 当且仅当 $x_1\le x_2$，$y_1\le y_2$，$z_1\le z_2$。

现在，请你帮助 RD 求出可以击中的球的最大数量，以及可以击中这么多球的方案数，对 $2^{30}$ 取模。两个方案中只要有一个球是不同的那么就认为他们不同。

本题有 $T​$ 组数据。

数据范围：$1\le T\le 3$，$1\le n\le 10^5$，$0\le x_i,y_i,z_i\le 2^{30}$。

Solution

我们发现这就是一个三维 $\text{LIS}$ 问题（并求方案数），可以直接套 $\text{CDQ}$ 解决。此处主要提几个注意点：

1. 要注意 $\text{DP}$ 转移循序（从前往后转移），因此我们要先处理子问题 $[l,m]$，再处理 $[l,m]$ 对 $[m+1,r]$ 的影响，最后再递归计算 $[m+1,r]$ 的转移。
2. 我们用树状数组维护 $2$ 个值：最大长度、方案数。其中在计算完贡献后要把对应树状数组的位置清空。
3. 把两个区间排序后，在计算 $[m+1,r]$ 之前要把右区间重新以 $x_i$ 为第一关键字排序。

时间复杂度：$\mathcal O(n\log^2 n)$

Code

#include <cstdio>
#include <algorithm>

typedef std::pair<int, int> pii;

const int N = 1e5 + 5;
const int mod = 1 << 30;

int n, b[N];
pii f[N];

struct Data {
    int x, y, z, idx;
    bool operator<(const Data &b) const {
        return x == b.x ? y == b.y ? z < b.z : y < b.y : x < b.x;
    }
} a[N], t[N];

void add(int &x, int y) {
    (x += y) >= mod && (x -= mod);
}
void upd(pii &x, pii y) {
    if (x.first == y.first) add(x.second, y.second);
    if (x.first < y.first) x = y;
}
struct BIT {
    pii b[N];
    void modify(int x, pii v) {
        for (; x <= n; x += x & -x) upd(b[x], v);
    }
    void clear(int x) {
        for (; x <= n; x += x & -x) b[x] = std::make_pair(0, 0);
    }
    pii query(int x) {
        pii ans = std::make_pair(0, 0);
        for (; x; x ^= x & -x) upd(ans, b[x]);
        return ans;
    }
} bit;

void discretize() {
    for (int i = 1; i <= n; i++) b[i] = a[i].z;
    std::sort(b + 1, b + n + 1);
    int sz = std::unique(b + 1, b + n + 1) - (b + 1);
    for (int i = 1; i <= n; i++) {
        a[i].z = std::lower_bound(b + 1, b + sz + 1, a[i].z) - b;
    }
}
bool cmp(Data a, Data b) {
    return a.y == b.y ? a.z < b.z : a.y < b.y;
}
void CDQ(int l, int r) {
    if (l == r) {
        return;
    }
    int m = (l + r) >> 1;
    CDQ(l, m);
    std::sort(a + l, a + m + 1, cmp);
    std::sort(a + m + 1, a + r + 1, cmp);
    int j = l;
    for (int i = m + 1; i <= r; i++) {
        for (; j <= m && a[j].y <= a[i].y; j++) {
            bit.modify(a[j].z, f[a[j].idx]);
        }
        pii now=bit.query(a[i].z);
        now.first++;
        upd(f[a[i].idx], now);
    }
    for (int i = l; i < j; i++) bit.clear(a[i].z);
    std::sort(a + m + 1, a + r + 1);
    CDQ(m + 1, r);
} 
int main() {
    int T;
    for (scanf("%d", &T); T--; ) {
        scanf("%d", &n);
        for (int i = 1; i <= n; i++) {
            scanf("%d%d%d", &a[i].x, &a[i].y, &a[i].z);
        }
        discretize();
        std::sort(a + 1, a + n + 1);
        for (int i = 1; i <= n; i++) {
            a[i].idx = i;
            f[i] = std::make_pair(1, 1);
        }
        CDQ(1, n);
        pii ans = std::make_pair(0, 0);
        for (int i = 1; i <= n; i++) {
            upd(ans, f[i]);
        }
        printf("%d %d\n", ans.first, ans.second);
    }
    return 0;
}