P3810[模板]三位偏序

Posted on Edited on In Word count in article: 479 Reading time ≈ 2 mins.
分治好题

P3810 【模板】三维偏序（陌上花开）

这道题, 刚看题时, 感觉就是把三个元素压缩成一个元素, 然后就是一个逆序对这样的一个问题 .

但是, 三个条件要求的是要同时成立, 所以, 不能这样做

既然想到逆序对了, 那么我们就可以先让其中的两维变成有序的, 剩下的一维, 就类似一个逆序对了

  • 首先对\(X\)进行排序
  • 分治, 在每个块中对\(Y\)排序
  • 对\(Z\)做逆序对, 此时\(Z\)是有限制条件的, 它依赖于\(X,Y\)的取值大小

Code

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
#include <bits/stdc++.h>
#define lowbit(x) (x & (-x))

using namespace std;

const int Maxn = 1e5 + 10;
struct Node
{
    int X, Y, Z, Ans, W;
}A[Maxn], B[Maxn];
int Cnt, Ans[Maxn << 1];
int K, N;
int Tree[Maxn << 1];

inline bool Cmpa(Node A, Node B)
{
    if (A.X == B.X) 
    {
        if (A.Y == B.Y) return A.Z < B.Z;
        return A.Y < B.Y;
    }
    return A.X < B.X;
}

inline bool Cmpy(Node A, Node B)
{
    if (A.Y == B.Y) return A.Z < B.Z;
    return A.Y < B.Y;
}

inline int Ask(int P)
{
    int Ans(0);
    while (P)
    {
        Ans += Tree[P];
        P -= lowbit(P);
    }
    return Ans;
}

inline void Add(int P, int Val)
{
    while (P <= K)
    {
        Tree[P] += Val;
        P += lowbit(P);
    }
}

inline void CDQ(int L, int R)
{
    if (L == R) return ;
    int Mid = (L + R) >> 1;
    CDQ (L, Mid), CDQ (Mid + 1, R);
    sort (A + L, A + Mid + 1, Cmpy);
    sort (A + Mid + 1, A + R + 1, Cmpy);
    int j(L);
    for (int i = Mid + 1; i <= R; ++i)
    {
        while (A[j].Y <= A[i].Y && j <= Mid)
            Add(A[j].Z, A[j].W), ++j;
        A[i].Ans += Ask(A[i].Z);
    }
    for (int i = L; i < j; ++i) Add(A[i].Z, -A[i].W);
}

int main()
{
    scanf ("%d %d", &N, &K);
    for (int i = 1; i <= N; ++i)
        scanf ("%d %d %d", &B[i].X, &B[i].Y, &B[i].Z);

    sort (B + 1, B + N + 1, Cmpa);
    for (int i = 1, C = 0; i <= N; ++i)
    {
        ++C;
        if (B[i].X != B[i + 1].X || B[i].Y != B[i + 1].Y || B[i].Z != B[i + 1].Z)
            A[++Cnt] = B[i], A[Cnt].W = C, C = 0;
    }
        

    CDQ (1, Cnt);
    for (int i = 1; i <= Cnt; ++i)
        Ans[A[i].Ans + A[i].W - 1] += A[i].W;
    
    for (int i = 0; i < N; ++i) printf ("%d\n", Ans[i]);
}

不明白为啥叫\(CDQ\), 大雾