题解 CF12D 【Ball】
LuckyCloud
2018-06-09 15:36:22
### 本题解，某些话有些绕，已加粗注明重点，可能需要多读几遍，也可以自己画图理解。
------------
第一次看到这道题完全无头绪，偶然间看到了一种东西叫**CDQ分治**——可以解决偏序问题的一种高端操作，不会CDQ分治的同学可以到B站或者Youtube上看视频，讲的超级详细！！我这里就稍微简单的讲一下基于CDQ分治如何解决这道题。
归并排序都会的吧？~~（假装你们会了）~~那么就简单多了，我们首先按所有lady的第一个属性排序，然后按照第二个属性归并排序，重点来了——归并排序有什么用？
首先我们已经按第一个属性排序过了，那么在归并排序中合并两个有序序列的时候，
可以保证
**左序列和右序列的所有元素的第一个属性值必定满足某种大小关系**
For Example
(5,3,2)(4,3,2)(3,5,1)(2,4,2)(1,4,3)[已经按第一个属性从大到小排序完成]
** 那么我们在归并排序中合并左右两个序列的时候，可以保证，左序列的任意一个元素的第一个属性必定大于右序列任意一个元素的第一个属性。**
OK，不知道你们有没有觉得有一丝神奇。那么接下来在合并左右序列的时候，**当遇到左序列的当前指向元素的第二个属性大于右序列的当前指向元素的第二个属性的时候**我们就把左序列的当前指向元素的第三个属性丢进**树状数组**。当右序列的当前指向元素的第二个属性小于等于右序列的当前指向元素的第二个属性的时候，我们就利用树状数组，通过一些计算，**得出大于右序列当前指向元素的第三个属性的属于左序列的元素的个数**为什么能这样做？第一个属性绝对满足大小关系，上文已经说过。至于第二个属性，**只有大于右序列当前元素的属于左序列的元素被查询的时候才会在树状数组里**
关于以上这些特性请仔细看代码和深入理解归并排序，代码丑陋，请谅解
LuckyCloud
```cpp
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
struct data
{
int a,b,c,id;
}p[500003],res[500003];
int n,t,tot,c[500003],ds[500003],f[500003],ans;
inline int read()
{
register int cnt=0,f=1,ch=getchar();
while (ch<'0'||ch>'9'){if (ch=='-')f=-1;ch=getchar();}
while (ch>='0'&&ch<='9'){cnt=cnt*10+ch-48;ch=getchar();}
return cnt*f;
}
inline int find(int x)
{
int l=1,r=tot,mid;
while (l<=r)
{
mid=(l+r)>>1;
if (ds[mid]==x) return mid;
if (ds[mid]>x) r=mid-1;
if (ds[mid]<x) l=mid+1;
}
}
inline void clear(int x)
{
for (int i=x;i<=500000;i+=i&-i)
c[i]=0;
}
inline void add(int x)
{
for (int i=x;i<=500000;i+=i&-i)
c[i]++;
}
inline int query(int x)
{
int res=0;
for (int i=x;i;i-=i&-i)
res+=c[i];
return res;
}
inline bool cmp(data x,data y)
{
return x.a>y.a||(x.a==y.a&&x.c<y.c);//(x.a==y.a&&x.c<y.c)为了避免一种情况，希望读者自行理解
}
void solve(int l,int r)
{
int mid=(l+r)>>1,x=l,y=mid+1,len=0;
while (x<=mid&&y<=r)
{
if (p[x].b>p[y].b){add(p[x].c);res[++len]=p[x++];}
else {f[p[y].id]+=x-l-query(p[y].c);res[++len]=p[y++];}//对于(a,b,c)，将x<a,y<b,z<c，(x,y,z)的个数存入f数组
}
while (x<=mid) res[++len]=p[x++];
while (y<=r) {f[p[y].id]+=x-l-query(p[y].c);res[++len]=p[y++];}
for (int i=l;i<=mid;i++)
clear(p[i].c);
for (int i=1;i<=len;i++)
p[l+i-1]=res[i];
}
inline void CDQ(int l,int r)
{
int mid=(l+r)>>1;
if (l==r) return;
CDQ(l,mid);
CDQ(mid+1,r);
solve(l,r);
}
int main()
{
n=read();
for (int i=1;i<=n;i++)
{p[i].id=i;p[i].a=read();}
for (int i=1;i<=n;i++)
p[i].b=read();
for (int i=1;i<=n;i++)
ds[i]=p[i].c=read();
sort(ds+1,ds+1+n);//离散化部分
tot=1;
t=ds[1];
for (int i=2;i<=n;i++)
if (ds[i]!=t){ds[++tot]=ds[i];t=ds[i];}
for (int i=1;i<=n;i++)
p[i].c=find(p[i].c);//将第三个属性离散化，用于之后的树状数组。
sort(p+1,p+1+n,cmp);//按第一个属性排序
CDQ(1,n);//CDQ分治
for (int i=1;i<=n;i++)
if (f[i]>0) ans++;
printf("%d\n",ans);
return 0;
}
```