P3810 【模板】三维偏序（陌上花开）
题目背景
这是一道模板题
可以使用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 leq n leq 100000, 1 leq k leq 200000 $
这里采用的是归并排序套树状数组的做法。
先不考虑重复元素
首先考虑二维偏序，我们可以对二元组((x,y))以(x)为第一关键字,(y)为第二关键字进行排序。然后单独讨论(y)的顺序对（与逆序对相反的一个概念），每个(y)的顺序对数量即为满足题目条件的顺序对数量。这点不难想明白。
然后类比三维偏序，我们可以对三元组((x,y,z))同样如此做，但统计时并不是(y)的所有顺序对都合法，我们对统计时的(z)维护一权值树状数组，每次查询在顺序对中有多少个(z)小于等于当前的(z)的
考虑重复元素，这个题题意没有明确说明，但每个三元组是不考虑自己的。
我们先缩点去重，然后统计的时候按数量统计即可
Code:
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int N=100010;
const int M=200010;
struct node
{
int x,y,z,cnt;
bool friend operator <(node n1,node n2)
{
if(n1.x==n2.x)
{
if(n1.y==n2.y) return n1.z<n2.z;
return n1.y<=n2.y;
}
return n1.x<n2.x;
}
}a[N],d[N],dx[N],tmp[N];
int n,n_,k;
void init()
{
scanf("%d%d",&n_,&k);
for(int i=1;i<=n_;i++)
{
scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].z);
a[i].cnt=1;
}
sort(a+1,a+1+n_);
for(int i=1;i<=n_;i++)
{
while(d[n].x==a[i].x&&d[n].y==a[i].y&&d[n].z==a[i].z) d[n].cnt++,i++;
if(i<=n_) d[++n]=a[i];
}
}
int sum[M],ans[N],cnt0[N];
void add(int x,int delta)
{
while(x<=k)
{
sum[x]+=delta;
x+=x&-x;
}
}
int query(int x)
{
int s=0;
while(x)
{
s+=sum[x];
x-=x&-x;
}
return s;
}
void divide(int l,int r)
{
if(l==r) {cnt0[l]+=dx[l].cnt-1;return;}
int mid=l+r>>1;
divide(l,mid);
divide(mid+1,r);
int pos=l,cnt=l-1;
for(int i=mid+1;i<=r;i++)
{
while(pos<=mid&&dx[pos]<dx[i])
{
tmp[++cnt]=dx[pos];
add(dx[pos].y,dx[pos].cnt);
pos++;
}
tmp[++cnt]=dx[i],cnt0[dx[i].z]+=query(dx[i].y);
}
for(int i=l;i<pos;i++)
add(dx[i].y,-dx[i].cnt);
while(pos<=mid) tmp[++cnt]=dx[pos++];
for(int i=l;i<=r;i++)
dx[i]=tmp[i];
}
void work()
{
for(int i=1;i<=n;i++)
dx[i].x=d[i].y,dx[i].y=d[i].z,dx[i].z=i,dx[i].cnt=d[i].cnt;
divide(1,n);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=dx[i].cnt;j++)
ans[cnt0[dx[i].z]]++;
}
for(int i=0;i<n_;i++)
printf("%d
",ans[i]);
}
int main()
{
init();
work();
return 0;
}
2018.7.15