题解 P3810 【【模板】三维偏序（陌上花开）】
Ireliaღ
2019-07-19 15:11:50
**树状数组套值域线段树**
## 三维偏序
看到三维偏序，最简单直接的思路就是先按照$x$把元素排序，然后按顺序把每个元素放进二维数据结构，统计二维前缀和，即为$x$、$y$、$z$都不超过该元素的元素个数。
以下为二维线段树（树套树）代码
```cpp
// luogu-judger-enable-o2
#include <iostream>
#include <algorithm>
using namespace std;
const int MAXN = 1e5 + 5;
const int MAXK = 2e5;
int n, k, cnt[MAXN];
struct Data{
int x, y, z;
int operator < (const Data &o) const {
return x != o.x ? (x < o.x) : (y != o.y ? (y < o.y) : (z < o.z));
}
int operator == (const Data &o) const {
return x == o.x && y == o.y && z == o.z;
}
}data[MAXN];
struct Seg{
struct Node{
int val;
Node *ch[2];
Node(int val = 0) : val(val) {
ch[0] = ch[1] = NULL;
}
};
Node *rt;
Seg() {
rt = NULL;
}
void Modify(Node *&now, int pos, int val = 1, int nl = 1, int nr = MAXK) {
if (!now) now = new Node();
if (nl == nr) {
now->val += val;
return;
}
int mid = nl + nr >> 1;
if (pos <= mid) Modify(now->ch[0], pos, val, nl, mid);
else Modify(now->ch[1], pos, val, mid + 1, nr);
now->val = (now->ch[0] ? now->ch[0]->val : 0) + (now->ch[1] ? now->ch[1]->val : 0);
}
int Query(Node *now, int l, int r, int nl = 1, int nr = MAXK) {
if (!now) return 0;
if (l == nl && r == nr) return now->val;
int mid = nl + nr >> 1;
if (r <= mid) return Query(now->ch[0], l, r, nl, mid);
else if (l > mid) return Query(now->ch[1], l, r, mid + 1, nr);
return Query(now->ch[0], l, mid, nl, mid) + Query(now->ch[1], mid + 1, r, mid + 1, nr);
}
};
Seg tree[MAXK * 4 + 5];
void Modify(int now, int posx, int posy, int val, int nl = 1, int nr = MAXK) {
tree[now].Modify(tree[now].rt, posy, val);
if (nl == nr) return;
int mid = nl + nr >> 1;
if (posx <= mid) Modify(now << 1, posx, posy, val, nl, mid);
else Modify(now << 1 | 1, posx, posy, val, mid + 1, nr);
}
int Query(int now, int xl, int xr, int yl, int yr, int nl = 1, int nr = MAXK) {
if (xl == nl && xr == nr) return tree[now].Query(tree[now].rt, yl, yr);
int mid = nl + nr >> 1;
if (xr <= mid) return Query(now << 1, xl, xr, yl, yr, nl, mid);
else if (nl > mid) return Query(now << 1 | 1, xl, xr, yl, yr, mid + 1, nr);
return Query(now << 1, xl, mid, yl, yr, nl, mid) + Query(now << 1 | 1, mid + 1, xr, yl, yr, mid + 1, nr);
}
int main() {
cin >> n >> k;
for (int i = 1; i <= n; i++) cin >> data[i].x >> data[i].y >> data[i].z;
sort(data + 1, data + n + 1);
int sum = 1;
for (int i = 1; i <= n; i++) {
if (data[i + 1] == data[i]) {
sum++;
continue;
}
Modify(1, data[i].y, data[i].z, sum);
int res = Query(1, 1, data[i].y, 1, data[i].z);
cnt[res] += sum;
sum = 1;
}
for (int i = 1; i <= n; i++) cout << cnt[i] << endl;
return 0;
}
```
~~你`Ctrl+C`、`Ctrl+v`交上去，发现TLE70~~
考虑到值域不大，并且线段树常数较大，可以把外层的非动态开点线段树换成树状数组，减小常数，以下为AC代码。
```cpp
// luogu-judger-enable-o2
#include <iostream>
#include <algorithm>
using namespace std;
const int MAXN = 1e5 + 5;
const int MAXK = 2e5;
int n, k, cnt[MAXN];
struct Data{
int x, y, z;
int operator < (const Data &o) const {
return x != o.x ? (x < o.x) : (y != o.y ? (y < o.y) : (z < o.z));
}
int operator == (const Data &o) const {
return x == o.x && y == o.y && z == o.z;
}
}data[MAXN];
struct Seg{
struct Node{
int val;
Node *ch[2];
Node(int val = 0) : val(val) {
ch[0] = ch[1] = NULL;
}
};
Node *rt;
Seg() {
rt = NULL;
}
void Modify(Node *&now, int pos, int val, int nl, int nr) {
if (!now) now = new Node();
if (nl == nr) {
now->val += val;
return;
}
int mid = nl + nr >> 1;
if (pos <= mid) Modify(now->ch[0], pos, val, nl, mid);
else Modify(now->ch[1], pos, val, mid + 1, nr);
now->val = (now->ch[0] ? now->ch[0]->val : 0) + (now->ch[1] ? now->ch[1]->val : 0);
}
int Query(Node *now, int l, int r, int nl, int nr) {
if (!now) return 0;
if (l == nl && r == nr) return now->val;
int mid = nl + nr >> 1;
if (r <= mid) return Query(now->ch[0], l, r, nl, mid);
else if (l > mid) return Query(now->ch[1], l, r, mid + 1, nr);
return Query(now->ch[0], l, mid, nl, mid) + Query(now->ch[1], mid + 1, r, mid + 1, nr);
}
};
/*
Seg tree[MAXK * 4 + 5];
void Modify(int now, int posx, int posy, int val, int nl = 1, int nr = MAXK) {
tree[now].Modify(tree[now].rt, posy, val);
if (nl == nr) return;
int mid = nl + nr >> 1;
if (posx <= mid) Modify(now << 1, posx, posy, val, nl, mid);
else Modify(now << 1 | 1, posx, posy, val, mid + 1, nr);
}
int Query(int now, int xl, int xr, int yl, int yr, int nl = 1, int nr = MAXK) {
if (xl == nl && xr == nr) return tree[now].Query(tree[now].rt, yl, yr);
int mid = nl + nr >> 1;
if (xr <= mid) return Query(now << 1, xl, xr, yl, yr, nl, mid);
else if (nl > mid) return Query(now << 1 | 1, xl, xr, yl, yr, mid + 1, nr);
return Query(now << 1, xl, mid, yl, yr, nl, mid) + Query(now << 1 | 1, mid + 1, xr, yl, yr, mid + 1, nr);
}
*/
Seg tree[MAXK + 5];
int LB(int x) {
return x & (-x);
}
void Modify(int posx, int posy, int val) {
for (int i = posx; i <= k; i += LB(i))
tree[i].Modify(tree[i].rt, posy, val, 1, k);
}
int Query(int x, int y) {
int ret = 0;
for (int i = x; i; i -= LB(i)) ret += tree[i].Query(tree[i].rt, 1, y, 1, k);
return ret;
}
int main() {
cin >> n >> k;
for (int i = 1; i <= n; i++) cin >> data[i].x >> data[i].y >> data[i].z;
sort(data + 1, data + n + 1);
int sum = 1;
for (int i = 1; i <= n; i++) {
if (data[i + 1] == data[i]) {
sum++;
continue;
}
Modify(data[i].y, data[i].z, sum);
int res = Query(data[i].y, data[i].z);
cnt[res] += sum;
sum = 1;
}
for (int i = 1; i <= n; i++) cout << cnt[i] << endl;
return 0;
}
```