洛谷P10800 「CZOI-R1」卡牌题解

题意：

Alice 和 Bob 正在玩卡牌游戏。

每张卡牌有四个属性：攻击、防御、速度、血量。

我们称一张卡牌能胜过另一张卡牌，当且仅当其至少有三个属性都大于另一张卡牌。

Bob 拥有 \(m\) 张卡牌，而 Alice 拥有每个属性值在 \([1, n]\) 的所有 \(n^4\) 张卡牌。

现在 Alice 想知道：她有多少张卡牌可以胜过所有 Bob 的卡牌？

输入格式：

第一行包含两个整数 \(n, m\)，分别表示属性值上限和 Bob 的卡牌数量。

接下来 \(m\) 行，每行四个整数 \(a_i, b_i, c_i, d_i\)，表示 Bob 一张卡牌的属性。

输出格式：

输出一行一个整数，表示答案对 \(2^{32}\) 取模后的结果。

数据范围：

对于所有测试数据，\(1 \le n, m \le 5 \times 10^5\)，\(1 \le a_i, b_i, c_i, d_i \le n\)。

因为参考文献1写的非常清楚，并不需要补充过多废话，所以本文大部分段落和原文表述类似。

显然一张卡牌满足条件，则任何严格大于它的卡牌都满足条件

因此满足条件的卡牌是连续的。考虑设 \(f(i,j,k)\) 为前三种属性为 \(i,j,k\) 时满足要求的卡牌数量。

考虑加入一张 \((a,b,c,d)\) 的卡牌时：

小于两种属性大于当前牌的牌显然不行，有 \(f(i,j,k) \gets 0\)
已经有两种属性大于当前牌，则需要一个更强的属性 \(\in (d,n]\) ，于是 \(f(i,j,k)\downarrow (n - d)\) 。
已经有三种属性大于当前牌，肯定 ok ，故没有影响。

怎么优化呢？注意到当 \(n=3\) 时，加入了一张 \((1,1,2,2)\) 的卡牌，此时 \(f\) 的值是这样的： \[ \begin{array}{|lll|lll|llll|} \hline0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 \\ 0 & 1 & 1 & 0 & 1 & 1 & 1 & 3 & 3 \\ 0 & 1 & 1 & 0 & 1 & 1 & 1 & 3 & 3\\\hline \end{array} \] 其中每一行表示 \(i\) ，每一列表示 \(j\) ，每一个块（或者说每一层）表示 \(k\) 。

可以发现，我们做的操作等价于

将前 \(a\) 行对 \(n-d\) 取 min
将前 \(b\) 列对 \(n-d\) 取 min
将前 \(c\) 层对 \(n-d\) 取 min
将一个左上角为原点，右下角为 \((a,b,n)\) 的长方体置零；
将一个左上角为原点，右下角为 \((a,n,c)\) 的长方体置零；
将一个左上角为原点，右下角为 \((n,b,c)\) 的长方体置零。

考虑记 \(a_i\) 为每一行的最小值，\(b_i\) 为每一列的最小值，\(c_i\) 为每一层的最小值。

那么 \(a_i,b_i,c_i\) 只需要从后往前推一遍就能 \(\mathcal{O}(n)\) 得到了。

现在考虑统计答案。考虑对每一层分别求和，同时维护每一列的和。

具体地，我们用数据结构维护以下区间 \([l,r]\) 的信息：

用 \(b_j\) 覆盖时 \(b_j\) 在列区间 \([l,r]\) 的和；
用 \(b_j\) 覆盖时 \(a_i\) 在列区间 \([l,r]\) 的和；
用 \(c_i\) 覆盖时 \(a_i\) 在列区间 \([l,r]\) 的和；
用 \(c_i\) 覆盖时 \(c_i\) 在列区间 \([l,r]\) 的和。

那么我们枚举枚举每一层，处理被取消置零的行和不被 \(c_i\) 覆盖的行，

利用以上四个信息，得到每一列的和后，考虑 \(b_j\) 和 \(c_i\) 覆盖了哪些列，然后去掉被置零的列即可。

时间复杂度 \(\mathcal{O}(m + n \log n)\)

代码：（~~建议看参考文献1的，我没写注释~~）

#include <bits/stdc++.h>
using namespace std;
// #define int long long
// #define INF 0x3f3f3f3f3f3f3f3f
void up(int &x, int y) { x < y ? x = y : 0; }
void down(int &x, int y) { x > y ? x = y : 0; }
#define rep(i, a, b) for(int i = (a), i##END = (b); i <= i##END; i++)
#define Rep(i, a, b) for(int i = (a), i##END = (b); i >= i##END; i--)
#define N ((int)(5e5 + 15))

int n, m;
struct Segment_Tree
{
    #define ls(at) ((at) << 1)
    #define rs(at) ((at) << 1 | 1)
    uint s[N], ans[N * 4], tag[N * 4];
    void push_up(int at) { ans[at] = ans[ls(at)] + ans[rs(at)]; }
    void proc(int l, int r, uint v, int at) { ans[at] += (s[r] - s[l - 1]) * v; tag[at] += v; }
    void push_down(int l, int r, int at)
    {
        if(tag[at])
        {
            int mid = (l + r) >> 1;
            proc(l, mid, tag[at], ls(at));
            proc(mid + 1, r, tag[at], rs(at));
            tag[at] = 0;
        }
    }
    void update(int nl, int nr, uint v, int l = 1, int r = n, int at = 1)
    {
        if(nl <= l && r <= nr) return proc(l, r, v, at);
        push_down(l, r, at); int mid = (l + r) >> 1;
        if(nl <= mid) update(nl, nr, v, l, mid, ls(at));
        if(nr > mid) update(nl, nr, v, mid + 1, r, rs(at));
        push_up(at);
    }
    uint query(int nl, int nr, int l = 1, int r = n, int at = 1)
    {
        if(nl <= l && r <= nr) return ans[at];
        push_down(l, r, at); int mid = (l + r) >> 1;
        uint sum = 0;
        if(nl <= mid) sum += query(nl, nr, l, mid, ls(at));
        if(nr > mid) sum += query(nl, nr, mid + 1, r, rs(at));
        return sum;
    }
    #undef ls
    #undef rs
} t1;
struct BIT
{
    uint tr1[N], tr2[N];
    #define lowbit(x) ((x) & (-x))
    void add(int x, uint v)
    { 
        for(int i = x; i <= n; i += lowbit(i))
            { tr1[i] += v, tr2[i] += v * x; }
    }
    uint qry(int x)
    {
        uint r = 0;
        for(int i = x; i; i -= lowbit(i))
            r += ((uint)x + 1) * tr1[i] - tr2[i]; 
        return r;
    }
    void update(int l, int r, uint v) { add(l, v); add(r + 1, -v); }
    uint query(int l, int r) { return qry(r) - qry(l - 1); }
    #undef lowbit
} t2, t3, t4;
int a[N], b[N], c[N], x[N], y[N], z[N], f[N], g[N], h[N];
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n >> m;
    rep(i, 1, n) a[i] = b[i] = c[i] = n;
    rep(i, 1, m)
    {
        static int ai, bi, ci, di;
        cin >> ai >> bi >> ci >> di; di = n - di;
        down(a[ai], di); down(b[bi], di); down(c[ci], di);
        up(x[ai], bi); up(y[ci], ai); up(z[ci], bi);
    }
    Rep(i, n - 1, 1)
    {
        down(a[i], a[i + 1]); down(b[i], b[i + 1]); down(c[i], c[i + 1]);
        up(x[i], x[i + 1]); up(y[i], y[i + 1]); up(z[i], z[i + 1]);
    }
    y[0] = n; g[0] = 1;
    rep(i, 1, n)
    {
        static int j = 1, k = 1, l = 1;
        while(j <= n && b[j] <= a[i]) ++j;
        while(k <= n && a[k] <= c[i]) ++k;
        while(l <= n && b[l] <= c[i]) ++l;
        f[i] = j, g[i] = k, h[i] = l;
    }
    rep(i, 1, n) t1.s[i] = t1.s[i - 1] + b[i];
    uint res = 0;
    rep(i, 1, n)
    {
        Rep(j, y[i - 1], y[i] + 1)
        {
            int l = x[j] + 1, r = max(l - 1, f[j] - 1);
            t1.update(l, r, 1); t2.update(r + 1, n, a[j]);
            if(j < g[i - 1]) t3.update(l, n, a[j]); else t4.update(l, n, 1);
        }
        rep(j, g[i - 1], g[i] - 1)
        {
            int l = x[j] + 1;
            if(j > y[i]) { t3.update(l, n, a[j]), t4.update(l, n, -1); }
        }
        int l = z[i] + 1, r = max(l - 1, h[i] - 1);
        res += t1.query(l, r) + t2.query(l, r) + t3.query(r + 1, n) + t4.query(r + 1, n) * c[i];
    }
    cout << res << '\n';
    return 0;
}