bzoj 3262 :陌上花开 (cdq分治 三维偏序)
程序员文章站
2022-05-14 18:56:27
...
题目描述:有n朵花,每朵花有三个属性:花形(s)、颜色©、气味(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的每级花的数量。
裸的三维偏向问题,但是花的属性可能相同,显然相同的花答案是一样的,将它们离散化缩点聚在一起即可,最后答案加上这种花的数量。
#include<bits/stdc++.h>
using namespace std;
const int maxn = 3e5 + 10;
#define lowbit(i) (i & (-i))
struct node {
int s,c,m,id,cnt;
}q[maxn],tmp[maxn];
int sum[maxn],n,k,top;
int ans[maxn];
int vis[maxn];
bool cmp(node a,node b) {
if(a.s == b.s) {
if(a.c == b.c) return a.m < b.m;
return a.c < b.c;
}
return a.s < b.s;
}
int cal(node a,node b) {
if(a.s < b.s) return -1;
else if(a.s > b.s) return 1;
else if(a.s == b.s) {
if(a.c < b.c) return -2;
else if(a.c > b.c) return 2;
else if(a.c == b.c) {
if(a.m < b.m) return -3;
else if(a.m > b.m) return 3;
else if(a.m == b.m) return 0;
}
}
}
int getsum(int p) {
int ans = 0;
for(; p; p -= lowbit(p)) ans += sum[p];
return ans;
}
void modify(int p,int v) {
for(; p <= k; p += lowbit(p)) sum[p] += v;
}
void cdq(int l,int r) {
if(l == r) return;
int mid = l + r >> 1;
cdq(l,mid);cdq(mid + 1,r);
top = 0;
for(int i = l,j = mid + 1; i <= mid || j <= r;) {
if(i <= mid && (j > r || q[i].c <= q[j].c)) {
modify(q[i].m,q[i].cnt);
tmp[++top] = q[i++];
}
else {
ans[q[j].id] += getsum(q[j].m);
tmp[++top] = q[j++];
}
}
for(int i = l; i <= mid; i++)
modify(q[i].m,-q[i].cnt);
for(int i = l; i <= r; i++)
q[i] = tmp[i - l + 1];
}
int main() {
scanf("%d%d",&n,&k);
for(int i = 1; i <= n; i++)
scanf("%d%d%d",&q[i].s,&q[i].c,&q[i].m);
sort(q + 1,q + n + 1,cmp);
int tot = 0;
for(int i = 1; i <= n; i++) {
if(tot && cal(q[i],q[tot]) == 0) {
q[tot].cnt++;
}
else {
q[++tot] = q[i];
q[tot].id = tot;
q[tot].cnt = 1;
}
}
cdq(1,tot);
for(int i = 1; i <= tot; i++) {
ans[q[i].id] += q[i].cnt - 1;
}
for(int i = 1;i <= tot; i++) {
vis[ans[q[i].id]] += q[i].cnt;
}
for(int i = 0; i < n; i++)
printf("%d\n",vis[i]);
return 0;
}