Catshao

用户名：Catshao

访问量：29119

签　名：

stO KHIN Orz

等　　级
排　　名	159
经　　验	7166
参赛次数	6
文章发表	46
年　　龄	12
在职情况	学生
学　　校	双语
专　　业

　　自我简介：

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题8.7 （Java代码）

三维偏序（CDQ分治的代码）

　　作者: Catshao　　　　发表时间：2022-02-19 13:36:49 浏览：203　|　评论：0　

原题链接：三维偏序

[TOC]

### 吐槽下这道题（瞎讲）

卡常。
如果你 TLE 了请加这么两个优化：

1.手动 Ofast

```cpp
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
```

2.如果你使用了 cin/cout，可以关闭同步：

```cpp
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
```

把 `cout << endl` 换成 `cout << '\n'` 就可以卡过去了。原因是 `cout << endl` 会输出换行的同时刷新缓冲区。

-----------------

以上都是奇淫技巧，这道题如果常数大还可以用离散化。

离散化 4 次，先分别离散化 $$a, b, c$$ ，再去掉位置重合的点（同时记录下一个位置的点有多少个，用于统计）。

这样值域就从 $$2 \times 10^5$$ 变成了 $$10^5$$ ，会更快。

注意位置相同的点也会有贡献。

------------------

树状数组是个好东西，能用树状数组就用树状数组，与线段树想必树状数组常数会小一点。（尤其树套树）

```cpp
//
// Created by Cat-shao on 2022/2/19.
//

#include <bits/stdc++.h>
using namespace std;

const int MAX_N = 100100;
typedef tuple<int, int, int, int> TI4;

int n, hx[MAX_N], hy[MAX_N], hz[MAX_N], kx, ky, kz, ka, ans[MAX_N], d[MAX_N], cnt[MAX_N];
TI4 a[MAX_N], temp[MAX_N];

inline int lowbit(int x) {
    return x & -x;
}

class BIT {
public:
    int node[MAX_N], n;

BIT(int _n) {
        memset(node, 0, sizeof(node));
        n = _n;
    }

int sum(int index) {
        int sum = 0;
        while (index > 0) {
            sum += node[index];
            index -= lowbit(index);
        }
        return sum;
    }

void add(int index, int value) {
        while (index <= n) {
            node[index] += value;
            index += lowbit(index);
        }
    }
};

void solve(int l, int r) {
    if (l + 1 >= r) {
        return;
    }
    int mid = (l + r) >> 1;
    solve(l, mid);
    solve(mid, r);
    static BIT tree(kz);
    int i, j, k;
    for (i = l, j = mid; j < r; ++j) {
        while (get<1>(a[i]) <= get<1>(a[j]) && i < mid) {
            tree.add(get<2>(a[i]), cnt[get<3>(a[i])]);
            i++;
        }
        ans[get<3>(a[j])] += tree.sum(get<2>(a[j]));
    }
    while (--i >= l) {
        tree.add(get<2>(a[i]), -cnt[get<3>(a[i])]);
    }
    for (i = l, j = mid, k = l; i < mid || j < r; temp[k++] = i >= mid ? a[j++] : (j >= r ? a[i++] : (get<1>(a[i]) <= get<1>(a[j]) ? a[i++] : a[j++])));
    memcpy(a + l, temp + l, (r - l) * sizeof(TI4));
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> ka; // 实际上这个输入的 ka 啥用都没有
    int x, y, z;
    for (int i = 1; i <= n; ++i) {
        cin >> x >> y >> z;
        a[i] = TI4(x, y, z, 0);
        hx[i] = x;
        hy[i] = y;
        hz[i] = z;
    }
    sort(hx + 1, hx + n + 1);
    sort(hy + 1, hy + n + 1);
    sort(hz + 1, hz + n + 1);
    kx = unique(hx + 1, hx + n + 1) - (hx + 1);
    ky = unique(hy + 1, hy + n + 1) - (hy + 1);
    kz = unique(hz + 1, hz + n + 1) - (hz + 1);
    for (int i = 1; i <= n; ++i) {
        get<0>(a[i]) = lower_bound(hx + 1, hx + kx + 1, get<0>(a[i])) - hx;
        get<1>(a[i]) = lower_bound(hy + 1, hy + ky + 1, get<1>(a[i])) - hy;
        get<2>(a[i]) = lower_bound(hz + 1, hz + kz + 1, get<2>(a[i])) - hz;
    }
    sort(a + 1, a + n + 1);
    ka = 0;
    for (int i = 1; i <= n; ++i) {
        if (i == 1 || a[i] != a[i - 1]) {
            a[++ka] = a[i];
        }
        cnt[ka]++;
    }
    for (int i = 1; i <= ka; ++i) {
        get<3>(a[i]) = i;
    }
    // 以上全是离散化
    solve(1, ka + 1);
    for (int i = 1; i <= ka; ++i) {
        d[(long long) ans[i] + cnt[i] - 1] += cnt[i];
    }
    for (int i = 0; i < n; ++i) {
        cout << d[i] << '\n';
    }
    return 0;
}
```

0.0分

0 人评分

新上线《蓝桥杯辅导》课程，近五年的蓝桥杯省赛与国赛真题都有，从读题开始理解题意、梳理思路、实现代码再提交评测全过程，可有效提升获奖比例甚至进国赛！课程介绍、试听请猛击这里

Catshao

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题8.7 （Java代码）

C语言程序设计教程（第三版）课后习题6.6 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

C语言程序设计教程（第三版）课后习题6.9 （C++代码）

三维偏序（CDQ分治的代码）

评论区

精彩推荐

点我有惊喜！你懂得！

C语言程序设计教程（第三版）课后习题7.2 （C语言代码）

奖学金（C++代码）

C语言训练-计算1977！* （C++代码）

回文数(一) （C语言代码）

C语言程序设计教程（第三版）课后习题5.5 （C语言代码）

C语言程序设计教程（第三版）课后习题5.4 （C语言代码）

本人酷爱递归实现很多问题，这里也是

三角形（C++代码）记忆化搜索

图形输出（C语言代码）

Catshao

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题8.7 （Java代码）

C语言程序设计教程（第三版）课后习题6.6 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

C语言程序设计教程（第三版）课后习题6.9 （C++代码）

三维偏序（CDQ分治的代码）

评论区

精彩推荐

点我有惊喜！你懂得！

C语言程序设计教程（第三版）课后习题7.2 （C语言代码）

奖学金 （C++代码）

C语言训练-计算1977！* （C++代码）

回文数(一) （C语言代码）

C语言程序设计教程（第三版）课后习题5.5 （C语言代码）

C语言程序设计教程（第三版）课后习题5.4 （C语言代码）

本人酷爱递归实现很多问题，这里也是

三角形 （C++代码）记忆化搜索

图形输出 （C语言代码）

　　评论区

奖学金（C++代码）

三角形（C++代码）记忆化搜索

图形输出（C语言代码）