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_i\leq 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("*********\n")

#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)<<"]\n"

#define debug2(x,y) cout<<"["<<#x<<" "<<(x)<<" "<<#y<<" "<<(y)<<"]\n"

#define debug3(x,y,z) cout<<"["<<#x<<" "<<(x)<<" "<<#y<<" "<<(y)<<" "<<#z<<" "<<z<<"]\n"

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\n", ans[i]);

    }

    return 0;

}