P3810 【模板】三维偏序[CDQ分治]

题目背景

这是一道模板题

可以使用bitset,CDQ分治,K-DTree等方式解决。

题目描述

有 $ n $ 个元素,第 $ i $ 个元素有 $ a_i $、$ b_i $、$ c_i $ 三个属性,设 $ f(i) $ 表示满足 $ a_j \leq a_i $ 且 $ b_j \leq b_i $ 且 $ c_j \leq c_i $ 的 $ j $ 的数量。

对于 $ d \in [0, n) $,求 $ f(i) = d $ 的数量

输入输出格式

输入格式:

第一行两个整数 $ n $、$ k $,分别表示元素数量和最大属性值。

之后 $ n $ 行,每行三个整数 $ a_i $、$ b_i $、$ c_i $,分别表示三个属性值。

输出格式:

输出 $ n $ 行,第 $ d + 1 $ 行表示 $ f(i) = d $ 的 $ i $ 的数量。

输入输出样例

输入样例#1:

1
2
3
4
5
6
7
8
9
10
11
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

输出样例#1:

1
2
3
4
5
6
7
8
9
10
3
1
3
0
1
0
1
0
0
1

说明

$1 \leq n \leq 100000, 1 \leq k \leq 200000$

题解

http://www.hekai.site/wordpress/2017/08/26/cdq%E5%88%86%E6%B2%BB%E8%AF%A6%E8%A7%A3%EF%BC%88bzoj3262-%E9%99%8C%E4%B8%8A%E8%8A%B1%E5%BC%80%EF%BC%89/

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
#include<bits/stdc++.h>
using namespace std;
int qmax(int &x,int y) {if (x<y) x=y;}
int qmin(int &x,int y) {if (x>y) x=y;}
inline int read()
{
char s;int k=0,base=1;
while((s=getchar())!='-'&&s!=EOF&&!(s>='0'&&s<='9'));
if(s==EOF)exit(0);if(s=='-')base=-1,s=getchar();
while(s>='0'&&s<='9'){k=k*10+(s^48);s=getchar();}
return k*base;
}
void write(int x)
{
if(x<0){putchar('-');write(-x);}
else{if(x/10)write(x/10);putchar(x%10+'0');}
}
int n,k,num;
struct node
{
int x,y,z,t,ans;
} a[100100];
node A[100100],c[100100];int ans[100100],t[200100];
bool cmp(node aa,node bb) {return (aa.x==bb.x)?(aa.y==bb.y?(aa.z<bb.z):(aa.y<bb.y)):(aa.x<bb.x);}
inline void xg(int x,int y) {while (x<=k) {t[x]+=y;x+=(x&(-x));}}//树状数组修改操作
inline int qh(int x) {int s=0;while (x) {s+=t[x];x^=(x&(-x));}return s;}//树状数组查询操作
inline void hb(int l,int r)//归并排序
{
if (l==r) return;
int mid=(l+r)>>1;int i=l,j=mid+1,p=l-1;
while (i<=mid&&j<=r) {p++;if (a[i].y<=a[j].y) c[p]=a[i++]; else c[p]=a[j++];}
while (i<=mid) {p++;c[p]=a[i++];}while (j<=r) {p++;c[p]=a[j++];}
for (int i=l;i<=r;i++) a[i]=c[i];
}
inline void ef(int l,int r)
{
if (l==r) return;int mid=(l+r)>>1;
ef(l,mid);ef(mid+1,r);
hb(l,mid);hb(mid+1,r);//把两边分开按y从小到大排序
int i=l,j=mid+1;
while (j<=r)
{
while (i<=mid&&a[i].y<=a[j].y) {xg(a[i].z,a[i].t);i++;}
a[j].ans+=qh(a[j].z);j++;
}
for (int k=l;k<i;k++) xg(a[k].z,-a[k].t);//清掉
}
int q[100100];int Map[100100];
int main()
{
n=read();k=read();
for (int i=1;i<=n;i++) {A[i].x=read();A[i].y=read();A[i].z=read();}
sort(A+1,A+n+1,cmp);num=0;
for (int i=1;i<=n;i++)
if (i==1||A[i].x!=A[i-1].x||A[i].y!=A[i-1].y||A[i].z!=A[i-1].z) {num++;a[num]=A[i];a[num].t=1;} else a[num].t++;//xyz都相同的情况放一起
ef(1,num);
for (int i=1;i<=num;i++) Map[a[i].ans+a[i].t-1]+=a[i].t;
for (int i=0;i<n;i++) write(Map[i]),putchar('\n');
return 0;
}