luogu3810 三维偏序

传送门

先是计算f。

显然第一维排序。

然后第二维CDQ分治。

CDQ分治时用树状数组处理第三维。 具体是这样的:

显然树状数组的两个操作分别是add(a,b)add(a,b)sum(a)sum(a),意义显然。

首先一样的点合并。(显然)

设和第i个点重合的点个数为TotiTot_i,第i个点的三维分别为Ai,Bi,CiA_i,B_i,C_i.

然后按照第一维,第二维,第三维为第一二三个关键字升序排序。

然后CDQ分治。

CDQ分治是这样的: CDQ(l,r): CDQ(l,mid) CDQ(mid+1,r) 处理[l,mid][l,mid]区间对(mid,r](mid,r]区间的贡献。

处理贡献时可以这样做: 首先很显然[l,mid][l,mid]区间和(mid,r](mid,r]区间的第二维是有序的(保持有序可以在之后归并维护),并且左区间的第一维全部严格小于右区间的。 然后归并。 假设正在比较左区间的x点和右区间的y点。 如果BxByB_x\le B_y,则add(Cx,Totx)add(C_x,Tot_x)。 否则f(y)+=sum(Cy)f(y)+=sum(C_y) 注意初始化的时候千万不能把树状数组全部置为0,要把加入树状数组的一个个减回去。 前一种方法复杂度 O(k)O(k) ,后一种复杂度 O(mlog2k)O(m log_2 k) ,其中m为加进去的个数。 则初始化的总复杂度为第一种O(nk)O(nk),后一种为O(nlog2nlog2k)O(n log_2 n log_2 k) 若一开始对第三维离散化,则复杂度为O(nlog22n)O(n log_2^2 n)

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
/*
Author: CNYALI_LK
LANG: C++
PROG: 3810.cpp
Mail: cnyalilk@vip.qq.com
*/
#include<bits/stdc++.h>
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define DEBUG printf("Passing [%s] in LINE %d\n",__FUNCTION__,__LINE__)
#define Debug debug("Passing [%s] in LINE %d\n",__FUNCTION__,__LINE__)
#define all(x) x.begin(),x.end()
using namespace std;
const double eps=1e-8;
const double PI=acos(-1.0);
typedef long long ll;
template<class T>int chkmin(T &a,T b){return a>b?a=b,1:0;}
template<class T>int chkmax(T &a,T b){return a<b?a=b,1:0;}
template<class T>T sqr(T a){return a*a;}
template<class T>T mmin(T a,T b){return a<b?a:b;}
template<class T>T mmax(T a,T b){return a>b?a:b;}
template<class T>T aabs(T a){return a<0?-a:a;}
#define min mmin
#define max mmax
#define abs aabs
int n,k;
inline int read(){
char c;
int s=0;
while(!isdigit(c=getchar()));
while(isdigit(c)){s=s*10+c-'0';c=getchar();}
return s;
}
struct node{
int a,b,c,cnt;
int ans;
void init(int d){a=read();b=read();c=read();}
};
int a_cmp(node a,node b){return a.a<b.a||(a.a==b.a&&(a.b<b.b||(a.b==b.b&&a.c<b.c)));}
node a[102424],b[102424];
int ans[102424];
int c[204848];
#define lowbit(x) x&(-x)
inline void add(int x,int y){
while(x<=k){
c[x]+=y;
x+=lowbit(x);
}
}
inline int sum(int x){
int cnt=0;
while(x){
cnt+=c[x];
x^=lowbit(x);
}
return cnt;
}
inline void cdq(int l,int r){
if(l==r){a[l].ans=a[l].cnt;return;}
int mid=(l+r)>>1;
cdq(l,mid);
cdq(mid+1,r);
int sa=l,sb=mid+1,t=l-1;
while(sb<=r){
while(sa<=mid&&a[sa].b<=a[sb].b){
b[++t]=a[sa];
add(a[sa].c,a[sa].cnt);
++sa;
}
b[++t]=a[sb];
b[t].ans+=sum(b[t].c);
++sb;
}
for(int i=l;i<sa;++i)add(a[i].c,-a[i].cnt);
while(sa<=mid){
b[++t]=a[sa];
++sa;
}
for(int i=l;i<=r;++i)a[i]=b[i];

}
inline int same(node a,node b){return a.a==b.a&&a.b==b.b&&a.c==b.c;}
int hv[233333];
int main(){
#ifdef cnyali_lk
freopen("3810.in","r",stdin);
freopen("3810.out","w",stdout);
#endif
n=read();k=read();
for(int i=1;i<=n;++i){
b[i].init(i);
hv[b[i].c]=1;
}
sort(b+1,b+n+1,a_cmp);
int m=0,l=0;
for(int i=1;i<=k;++i)if(hv[i])hv[i]=++l;
k=l;
for(int i=1;i<=n;++i)if(same(b[i],a[m])){
++a[m].cnt;
}
else {a[++m]=b[i];a[m].cnt=1;}
for(int i=1;i<=n;++i)a[i].c=hv[a[i].c];
n^=m^=n^=m;
cdq(1,n);
for(int i=1;i<=n;++i)ans[a[i].ans]+=a[i].cnt;
for(int i=1;i<=m;++i)printf("%d\n",ans[i]);
return 0;
}
文章目录
|

博客使用Disqus作为评论系统