题解：P10800 「CZOI-R1」卡牌

· · 题解

分享一个比较难写的做法。

::::info[三维弱化弱化版]{open} 考虑三维的部分分，虽然好像没有这个部分分呢？就是卡牌只有三个属性，只需要满足两个比较大就可以赢。先只用做到 n\le 10^3。

枚举 C 属性的值 c，那么对于 c_i\ge c，则要求 a_i<a,b_i<b。那其实相当于当 a>a_i,b>b_i 时，C 属性可以取 c。

我们考虑预处理出 sa_i 表示属性 A 的值为 i 时，C 属性可以取多少种数。sb 同理，容易预处理。你可能发现这两个数组具有单调性，但是在这个版本内没有什么用。

那么接下来我们规约成了二维的形式，只需要枚举 a,b 了，但是对于一个合法的 a,b，它会产生 \min(sa_a,sb_b) 的贡献。我们做到了 O(n^2)。 ::::

::::info[三维弱化版]{open} 同样的还是只有三个属性，但是要求做到 n\le 5\times 10^5。这个做法和「弱化弱化版」没有关系。

「三个属性，至少有两个要大于其它的」相当于「三个属性，不能有两个小于等于其它的」。

我们可以把这个限制弄成类似于 2-SAT 那样的限制，也就是对于 A\le a_i\Rarr B>b_i、A\le a_i\Rarr C>c_i 等等等等。

稍加思索可以发现，限制 A\le a_i\Rarr B>b_i 与 B\le b_i\Rarr A>a_i 是没有必要重复存在的，我们保留一条就好。

所以最后剩下三条限制：A\le a_i\Rarr B>b_i、A\le a_i\Rarr C>c_i、B\le b_i\Rarr C>c_i。

考虑求出 lim_{A,B,a} 表示我们选择的卡牌 A 属性为 a，那么 B 属性至少要为多少？因为不能有两个小于等于其它的，那么我们的 B 属性要大于「所有 A 属性大于等于 a 的卡牌的 B 属性」，这个可以容易处理出来。

同理，计算出 lim_{A,C,*}、lim_{B,C,*}。

预处理完后考虑如何计算答案，先枚举 A 的值 a，那么 B 的值至少要为 lim_{A,B,a}，C 的值至少要为 lim_{A,C,a}。

那么我们画一张图，其中横坐标为 B 的值，纵坐标为 C 的值：

这里你应当发现了，lim_{B,C,*} 的值是递减的。

然后我们发现贡献是橙色那一块，可以分成前面 lim_{B,C,*}\ge lim_{A,C,a} 和后面 lim_{B,C,*}< lim_{A,C,a}。

前者的贡献可以用 lim 的前缀和计算，后者的贡献是一个矩阵，乘法简单计算即可。

中间的分界点可以用指针扫做到 O(n)，也可以二分带个 \log。 ::::

::::info[原版]{open} 相信你已经想到把上面两个做法缝合起来了。

首先枚举 D 属性的值 d，那么预处理出 sa,sb,sc，接下来就变成带权的「三维弱化版」了。

但是带权似乎不是很好处理？因为是要取 \min。

枚举 a/b/c 为 sa 最小的那个，然后我们发现，因为要求 sb>sa，所以 B 的下限应当是还要和最小的满足 sb_i>sa_a 的 i 取 \max 的，C 同理。

然后你还需要处理有相等的情况，那太麻烦了。考虑合并同类项，我们只需要考虑：

四种情况。

前面三种是好处理的，第四种的 B 和 C 还有取值的上界，需要处理一下。 ::::

::::success[参考代码]

// 参考 https://www.luogu.com.cn/article/kjt9ubyn
#include <bits/stdc++.h>
using namespace std;
namespace {
constexpr int N = 5e5 + 10;
using uint = unsigned int;
struct card { int a[4]; } p[N];
int n, m, pos, mx[3], s[3][N], l[3][3][N];
uint ans, ls[3][3][N];
void solve(int i, int j, int k, int mny, int mnz, int mxy, int mxz, uint coef) {
    if (mny > mxy || mnz > mxz) return;
    // 二分一个最小的点，使得 l[j][k][x] <= mxz
    int L = mny, R = mxy, x = mxy + 1;
    while (L <= R) {
        int mid = (L + R) >> 1;
        if (l[j][k][mid] <= mxz) {
            x = mid;
            R = mid - 1;
        } else {
            L = mid + 1;
        }
    }
    // 这个点前面全部不贡献
    mny = x;

    // 二分一个最大的点，使得 l[j][k][x] >= mnz
    L = mny, R = mxy, x = mny - 1;
    while (L <= R) {
        int mid = (L + R) >> 1;
        if (l[j][k][mid] >= mnz) {
            x = mid;
            L = mid + 1;
        } else {
            R = mid - 1;
        }
    }
    // 这个点后面的全部贡献
    ans += coef * (mxy - x) * (mxz - mnz + 1);
    mxy = x;

    // 中间是一个前缀和,lbc的前缀和
    ans += coef * (((uint)(mxy - mny + 1) * (mxz + 1)) - (ls[j][k][mxy] - ls[j][k][mny - 1]));
}
void entry() {
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);

    cin >> n >> m;
    for (int i = 1; i <= m; i++) cin >> p[i].a[0] >> p[i].a[1] >> p[i].a[2] >> p[i].a[3];

    sort(p + 1, p + 1 + m, [](const auto &x, const auto &y) { return x.a[3] > y.a[3]; });
    pos = 1;
    for (int x = n; x >= 1; x--) {
        while (pos <= m && p[pos].a[3] == x) {
            for (int j = 0; j < 3; j++) mx[j] = max(mx[j], p[pos].a[j]);
            pos++;
        }
        for (int j = 0; j < 3; j++) s[j][mx[j] + 1]++;
    }
    for (int i = 1; i <= n; i++) for (int j = 0; j < 3; j++) s[j][i] += s[j][i - 1];

    for (int i = 0; i < 3; i++) {
        sort(p + 1, p + 1 + m, [&](const auto &x, const auto &y) { return x.a[i] > y.a[i]; });
        pos = 1;
        for (int j = 0; j < 3; j++) l[i][j][n + 1] = 1;
        for (int x = n; x >= 1; x--) {
            for (int j = 0; j < 3; j++) l[i][j][x] = l[i][j][x + 1];
            while (pos <= m && p[pos].a[i] == x) {
                for (int j = 0; j < 3; j++) l[i][j][x] = max(l[i][j][x], p[pos].a[j] + 1);
                pos++;
            }
        }
    }

    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            for (int x = 1; x <= n; x++) ls[i][j][x] = l[i][j][x] + ls[i][j][x - 1];
        }
    }

    for (int i = 0; i < 3; i++) {
        int j = (i + 1) % 3, k = (i + 2) % 3;
        // sa <= sb && sa < sc
        for (int x = 1; x <= n; x++) {
            int mny = max<int>(lower_bound(s[j] + 1, s[j] + 1 + n, s[i][x]) - s[j], l[i][j][x]);
            int mxy = n;
            int mnz = max<int>(upper_bound(s[k] + 1, s[k] + 1 + n, s[i][x]) - s[k], l[i][k][x]);
            int mxz = n;
            solve(i, j, k, mny, mnz, mxy, mxz, s[i][x]);
        }
    }

    // sa = sb = sc
    for (int x = 1; x <= n; x++) {
        int mny = max<int>(lower_bound(s[1] + 1, s[1] + 1 + n, s[0][x]) - s[1], l[0][1][x]);
        int mxy = upper_bound(s[1] + 1, s[1] + 1 + n, s[0][x]) - 1 - s[1];
        int mnz = max<int>(lower_bound(s[2] + 1, s[2] + 1 + n, s[0][x]) - s[2], l[0][2][x]);
        int mxz = upper_bound(s[2] + 1, s[2] + 1 + n, s[0][x]) - 1 - s[2];
        solve(0, 1, 2, mny, mnz, mxy, mxz, s[0][x]);
    }

    cout << ans << '\n';
}
}
int main() { entry(); }

::::