CF815D Karen and Cards 题解

题意：

有 $n$ 张卡牌，每张卡牌都有三个属性，第 $i$ 张卡牌的三个属性记作 $a_i,b_i,c_i$。卡牌 $x$ 可以打败卡牌 $y$ 当且仅当 $x$ 至少有两个属性值比 $y$ 对应的属性值大。如卡牌 $(1,2,3)$ 可以打败卡牌 $(3,1,2)$，因为 $2>1,3>2$。

现在请你判断满足 $a\leq A,b\leq B, c\leq C$ 的卡牌中，可以打败给定的所有 $n$ 张卡牌的有多少张。

数据范围：

$1 \le n,A,B,C \le 5\times 10^5$ 。

九条可怜镇楼

这里讲讲 $\mathcal{O}(n \log n)$ 的更好想的解法。（~~其实是我的思路和这个解法比较接近~~）

方便起见，记当前考察的三元组为 $(x,y,z)$ 。

首先考虑所有的 $c_i$ 相等时（设为 $c$ ）怎么做。正难则反，考虑计算不可行解的数量。

分类讨论一下 $z$ 和 $c_i$ 的大小关系：

若 $z \le c$ ，对于每个三元组
- 当 $y \in [1, b_i]$ 时，有 $x \in (A,+\infty)$ ；
- 当 $y \in (b_i, B]$ 时，有 $x \in (a_i,+\infty)$ 。
若 $z > c$ ，对于每个三元组，只需满足当 $y \in [1, b_i]$ 时 $x \in (a_i,+\infty)$ 即可。

显然对于每个 $y$ ，可选的 $x$ 取值范围的左端点是单调增的。

这个相当于区间取 max 操作，可以用吉司机线段树维护，均摊是 $\mathcal{O}(q \log n)$ 的。

现在考虑 $c_i$ 不同的情况。我们把 $c_i$ 降序排序，可以发现当 $z \in (c_i,c_{i+1}]$ 时，每个 $z$ 的贡献是一样的。

由于 $z \le c$ 的限制更为严格，所以我们先把 $z > c$ 的贡献加上，再扫一遍计算即可，详见代码。

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

代码：（~~喜提最劣解 1187ms~~）

#include <bits/stdc++.h>
using namespace std;
// #define int long long
#define INF 0x3f3f3f3f
typedef long long ll;
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 ls(at) ((at) << 1)
#define rs(at) ((at) << 1 | 1)
namespace FastIO
{
    #define gc() readchar()
    #define pc(a) putchar(a)
    #define SIZ (int)(1e6 + 15)
    char buf1[SIZ], *p1, *p2;
    char readchar()
    {
        if(p1 == p2) { p1 = buf1, p2 = buf1 + fread(buf1, 1, SIZ, stdin); }
        return p1 == p2? EOF : *p1++;
    }
    template<typename T>void read(T &k)
    {
        char ch = gc(); T x = 0, f = 1;
        while(!isdigit(ch)) { if(ch == '-') { f = -1; } ch = gc(); }
        while(isdigit(ch)) { x = (x << 1) + (x << 3) + (ch ^ 48); ch = gc(); }
        k = x * f;
    }
    template<typename A, typename ...B>
        void read(A &x, B &...y) { return read(x), read(y...); }
    template<typename T>void write(T k)
    {
        if(k < 0){ k = -k; pc('-'); }
        static T stk[66]; T top = 0;
        do{ stk[top++] = k % 10, k /= 10; } while(k);
        while(top) { pc(stk[--top] + '0'); }
    }
}using namespace FastIO;
#define N ((int)(1e6 + 15))

int n, A, B, C, sn;
struct card { int a, b, c; } a[N];
struct node { ll sum; int mn, smn, cnt, tag; } tr[N * 4];
void push_up(int at)
{
    tr[at].sum = tr[ls(at)].sum + tr[rs(at)].sum;
    if(tr[ls(at)].mn == tr[rs(at)].mn)
    {
        tr[at].mn = tr[ls(at)].mn;
        tr[at].cnt = tr[ls(at)].cnt + tr[rs(at)].cnt;
        down(tr[at].smn = tr[ls(at)].smn, tr[rs(at)].smn);
    }else
    {
        if(tr[ls(at)].mn < tr[rs(at)].mn)
        {
            tr[at].mn = tr[ls(at)].mn;
            tr[at].cnt = tr[ls(at)].cnt;
            down(tr[at].smn = tr[ls(at)].smn, tr[rs(at)].mn);
        }else
        {
            tr[at].mn = tr[rs(at)].mn;
            tr[at].cnt = tr[rs(at)].cnt;
            down(tr[at].smn = tr[ls(at)].mn, tr[rs(at)].smn);
        }
    }
}
void build(int l = 1, int r = sn, int at = 1)
{
    if(l == r) { return tr[at] = {0, 0, INF, 1, 0}, void(0); }
    int mid = (l + r) >> 1;
    build(l, mid, ls(at)); build(mid + 1, r, rs(at)); push_up(at);
}
void proc(int l, int r, int k, int at) // 区间取 max
{
    if(k <= tr[at].mn) return;
    if(k < tr[at].smn)
    {
        tr[at].sum += 1ll * (k - tr[at].mn) * tr[at].cnt;
        tr[at].mn = k; up(tr[at].cnt, 1); up(tr[at].tag, k);
        return;
    }
    int mid = (l + r) / 2;
    proc(l, mid, k, ls(at)); proc(mid + 1, r, k, rs(at)); push_up(at);
}
void push_down(int l, int r, int at)
{
    if(tr[at].tag)
    {
        int mid = (l + r) >> 1;
        proc(l, mid, tr[at].tag, ls(at));
        proc(mid + 1, r, tr[at].tag, rs(at));
        tr[at].tag = 0;
    }
}
void update(int nl, int nr, int k, int l = 1, int r = sn, int at = 1)
{
    if(nl > nr) return;
    if(nl <= l && r <= nr) { return proc(l, r, k, at), void(0); }
    int mid = (l + r) >> 1; push_down(l, r, at);
    if(nl <= mid) update(nl, nr, k, l, mid, ls(at));
    if(nr > mid) update(nl, nr, k, mid + 1, r, rs(at));
    push_up(at);
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    read(n, A, B, C); sn = B;
    rep(i, 1, n) read(a[i].a, a[i].b, a[i].c);
    sort(a + 1, a + 1 + n, [](card x, card y) { return x.c > y.c; });
    a[0] = {0, 0, C}; a[n + 1] = {0, 0, 0};
    build(); ll res = 0; 
    rep(i, 1, n) update(1, a[i].b, a[i].a);
    rep(i, 0, n)
    {
        update(1, a[i].b, A); update(a[i].b + 1, B, a[i].a);
        res += 1ll * (a[i].c - a[i + 1].c) * (1ll * A * B - tr[1].sum);
    }
    write(res); pc('\n');
    return 0;
}