欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

洛谷P3810 陌上花开(CDQ分治)

程序员文章站 2022-05-14 18:42:03
...

洛谷P3810 陌上花开

传送门

题解:

CDQ分治模板题。
一维排序,二维归并,三维树状数组。
核心思想是分治,即计算左边区间对右边区间的影响。
代码如下:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 200005;
int n, k, m;
struct node{
    int x, y, z, id, w;
    bool operator < (const node &A)const{
        if(A.x == x && A.y == y) return z < A.z;
        else if(A.x == x) return y < A.y;
        return x < A.x;
    }
}a[N], b[N], d[N];
int ans[N], c[N], cnt[N];
vector <int> v1, v2[N] ;
int lowbit(int x) {
    return x& (-x);
}
void add(int x, int v) {
    for(int i = x; i < N; i += lowbit(i)) c[i] += v;
}
int query(int x) {
    int ans = 0;
    for(int i = x; i; i -= lowbit(i)) ans += c[i];
    return ans;
}
void cdq(int l, int r) {
    if(l == r) return ;
    int mid = (l + r) >> 1;
    cdq(l, mid), cdq(mid + 1, r) ;
    int t1 = l, t2 = mid + 1;
    for(int i = l; i <= r; i++) {
        if((t1 <= mid && a[t1].y <= a[t2].y) || t2 > r) {
            add(a[t1].z, a[t1].w);
            b[i] = a[t1++];
        } else {
            cnt[a[t2].id] += query(a[t2].z);
            b[i] = a[t2++];
        }
    }
    for(int i = l; i <= mid; i++) add(a[i].z, -a[i].w);
    for(int i = l; i <= r; i++) a[i] = b[i];
}
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    cin >> n >> k;
    for(int i = 1; i <= n; i++) {
        cin >> a[i].x >> a[i].y >> a[i].z;
        a[i].id = i;
    }
    sort(a + 1, a + n + 1);
    int num = 1;
    for(int i = 2; i <= n + 1; i++) {
        if(a[i].x != a[i - 1].x || a[i].y != a[i - 1].y || a[i].z != a[i - 1].z) {
            d[++m] = a[i - 1];
            d[m].w = num;
            num = 1;
            v2[a[i - 1].id] = v1;
            v1.clear();
        } else {
            num++;
            v1.push_back(a[i - 1].id) ;
        }
    }
    for(int i = 1; i <= m; i++) a[i] = d[i];
    cdq(1, m);
    for(int i = 1; i <= m; i++) {
        int sz = v2[a[i].id].size();
        for(auto v : v2[a[i].id]) cnt[v] += cnt[a[i].id] + sz;
        cnt[a[i].id] += sz;
    }
    for(int i = 1; i <= n; i++) ans[cnt[i]]++;
    for(int i = 0; i < n; i++) cout << ans[i] << '\n';
    return 0;
}
/*
3 4
1 2 3
1 2 3
2 1 3
*/