自动搬运

查看原文

来自洛谷，原作者为

	huyufeifei **

搬运于2025-08-24 22:04:34，当前版本为作者最后更新于2018-11-22 13:47:04，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

这是比赛题，附上链接，里面有官方题解。

CDQ套CDQ裸题...
不会CDQ分治的请去陌上花开。

然后关于CDQ套CDQ，我觉得stdcall的博客写的不错。

大概就是，在第一层CDQ分治的时候，对于左边和右边进行标记，然后不进行任何操作，按照第二维排序后进入第二层CDQ分治。
在第二层里面也对左右进行标记，然后按照第三维排序，树状数组更新DP值即可。

这里要说一个CDQ分治刚学时极易写错的点：排序一定要彻底！
按照第二维排序的时候，如果二，三，四维都相同，那么要按照第一维排序。同理，按照第三维排序的时候，如果三，四维都相同，就要再按照一，二维来排序。
不这样做就会以奇怪的姿势挂掉...
比如我有两个四元组：

2 2 2 3
1 2 2 3

显然第二个是可以更新第一个的，但是如果你在按照第三维排序的时候不小心把第二个放在后面(c++ sort是不稳定的)，就凉了。

然后要记得随时取模，就没啥问题了。

CDQ分治嵌套其实可以只用一个函数完成，参考标程的实现。

为什么我写的比标程慢2倍啊......
上代码：

#include <cstdio>
#include <cstring>
#include <algorithm>

typedef long long LL;
const int N = 80010;
const LL MO = 998244353;

struct Node {
    int a, b, c, d, id;
    bool A, B; 　
    LL val, cnt, f;
    inline bool operator <(const Node &w) const {
        if(a != w.a) {
            return a < w.a;
        }
        if(b != w.b) {
            return b < w.b;
        }
        if(c != w.c) {
            return c < w.c;
        }
        return d < w.d;　
    }
    inline bool operator ==(const Node &w) const {
        return a == w.a && b == w.b && c == w.c && d == w.d;
    }
}node[N], t1[N], t2[N];

int n, X[N];
　
namespace ta {
    LL cnt[N], f[N];
    inline void add(int x, LL v, LL sum) {
        for(; x <= n; x += x & (-x)) {
            if(v > f[x]) {
                f[x] = v;
                cnt[x] = sum;
            }
            else if(v == f[x]) {
                cnt[x] += sum;
                cnt[x] %= MO;
            }
        }
        return;
    }　
    inline void ask(int x, LL &ff, LL &sum, LL val) {
        for(; x > 0; x -= x & (-x)) {
            if(f[x] + val > ff) {
                ff = f[x] + val;
                sum = cnt[x];
            }
            else if(f[x] + val == ff) {
                sum += cnt[x];
                sum %= MO;
            }
        }
        return;
    }
    inline void del(int x) {　
        for(; x <= n; x += x & (-x)) {
            cnt[x] = f[x] = 0;
        }
        return;
    }
}

inline bool cmp_c(const Node &x, const Node &y) {
    if(x.c != y.c) {
        return x.c < y.c;
    }
    if(x.d != y.d) {　
        return x.d < y.d;
    }
    if(x.a != y.a) {
        return x.a < y.a;
    }
    return x.b < y.b;
}

inline bool cmp_b(const Node &x, const Node &y) {
    if(x.b != y.b) {
        return x.b < y.b;
    }
    if(x.c != y.c) {
        return x.c < y.c;
    }　
    if(x.d != y.d) {
        return x.d < y.d;
    }
    return x.a < y.a;
}

void CDQ_2(int l, int r) {
    if(l == r) {
        return;
    }
    int mid = (l + r) >> 1;
    CDQ_2(l, mid);

    for(int i = l; i <= r; i++) {
        t1[i].B = (i > mid);
        t2[i] = t1[i];
        t2[i].id = i;
    }　
    std::sort(t2 + l, t2 + r + 1, cmp_c);

    for(int i = l; i <= r; i++) {
        if(t2[i].A && t2[i].B) {
            ta::ask(t2[i].d, t2[i].f, t2[i].cnt, t2[i].val);
            t1[t2[i].id].f = t2[i].f;
            t1[t2[i].id].cnt = t2[i].cnt;
        }
        if(!t2[i].A && !t2[i].B) {
            ta::add(t2[i].d, t2[i].f, t2[i].cnt);
        }
    }　

    for(int i = l; i <= mid; i++) {
        if(!t1[i].A) {
            ta::del(t1[i].d);
        }
    }
    CDQ_2(mid + 1, r);
    return;
}

void CDQ_1(int l, int r) {
    if(l == r) {
        return;
    }
　
    int mid = (l + r) >> 1;
    CDQ_1(l, mid);

    for(int i = l; i <= r; i++) {
        node[i].A = (i > mid);
        t1[i] = node[i];
        t1[i].id = i;
    }
    std::sort(t1 + l, t1 + r + 1, cmp_b);
    CDQ_2(l, r);
    for(int i = l; i <= r; i++) {
        node[t1[i].id].f = t1[i].f;　
        node[t1[i].id].cnt = t1[i].cnt;
    }

    CDQ_1(mid + 1, r);
    return;
}

int main() {

    int m;
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i++) {
        scanf("%d%d%d%d%lld", &node[i].a, &node[i].b, &node[i].c, &node[i].d, &node[i].val);
    }
    std::sort(node + 1, node + n + 1);　
    int temp = 1;
    for(int i = 2; i <= n; i++) { /// unique
        if(node[i] == node[temp]) {
            node[temp].val += node[i].val;
        }
        else {
            node[++temp] = node[i];
        }
    }
    n = temp;

    for(int i = 1; i <= n; i++) {
        X[i] = node[i].a;
    }
    std::sort(X + 1, X + n + 1);
    temp = std::unique(X + 1, X + n + 1) - X - 1;
    for(int i = 1; i <= n; i++) {　
        node[i].a = std::lower_bound(X + 1, X + temp + 1, node[i].a) - X;
    }

    for(int i = 1; i <= n; i++) {
        X[i] = node[i].b;
    }
    std::sort(X + 1, X + n + 1);
    temp = std::unique(X + 1, X + n + 1) - X - 1;
    for(int i = 1; i <= n; i++) {
        node[i].b = std::lower_bound(X + 1, X + temp + 1, node[i].b) - X;
    }

    for(int i = 1; i <= n; i++) {
        X[i] = node[i].c;
    }　
    std::sort(X + 1, X + n + 1);
    temp = std::unique(X + 1, X + n + 1) - X - 1;
    for(int i = 1; i <= n; i++) {
        node[i].c = std::lower_bound(X + 1, X + temp + 1, node[i].c) - X;
    }

    for(int i = 1; i <= n; i++) {
        X[i] = node[i].d;
    }
    std::sort(X + 1, X + n + 1);
    temp = std::unique(X + 1, X + n + 1) - X - 1;
    for(int i = 1; i <= n; i++) {　
        node[i].d = std::lower_bound(X + 1, X + temp + 1, node[i].d) - X;
    }

    for(int i = 1; i <= n; i++) {
        node[i].f = node[i].val;
        node[i].cnt = 1;
        node[i].id = i;
    }

    // prework OVER

    CDQ_1(1, n);　

    LL sum = 0, ans = 0;
    for(int i = 1; i <= n; i++) {
        if(node[i].f > ans) {
            ans = node[i].f;
            sum = node[i].cnt;
        }
        else if(node[i].f == ans) {
            sum += node[i].cnt;
            sum %= MO;
        }
    }
    
    printf("%lld\n%lld\n", ans, sum);　

    return 0;
}