关键词:三维偏序 CDQ分治 相关题目:陌上花开

将动态修改的问题改为没有动态修改的简化版 适用条件:修改独立 允许离线

论文相关:国家集训队2013论文集 浅谈数据结构题的几个非经典解法 入门题:[BZOJ1176]Mokia 题解

3262: 陌上花开

Time Limit: 20 Sec Memory Limit: 256 MB

题目链接

Description

nn朵花,每朵花有三个属性:花形(s)(s)、颜色(c)(c)、气味(m)(m),用三个整数表示。 现在要对每朵花评级,一朵花的级别是它拥有的美丽能超过的花的数量。 定义一朵花A比另一朵花B要美丽,当且仅 。 显然,两朵花可能有同样的属性。需要统计出评出每个等级的花的数量。

Input&Output

Input

第一行为 , 分别表示花的数量和最大属性值。 以下 NN 行,每行三个整数 ,表示第 ii 朵花的属性

Output

包含 NN 行,分别表示评级为 0...N10...N-1 的每级花的数量。

Sample Input

10 3
3 3 3
2 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 1

Sample Output

3
1
3
0
1
0
1
0
0
1

Solution

预备知识:逆序对

经典三维偏序问题。

思路:先将第一维排序,进行CDQ分治。分治的时候保证前一半的元素 aa 始终小于等于后一半,并且两半分别按照 bb 升序。 分治完后按照 bb 归并,对 cc 用树状数组进行维护。 当 c[i] < c[j] 时,add(a[i].z) 当 c[i] > c[j] 时,从指针 i 的起点到指针 i 的当前位置的元素可能对答案产生影响(也只有这部分元素)。在树状数组中查一下 ≤a[j].z 的数,即为答案。 (一句话:计算左边操作对右边询问的贡献) 每次分治完成后清空树状数组。

注意去重,因为一个元素会对其本身产生贡献。

AC代码

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
#include<cstdio>
#include<cctype>
#include<algorithm>
using namespace std;
#define re register int
#define rep(i,a,b) for(re i=(a);i<=(b);++i)
inline void read(int &x){
x=0;
int f=1;char ch=getchar();
while (!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while (isdigit(ch)){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
x*=f;
}
const int N=100020,K=200020;

int n,k,cnt=0,ans[N];
struct node{
int x,y,z,w,ans;
inline bool operator != (const node& rhy)const{
return x!=rhy.x || y!=rhy.y || z!=rhy.z;
}
}a[N], p[N];

struct BIT{
int t[K];
inline int lowbit(int x){return x&(-x);}
inline void update(int x,int _k){
while(x<=k) t[x] += _k, x += lowbit(x);
}
inline int query(int x){
int res=0;
while(x) res += t[x], x -= lowbit(x);
return res;
}
}T;

inline bool cmp(const node& A,const node& B){
if(A.x==B.x && A.y==B.y) return A.z<B.z;
if(A.x==B.x) return A.y<B.y;
return A.x<B.x;
} // 关键词 x<y<z
inline bool cmp_y(const node& A,const node& B)
{ return A.y<B.y || (A.y==B.y && A.z<B.z);}

inline void _unique(){
re s=0;
rep(i,1,n){
++s;
if(a[i]!=a[i+1])
p[++cnt]=a[i],p[cnt].w=s,s=0;
}
} //统计重复

inline void cdq(int l,int r){
if(l==r) return ;
int mid=(l+r)>>1;
cdq(l,mid), cdq(mid+1,r);
sort(p+l,p+mid+1,cmp_y), sort(p+mid+1,p+r+1,cmp_y);
int i=l, j=mid+1;
while(j<=r){
while(i<=mid && p[i].y<=p[j].y)
T.update(p[i].z,p[i].w), ++i;
p[j].ans += T.query(p[j].z),
++j;
}
--i;
rep(z,l,i) T.update(p[z].z,-p[z].w);
} //cdq分治

int main(){
read(n),read(k);
rep(i,1,n) read(a[i].x),read(a[i].y),read(a[i].z);
sort(a+1,a+n+1,cmp); //按x排序

_unique();
cdq(1,cnt);
rep(i,1,cnt)
ans[p[i].ans+p[i].w-1] += p[i].w;--n; //调整重复
rep(i,0,n)
printf("%d\n",ans[i]);
}