[BZOJ3262]陌上花开
试题描述
有n朵花，每朵花有三个属性：花形(s)、颜色(c)、气味(m)，又三个整数表示。现要对每朵花评级，一朵花的级别是它拥有的美丽能超过的花的数量。定义一朵花A比另一朵花B要美丽，当且仅当Sa>=Sb,Ca>=Cb,Ma>=Mb。显然，两朵花可能有同样的属性。需要统计出评出每个等级的花的数量。
输入
第一行为N,K (1 <= N <= 100,000, 1 <= K <= 200,000 ), 分别表示花的数量和最大属性值。
以下N行，每行三个整数si, ci, mi (1 <= si, ci, mi <= K)，表示第i朵花的属性
输出
包含N行，分别表示评级为0...N-1的每级花的数量。
输入示例
10 33 3 32 3 32 3 13 1 13 1 21 3 11 1 21 2 21 3 21 2 1
输出示例
3130101001
数据规模及约定
1 <= N <= 100,000, 1 <= K <= 200,000
题解
三维问题，第一维排序，第二维树状数组，第三维平衡树。然后慢得飞起。。。以后再用 kd 树切一切试试。。。哦对了这题有坑，需要判一判重合点的情况。
#include#include #include #include #include #include using namespace std;int read() { int x = 0, f = 1; char c = getchar(); while(!isdigit(c)){ if(c == '-') f = -1; c = getchar(); } while(isdigit(c)){ x = x * 10 + c - '0'; c = getchar(); } return x * f;}#define maxn 200010#define maxnode 3600010struct Node { int v, r, siz; Node() {} Node(int _, int __): v(_), r(__) {}} ns[maxnode];int ToT, fa[maxnode], ch[2][maxnode];void maintain(int o) { ns[o].siz = 1; for(int i = 0; i < 2; i++) if(ch[i][o]) ns[o].siz += ns[ch[i][o]].siz; return ;}void rotate(int u) { int y = fa[u], z = fa[y], l = 0, r = 1; if(z) ch[ch[1][z]==y][z] = u; if(ch[1][y] == u) swap(l, r); fa[u] = z; fa[y] = u; fa[ch[r][u]] = y; ch[l][y] = ch[r][u]; ch[r][u] = y; maintain(y); maintain(u); return ;}void insert(int& o, int v) { if(!o) { ns[o = ++ToT] = Node(v, rand()); return maintain(o); } bool d = v > ns[o].v; insert(ch[d][o], v); fa[ch[d][o]] = o; if(ns[ch[d][o]].r > ns[o].r) { int t = ch[d][o]; rotate(t); o = t; } return maintain(o);}int que(int& o, int v) { if(!o) return 0; int ls = ch[0][o] ? ns[ch[0][o]].siz : 0; if(v >= ns[o].v) return ls + 1 + que(ch[1][o], v); return que(ch[0][o], v);}int K, rt[maxn];void add(int x, int y) { for(; x <= K; x += x & -x) insert(rt[x], y); return ;}int query(int x, int y) { int sum = 0; for(; x; x -= x & -x) sum += que(rt[x], y); return sum;}struct Flw { int x, y, z; Flw() {} Flw(int _1, int _2, int _3): x(_1), y(_2), z(_3) {} bool operator < (const Flw& t) const { if(x != t.x) return x < t.x; if(y != t.y) return y < t.y; return z < t.z; }} fs[maxn];int ans[maxn];int main() { int n = read(); K = read(); for(int i = 1; i <= n; i++) { int x = read(), y = read(), z = read(); fs[i] = Flw(x, y, z); } sort(fs + 1, fs + n + 1); int tmp = 1; for(int i = 1; i <= n; i++) { if(i == n || fs[i].x != fs[i+1].x || fs[i].y != fs[i+1].y || fs[i].z != fs[i+1].z) { ans[query(fs[i].y,fs[i].z)] += tmp; tmp = 1; } else tmp++; add(fs[i].y, fs[i].z); } for(int i = 0; i < n; i++) printf("%d\n", ans[i]); return 0;}