HDU5618 Jam's problem again CDQ分治

Jam's problem again CDQ分治

传送门：http://acm.hdu.edu.cn/showproblem.php?pid=5618

题意：

[有n 个元素，第 i 个元素有 a_i、 b_i、 c_i 三个属性，设 f(i) 表示满足 a_ileq a_j 且 b_i leq b_j且 c_i leq c_j的 j 的数量。\ 对于 d in [0, n]，求 f(i) = d 的数量 ]

题解：

和陌上花开这个题是一样的实际上

就不写详细过程了，思想是一样的

详情看这个吧

https://www.cnblogs.com/buerdepepeqi/p/11182571.html

代码：

#include <set>
#include <map>
#include <deque>
#include <queue>
#include <stack>
#include <cmath>
#include <ctime>
#include <bitset>
#include <cstdio>
#include <string>
#include <vector>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

typedef long long LL;
typedef long long ll;
typedef pair<LL, LL> pLL;
typedef pair<LL, int> pLi;
typedef pair<int, LL> pil;;
typedef pair<int, int> pii;
typedef unsigned long long uLL;
#define ls rt<<1
#define rs rt<<1|1
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define bug printf("*********
")
#define FIN freopen("input.txt","r",stdin);
#define FON freopen("output.txt","w+",stdout);
#define IO ios::sync_with_stdio(false),cin.tie(0)
#define debug1(x) cout<<"["<<#x<<" "<<(x)<<"]
"
#define debug2(x,y) cout<<"["<<#x<<" "<<(x)<<" "<<#y<<" "<<(y)<<"]
"
#define debug3(x,y,z) cout<<"["<<#x<<" "<<(x)<<" "<<#y<<" "<<(y)<<" "<<#z<<" "<<z<<"]
"

const double eps = 1e-8;
const int mod = 1e9 + 7;
const int maxn = 3e5 + 5;
const int INF = 0x3f3f3f3f;
const LL INFLL = 0x3f3f3f3f3f3f3f3f;
struct EDGE {
    int v, nxt;
} edge[maxn << 1];
int head[maxn], tot;
void add_edge(int u, int v) {
    edge[tot].v = v, edge[tot].nxt = head[u], head[u] = tot++;
}
LL bit[maxn];
int lowbit(int x) {
    return x & (-x);
}
void add(int pos, int val) {
    while(pos < maxn) {
        bit[pos] += val, pos += lowbit(pos);
    }
}
int sum(int pos) {
    int ans = 0;
    while(pos) {
        ans += bit[pos], pos -= lowbit(pos);
    } return ans;
}
struct node {
    int x, y, z;
    int ans;
    int id;
} t[maxn], a[maxn], b[maxn];
bool cmp1(node a, node b) {
    if(a.x == b.x && a.y == b.y) return a.z < b.z;
    if(a.x == b.x) return a.y < b.y;
    return a.x < b.x;
}
bool cmp2(node a, node b) {
    if(a.y == b.y && a.z == b.z) return a.x < b.x;
    if(a.y == b.y) return a.z < b.z;
    return a.y < b.y;
}

int ans[maxn];
int num[maxn];
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, cmp2);
    sort(a + mid + 1, a + r + 1, cmp2);
    int j = l;
    for(int i = mid + 1; i <= r; ++i) {
        while(j <= mid && a[j].y <= a[i].y) {
            add(a[j].z, 1), ++j;
        }
        a[i].ans += sum(a[i].z);
    }
    for(j--; j >= l; j--) add(a[j].z, -1);

}

int main() {
#ifndef ONLINE_JUDGE
    FIN
#endif
    int T;
    scanf("%d", &T);
    while(T--) {
        int n, k;
        scanf("%d", &n);
        for(int i = 1; i <= n; i++) {
            scanf("%d%d%d", &a[i].x, &a[i].y, &a[i].z);
            a[i].id = i;
            a[i].ans = 0;
        }
        sort(a + 1, a + n + 1, cmp1);
        CDQ(1, n);

        for(int i = 1; i <= n;) {
            int j = i + 1;
            int tmp = a[i].ans;
            for(; j <= n && a[i].x == a[j].x && a[i].y == a[j].y && a[i].z == a[j].z; j++) tmp = max(tmp, a[j].ans);
            for(int k = i; k < j; k++) ans[a[k].id] = tmp;
            i = j;
        }
        for(int i = 1; i <= n; i++) printf("%d
", ans[i]);
    }

    return 0;
}