洛谷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;
}