【题解】-洛谷-3810-BZOJ-3262 三维偏序（陌上花开）

Posted on Edited on In Disqus:

题目

https://www.luogu.org/problemnew/show/P3810

题意

对于每个元素，求对应三围都不大于它的元素个数。

题解

树套树

  • 简单粗暴。
  • 空间复杂度多了一个 log，而且常数会比较大。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#define FOR(i, x, y) for (decay<decltype(y)>::type i = (x), _##i = (y); i < _##i; ++i)
#define FORD(i, x, y) for (decay<decltype(x)>::type i = (x), _##i = (y); i > _##i; --i)
#ifdef zerol
#define dbg(args...) do { cout << "\033[32;1m" << #args << " -> "; err(args); } while (0)
#else
#define dbg(...)
#endif
void err() { cout << "\033[39;0m" << endl; }
template<template<typename...> class T, typename t, typename... Args>
void err(T<t> a, Args... args) { for (auto x: a) cout << x << ' '; err(args...); }
template<typename T, typename... Args>
void err(T a, Args... args) { cout << a << ' '; err(args...); }
// -----------------------------------------------------------------------------
const int maxn = 1E5 + 100, maxk = 2E5 + 100;
int n, k;
struct Q {
    int a, b, c;
};
Q a[maxn];
int ans[maxn];

unsigned rnd() {
    static unsigned A = 1 << 16 | 3, B = 33333331, C = 2341;
    return C = A * C + B;
}

namespace treap {
    const int M = maxn * 17;
    extern struct P* const null;
    struct P {
        P *ls, *rs;
        int v, sz;
        unsigned rd;
        P(int v): ls(null), rs(null), v(v), sz(1), rd(rnd()) {}
        P(): sz(0) {}

        P* up() { sz = ls->sz + rs->sz + 1; return this; }
        int lower(int v) {
            if (this == null) return 0;
            return this->v >= v ? ls->lower(v) : rs->lower(v) + ls->sz + 1;
        }
        int upper(int v) {
            if (this == null) return 0;
            return this->v > v ? ls->upper(v) : rs->upper(v) + ls->sz + 1;
        }
    } *const null = new P, pool[M], *pit = pool;

    P* merge(P* l, P* r) {
        if (l == null) return r; if (r == null) return l;
        if (l->rd < r->rd) { l->rs = merge(l->rs, r); return l->up(); }
        else { r->ls = merge(l, r->ls); return r->up(); }
    }

    void split(P* o, int rk, P*& l, P*& r) {
        if (o == null) { l = r = null; return; }
        if (o->ls->sz >= rk) { split(o->ls, rk, l, o->ls); r = o->up(); }
        else { split(o->rs, rk - o->ls->sz - 1, o->rs, r); l = o->up(); }
    }
}

namespace bit {
    using namespace treap;
    P* c[maxk];
    void init() { FOR (i, 1, k + 1) c[i] = null; }
    inline int lowbit(int x) { return x & -x; }
    void ins(int p, int v) {
        for (int i = p; i <= k; i += lowbit(i)) {
            P *l, *r; split(c[i], c[i]->lower(v), l, r);
            c[i] = merge(l, merge(new (pit++) P{v}, r));
        }
    }
    int query(int p, int v) {
        int ret = 0;
        for (int i = p; i > 0; i -= lowbit(i))
            ret += c[i]->upper(v);
        return ret;
    }
}

int main() {
    cin >> n >> k;
    FOR (i, 0, n) scanf("%d%d%d", &a[i].a, &a[i].b, &a[i].c);
    sort(a, a + n, [](const Q& a, const Q& b)->bool{
            if (a.a != b.a) return a.a < b.a;
            if (a.b != b.b) return a.b < b.b;
            return a.c  < b.c;
    });
    bit::init();
    int s = 0;
    FOR (i, 0, n) {
        ++s;
        if (i == n - 1 || a[i].a != a[i + 1].a || a[i].b != a[i + 1].b || a[i].c != a[i + 1].c) {
            ans[bit::query(a[i].b, a[i].c)] += s;
            s = 0;
        }
        bit::ins(a[i].b, a[i].c);
    }
    FOR (i, 0, n) printf("%d\n", ans[i]);
}

一层 cdq 分治 + 树状数组

  • 正如大家所说，cdq 在分治的基础上需要累计前一半对后一半的贡献。
  • 由于完全一样的元素，只有最后的那一个会被正确计数，所以采用 STL 中的稳定排序 stable_sort 。但事实上并不需要在分治内部排序，因为可以归并，而且归并是稳定的。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#define FOR(i, x, y) for (decay<decltype(y)>::type i = (x), _##i = (y); i < _##i; ++i)
#define FORD(i, x, y) for (decay<decltype(x)>::type i = (x), _##i = (y); i > _##i; --i)
#ifdef zerol
#define dbg(args...) do { cout << "\033[32;1m" << #args << " -> "; err(args); } while (0)
#else
#define dbg(...)
#endif
void err() { cout << "\033[39;0m" << endl; }
template<template<typename...> class T, typename t, typename... Args>
void err(T<t> a, Args... args) { for (auto x: a) cout << x << ' '; err(args...); }
template<typename T, typename... Args>
void err(T a, Args... args) { cout << a << ' '; err(args...); }
// -----------------------------------------------------------------------------
const int maxn = 1E5 + 100, maxk = 2E5 + 100;
int n, k;
struct P {
    int x, y, z, c;
} a[maxn];
auto cmpy = [](const P& a, const P& b)->bool {
    if (a.y != b.y) return a.y < b.y;
    return a.z < b.z;
};
auto cmpx = [](const P& a, const P& b)->bool {
    if (a.x != b.x) return a.x < b.x;
    return cmpy(a, b);
};
bool operator == (const P& a, const P& b) {
    return !cmpx(a, b) && !cmpx(b, a);
}
namespace bit {
    int c[maxk];
    inline int lowbit(int x) { return x & -x; }
    void add(int x, int v) {
        for (int i = x; i <= k; i += lowbit(i))
            c[i] += v;
    }
    int sum(int x) {
        int ret = 0;
        for (int i = x; i > 0; i -= lowbit(i))
            ret += c[i];
        return ret;
    }
}
void go(int l, int r) {
    if (l == r) return;
    int m = (l + r) / 2;
    go(l, m); go(m + 1, r);
    stable_sort(a + l, a + m + 1, cmpy);
    stable_sort(a + m + 1, a + r + 1, cmpy);
    int qr = m + 1, ql = l;
    while (qr <= r) {
        while (ql <= m && a[ql].y <= a[qr].y)
            bit::add(a[ql++].z, 1);
        a[qr].c += bit::sum(a[qr].z);
        qr++;
    }
    FOR (i, l, ql) bit::add(a[i].z, -1);
}

int ans[maxn];
int main() {
    cin >> n >> k;
    FOR (i, 0, n) scanf("%d%d%d", &a[i].x, &a[i].y, &a[i].z);
    sort(a, a + n, cmpx);
    go(0, n - 1);
    stable_sort(a, a + n, cmpx);
    FORD (i, n - 1, -1) {
        if (i < n - 1 && a[i] == a[i + 1]) a[i].c = a[i + 1].c;
        ans[a[i].c]++;
    }
    FOR (i, 0, n) printf("%d\n", ans[i]);
}

两层 cdq 分治

  • STL 中的 merge 在两个迭代器中的值相等的情况下会优先选择前一个。
  • 写成左闭右开果然舒服多了。
  • 如果写成间接排序的话可以进一步减少常数。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#define FOR(i, x, y) for (decay<decltype(y)>::type i = (x), _##i = (y); i < _##i; ++i)
#define FORD(i, x, y) for (decay<decltype(x)>::type i = (x), _##i = (y); i > _##i; --i)
#ifdef zerol
#define dbg(args...) do { cout << "\033[32;1m" << #args << " -> "; err(args); } while (0)
#else
#define dbg(...)
#endif
void err() { cout << "\033[39;0m" << endl; }
template<template<typename...> class T, typename t, typename... Args>
void err(T<t> a, Args... args) { for (auto x: a) cout << x << ' '; err(args...); }
template<typename T, typename... Args>
void err(T a, Args... args) { cout << a << ' '; err(args...); }
// -----------------------------------------------------------------------------
const int maxn = 1E5 + 100, maxk = 2E5 + 100;
struct P {
    int x, y, z;
    int* ans;
    bool d1, d2;
} a[maxn], b[maxn], c[maxn];

void go2(int l, int r) { // [l, r)
    if (l + 1 == r) return;
    int m = (l + r) / 2;
    go2(l, m); go2(m, r);
    FOR (i, l, m) b[i].d2 = 0;
    FOR (i, m, r) b[i].d2 = 1;
    merge(b + l, b + m, b + m, b + r, c + l, [](const P& a, const P& b)->bool { return a.z < b.z; });
    int s = 0;
    FOR (i, l, r) {
        if (c[i].d1 && c[i].d2) *c[i].ans += s;
        s += !c[i].d1 && !c[i].d2;
    }
    FOR (i, l, r) b[i] = c[i];
}

void go1(int l, int r) { // [l, r)
    if (l + 1 == r) return;
    int m = (l + r) / 2;
    go1(l, m); go1(m, r);
    FOR (i, l, m) a[i].d1 = 0;
    FOR (i, m, r) a[i].d1 = 1;
    merge(a + l, a + m, a + m, a + r, b + l, [](const P& a, const P& b)->bool { return a.y < b.y; });
    FOR (i, l, r) a[i] = b[i];
    go2(l, r);
}

int ans[maxn], cnt[maxn];
int n, k;
int main() {
    cin >> n >> k;
    FOR (i, 0, n) scanf("%d%d%d", &a[i].x, &a[i].y, &a[i].z);
    sort(a, a + n, [](const P& a, const P& b)->bool {
            if (a.x != b.x) return a.x < b.x;
            if (a.y != b.y) return a.y < b.y;
            return a.z < b.z;
        });
    FOR (i, 0, n) a[i].ans = &ans[i];
    FORD (i, n - 2, -1)
        if (a[i].x == a[i + 1].x && a[i].y == a[i + 1].y && a[i].z == a[i + 1].z) ans[i] = ans[i + 1] + 1;
    go1(0, n);
    FOR (i, 0, n) cnt[ans[i]]++;
    FOR (i, 0, n) printf("%d\n", cnt[i]);
}