[BZOJ3262]陌上花开 CDQ+树状数组

本文主要是介绍[BZOJ3262]陌上花开 CDQ+树状数组，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

三维的有序 第一维排序 第二维CDQ 第三维树状数组 

注意要把完全相同的两个点合在一起 他们都互相比对方美丽

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<queue>
#define SF scanf
#define PF printf
#define lowbit(x) ((x) & (-(x)))
using namespace std;
typedef long long LL;
const int MAXN = 100000;
const int MAXK = 200000;
struct Node {int a, b, c, cnt, ans;bool operator < (const Node &t) const {if(a != t.a) return a < t.a;if(b != t.b) return b < t.b;return c < t.c;}
} A[MAXN+10], tmp[MAXN+10];
bool cmp(const Node &a, const Node &b) {if(a.b != b.b) return a.b < b.b;if(a.c != b.c) return a.c < b.c;return a.a < b.a;
}
int n, K, tot, c[MAXK+10], tim[MAXK+10], T, cnt[MAXK+10];
void add(int x, int val) {for( ; x <= K; x += lowbit(x)) {if(tim[x] != T) c[x] = 0;tim[x] = T; c[x] += val;}
}
int query(int x) {int ret = 0;for( ; x; x -= lowbit(x)) if(tim[x] == T)ret += c[x];return ret;
}
void CDQ(int L, int R) {if(L == R) {A[L].ans += A[L].cnt-1;return ;}int mid = (L+R) >> 1, l1, l2;l1 = L; l2 = mid+1;for(int i = L; i <= R; i++) if(A[i].a <= mid) tmp[l1++] = A[i];else tmp[l2++] = A[i];for(int i = L; i <= R; i++) A[i] = tmp[i];CDQ(L, mid);int j = L; T++;for(int i = mid+1; i <= R; i++) {for( ; j <= mid && A[j].b <= A[i].b; j++) add(A[j].c, A[j].cnt);A[i].ans += query(A[i].c);}CDQ(mid+1, R);l1 = L; l2 = mid+1;for(int i = L; i <= R; i++) if(l1 <= mid && (l2 > R || cmp(A[l1], A[l2]))) tmp[i] = A[l1++];else tmp[i] = A[l2++];for(int i = L; i <= R; i++) A[i] = tmp[i];
}
int main() {SF("%d%d", &n, &K);for(int i = 1; i <= n; i++) SF("%d%d%d", &A[i].a, &A[i].b, &A[i].c), A[i].cnt++;sort(A+1, A+1+n);for(int i = 1; i <= n; i++) {if(i == 1 || A[i-1] < A[i]) A[++tot] = A[i];else A[tot].cnt++;}for(int i = 1; i <= tot; i++) A[i].a = i;sort(A+1, A+1+tot, cmp);CDQ(1, tot);for(int i = 1; i <= tot; i++) cnt[A[i].ans] += A[i].cnt;for(int i = 0; i < n; i++) PF("%d\n", cnt[i]);
}

这篇关于[BZOJ3262]陌上花开 CDQ+树状数组的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---