题目链接
思路
对一维排序后, 使用 $cdq$ 分治, 以类似归并排序的方法处理的二维, 对于满足 $a[i].b \leq a[j].b$ 的点对, 用树状数组维护 $a[i].c$ 的数量. 当遇到 $a[i].b>a[j].b$ 时可以更新 $j$ 的答案, 因为前半部分中剩余的点的第二维必然大于 $j$ 点的第二维 (记住我们是对第二维进行归并排序所以第二维是有序的, 因此有这样的判断). 每次要记得初始化树状数组.
代码
- #include <bits/stdc++.h>
- #define DBG(x) cerr <<#x << "=" << x << endl
- using namespace std;
- typedef long long LL;
- const int N = 1e5 + 5;
- int n, k;
- LL ans[N];
- struct node {
- int x, y, z, w, f;
- bool operator < (const node &a) const {
- if(x != a.x) return x < a.x;
- if(y != a.y) return y < a.y;
- return z < a.z;
- }
- } a[N], b[N];
- struct BIT {
- static const int M = 2e5 + 5;
- int c[M];
- int lowbit(int x) {return (x & (-(x)));}
- void update(int x, int y) {
- while(x < M) {
- c[x] += y;
- x += lowbit(x);
- }
- }
- int query(int x) {
- int res = 0;
- while(x) {
- res += c[x];
- x -= lowbit(x);
- }
- return res;
- }
- } tree;
- void solve(int L, int R) {
- if(L == R) return;
- int Mid = (L + R) / 2;
- solve(L, Mid); solve(Mid + 1, R);
- int t1 = L, t2 = Mid + 1, tot = L;
- for(int i = L; i <= R; i++) {
- if((t1 <= Mid && a[t1].y <= a[t2].y) || t2> R) tree.update(a[t1].z, a[t1].w), b[tot++] = a[t1++];
- else a[t2].f += tree.query(a[t2].z), b[tot++] = a[t2++];
- }
- for(int i = L; i <= Mid; i++) tree.update(a[i].z, -a[i].w);
- for(int i = L; i <= R; i++) a[i] = b[i];
- }
- int main() {
- scanf("%d%d", &n, &k);
- for(int i = 1; i <= n; i++) scanf("%d%d%d", &a[i].x, &a[i].y, &a[i].z), a[i].w = 1;
- sort(a + 1, a + 1 + n);
- int cnt = 1;
- for(int i = 2; i <= n; i++) {
- if(a[i].x == a[cnt].x && a[i].y == a[cnt].y && a[i].z == a[cnt].z) a[cnt].w++;
- else a[++cnt] = a[i];
- }
- solve(1, cnt);
- for(int i = 1; i <= cnt; i++) ans[a[i].w + a[i].f - 1] += 1LL * a[i].w;
- for(int i = 0; i < n; i++) printf("%lld\n", ans[i]);
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3023865.html