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

2017-11-27

题目背景

这是一道模板题

可以使用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：

说明

$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/

#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;
}