3262:陌上花开Description有n朵花，每朵花有三个属性：花形(s)、颜色(c)、气味(m)，又三个整数表示。现要对每朵花评级，一朵花的级别是它拥有的美丽能超过的花的数量 3262: 陌上花开 Tim
3262: 陌上花开
Time Limit: 20 Sec Memory Limit: 256 MB Submit: 2497 Solved: 1115 [Submit][Status][Discuss]Description
有n朵花，每朵花有三个属性：花形(s)、颜色(c)、气味(m)，又三个整数表示。现要对每朵花评级，一朵花的级别是它拥有的美丽能超过的花的数量。定义一朵花A比另一朵花B要美丽，当且仅当Sa>=Sb,Ca>=Cb,Ma>=Mb。显然，两朵花可能有同样的属性。需要统计出评出每个等级的花的数量。Input
第一行为N,K (1 <= N <= 100,000, 1 <= K <= 200,000 ), 分别表示花的数量和最大属性值。 以下N行，每行三个整数si, ci, mi (1 <= si, ci, mi <= K)，表示第i朵花的属性Output
包含N行，分别表示评级为0...N-1的每级花的数量。Sample Input
10 33 3 32 3 3 2 3 1 3 1 1 3 1 2 1 3 1 1 1 2 1 2 2 1 3 2 1 2 1Sample Output
3130101001HINT
1 <= N <= 100,000, 1 <= K <= 200,000
CDQ分治先把相同的花合并到一起，因为如果不合并的话在前面的花统计不到在后面的花先保证$a$单调不降然后在分治过程中一边以$b$为关键字归并，一边把$c$插入到权值树状数组里注意在$b$相同的时候先处理左区间的还有树状数组要每次清空，但清空方式一定要是怎么插怎么删我第一次写竟然写出了$O(nk)$的复杂度来清空树状数组。。。真是石乐志时间复杂度满足关系$T(n)=2T(\frac{n}{2})+O(nlogn)$且$T(1)=O(1)$根据主定理得到$T(n)=O(nlog^2n)$ #include #include using namespace std;char buf[10000000], *ptr = buf - 1;inline int readint(){ int n = 0; char ch = *++ptr; while(ch ‘9‘) ch = *++ptr; while(ch = ‘0‘){ n = (n <<1) + (n <<3) + ch - ‘0‘; ch = *++ptr; } return n;}const int maxn = 100000 + 10, maxk = 200000 + 10;int n, k;int arr[maxk] = {0};inline void Update(int w, int s){ for(; w <= k; w += w }inline int Query(int w){ int s = 0; for(; w; w -= w return s; }struct Node{ int a, b, c, id, s; Node(){} Node(int _a, int _b, int _c, int _id = 0, int _s = 1): a(_a), b(_b), c(_c), id(_id), s(_s){}}tp[maxn], no[maxn];class cmp{ public: bool operator () (const Node CDQ(l, mid); CDQ(mid + 1, r); while(ll <= mid tp[++tcnt] = no[ll++]; } else{ rank[no[rr].id] += Query(no[rr].c); tp[++tcnt] = no[rr++]; } } while(ll <= mid){ Update(no[ll].c, no[ll].s); tp[++tcnt] = no[ll++]; } while(rr <= r){ rank[no[rr].id] += Query(no[rr].c); tp[++tcnt] = no[rr++]; } for(int i = l; i <= mid; i++) Update(no[i].c, -no[i].s); for(int i = 1; i <= tcnt; i++) no[l + i - 1] = tp[i];}int main(){ fread(buf, sizeof(char), sizeof(buf), stdin); int N = readint(); n = 0; k = readint(); tp[0] = Node(0, 0, 0, 0, 0); for(int a, b, c, i = 1; i <= N; i++){ a = readint(); b = readint(); c = readint(); tp[i] = Node(a, b, c); } sort(tp + 1, tp + N + 1, cmp()); for(int i = 1; i <= N; i++){ if(tp[i].a == no[n].a else no[++n] = Node(tp[i].a, tp[i].b, tp[i].c, n); } CDQ(1, n); for(int i = 1; i <= n; i++) cnt[rank[no[i].id] + no[i].s - 1] += no[i].s; for(int i = 0; i