摘要:cdq分治解决偏序问题

三维偏序

有n个元素,每个元素有$a_i,b_i,c_i$三个属性,令$f(i)$为$a_j<a_i,b_j<b_i,c_j<a_i(j \neq i)$的数量,求$d \in [0,n),f(i)=d$,的数量.

考虑对第一维排序,把问题降为两维.

然后考虑cdq分治,按时间划分左右区间来计算贡献,这里的时间为序列下标.

设现在分出了区间(l,r),递归求解子区间之后,计算跨区间的贡献,先对左右边分别按b为第一关键字排序,排序后第一维的关系并不影响,左区间还是全部小于右区间.

然后在左区间维护一个指针j,右区间维护一个指针i,在向右边移动一位i后,不断右移使得$b_j<b_i$的j,并将$c_j$加入树状数组,统计一下比$c_i$小的计算得贡献.

然后每次清除一下树状数组新加入的数.

代码

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
#include "iostream"
#include "cstdio"
#include "cstring"
#include "cmath"
#include "cstdlib"
#include "cctype"
#include "cctype"
#include "iomanip"
#include "algorithm"
#include "set"
#include "queue"
#include "map"
#include "stack"
#include "deque"
#include "vector"
#define R register
#define INF 0x3f3f3f3f
#define debug(x) printf("debug:%lld\n",x)
#define debugf(x) printf("debug:%llf\n",x)
#define debugi(x) printf("debug:%d\n",x)
#define lowbit(x) (x&-x)
#define endl putchar('\n');
typedef long long lxl;
const lxl maxn=100010,maxk=200010;
lxl n,n_,k_;
lxl ans[maxn],t[maxn];
struct _Element
{
lxl a,b,c,times,ans;
}a[maxn],b[maxn];

inline bool cmp1(_Element d1,_Element d2){return d1.a==d2.a?(d1.b==d2.b?d1.c<d2.c:d1.b<d2.b):d1.a<d2.a;}
inline bool cmp2(_Element d1,_Element d2){return d1.b==d2.b?d1.c<d2.c:d1.b<d2.b;}
inline lxl read()
{
char c=getchar();
lxl f=1,x=0;
for(;!isdigit(c);(c=='-')&&(f=-1),c=getchar());
for(;isdigit(c);x=(x<<1)+(x<<3)+(c^48),c=getchar());
return f*x;
}
inline void modify(lxl x,lxl val)
{
for(;x<maxk;x+=lowbit(x))t[x]+=val;
}
inline lxl query(lxl x)
{
lxl sum(0);
for(;x;x-=lowbit(x))sum+=t[x];
return sum;
}
void cdq(lxl l,lxl r)
{
if(l==r)return;
lxl mid((l+r)>>1);
cdq(l,mid),cdq(mid+1,r);
std::sort(b+l,b+1+mid,cmp2),std::sort(b+mid+1,b+r+1,cmp2);
lxl j=l,i=mid+1;
for(;i<=r;++i)
{
while(b[j].b<=b[i].b&&j<=mid)modify(b[j].c,b[j].times),++j;
b[i].ans+=query(b[i].c);
}
for(R int i(l);i<j;++i)modify(b[i].c,-b[i].times);
}
int main(void)
{
n_=read(),k_=read();
for(R int i(1);i<=n_;a[i].a=read(),a[i].b=read(),a[i].c=read(),++i);
std::sort(a+1,a+1+n_,cmp1);
for(R int i(1),c(0);i<=n_;++i)
{
++c;
if(a[i].a!=a[i+1].a||a[i].b!=a[i+1].b||a[i].c!=a[i+1].c)b[++n]=a[i],b[n].times=c,c=0;
}
cdq(1,n);
for(R int i(1);i<=n;++i)ans[b[i].ans+b[i].times-1]+=b[i].times;
for(R int i(0);i<n_;++i)printf("%lld\n",ans[i]);
return 0;
}