题解 P4849 【寻找宝藏】
huyufeifei · · 题解
这是比赛题，附上链接，里面有官方题解。
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;
}