题目描述
有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的每级花的数量。
题目解析
伟大的CDQ,您真是我们的红太阳!
再一次被CDQ分治的力量所折服。本题是裸的三维数点问题,类比于二维数点,我们用降维的思想来做。先去重,第一维直接排序,后两维套用CDQ分治,用树状数组维护即可。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 |
/************************************************************** Problem: 3262 User: frank_c1 Language: C++ Result: Accepted Time:3184 ms Memory:5964 kb ****************************************************************/ #include <set> #include <map> #include <queue> #include <ctime> #include <cmath> #include <cstdio> #include <vector> #include <string> #include <cctype> #include <bitset> #include <cstring> #include <cstdlib> #include <utility> #include <iostream> #include <algorithm> #define REP(i,a,b) for(int i=(a);i<=(b);i++) #define PER(i,a,b) for(int i=(a);i>=(b);i--) #define RVC(i,S) for(int i=0;i<(S).size();i++) #define RAL(i,u) for(int i=fr[u];i!=-1;i=e[i].next) using namespace std; typedef long long LL; typedef pair<int,int> pii; template<class T> inline void read(T& num) { bool start=false,neg=false; char c; num=0; while((c=getchar())!=EOF) { if(c=='-') start=neg=true; else if(c>='0' && c<='9') { start=true; num=num*10+c-'0'; } else if(start) break; } if(neg) num=-num; } /*============ Header Template ============*/ #define lowbit(x) (x)&(-x) struct node { int a,b,c,siz,ans; bool operator == (const node& t) const { if(a==t.a && b==t.b && c==t.c) return true; else return false; } bool operator != (const node& t) const {return !(*this==t);} }; bool cmpa(node s,node t) { if(s.a!=t.a) return s.a<t.a; if(s.b!=t.b) return s.b<t.b; return s.c<t.c; } bool cmpb(node s,node t) { if(s.b!=t.b) return s.b<t.b; return s.c<t.c; } const int maxn=(int)(1e5)+5; const int maxk=(int)(2e5)+5; node A[maxn],T[maxn]; int C[maxn],res[maxn]; int n,mx,tot=0; inline void add(int x,int d) { while(x<=mx) { C[x]+=d; x+=lowbit(x); } } inline int sum(int x) { int ret=0; while(x>0) { ret+=C[x]; x-=lowbit(x); } return ret; } void solve(int l,int r) { if(l==r) return; int mid=(l+r)>>1; solve(l,mid);solve(mid+1,r); sort(T+l,T+mid+1,cmpb); sort(T+mid+1,T+r+1,cmpb); int i=l; for(int j=mid+1;j<=r;j++) { while(i<=mid && T[i].b<=T[j].b) add(T[i].c,T[i].siz),++i; T[j].ans+=sum(T[j].c); } for(int j=l;j<i;j++) add(T[j].c,-T[j].siz); } int main() { read(n);read(mx); REP(i,1,n) { read(A[i].a); read(A[i].b); read(A[i].c); } sort(A+1,A+n+1,cmpa); int cnt=0; REP(i,1,n) { cnt++; if(A[i]!=A[i+1]) { T[++tot]=A[i]; T[tot].siz=cnt; cnt=0; } } solve(1,tot); REP(i,1,tot) res[T[i].ans+T[i].siz-1]+=T[i].siz; REP(i,0,n-1) printf("%d\n",res[i]); return 0; } |