题目描述
题解:
这是cdq分治模板题。
前置:cdq分治。
好像是一位大佬搞出来的神奇分治,可以直接干掉一层树形结构。
其实实现还是比较简单的。
对于区间(l,r),我们先处理(l,mid)和(mid+1,r),然后处理左右区间之间产生的影响。
具体顺序看题目而定。
比如本题,我们可以先令a有序,然后分治。
每次处理影响时先排序,然后双指针分别扫。
由于aj<=ai,bj<=bi,cj<=ci,我们在刚开始已经令a有序,所以在保证bj<=bi时将c扔到数据结构中(我用的是树状数组,线段树可以解决更多情况)。
然后每次加一下当前c的前缀和就行了。
代码:
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define N 100050
#define ll long long
inline int rd()
{
int f=1,c=0;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){c=10*c+ch-'0';ch=getchar();}
return f*c;
}
int n,k;
struct node
{
int a,b,c,f,w;
void read(){a=rd(),b=rd(),c=rd();}
}p[N],tmp[N];
bool cmp(node x,node y)
{
if(x.a!=y.a)return x.a<y.a;
if(x.b!=y.b)return x.b<y.b;
return x.c<y.c;
}
struct BIT
{
int g[N<<1];
void up(int x,int d)
{
if(!x)return ;
while(x<=200000)
{
g[x]+=d;
x+=(x&(-x));
}
}
int down(int x)
{
if(!x)return 0;
int ret = 0;
while(x)
{
ret+=g[x];
x-=(x&(-x));
}
return ret;
}
}bit;
void Sort(int l,int r)
{
int mid = (l+r)>>1;
int i = l,j = mid+1,k = l;
while(i<=mid&&j<=r)
{
while(p[i].b<=p[j].b&&i<=mid&&j<=r)
{
tmp[k] = p[i];
i++,k++;
}
while(p[i].b>p[j].b&&i<=mid&&j<=r)
{
tmp[k] = p[j];
j++,k++;
}
}
while(i<=mid)
{
tmp[k]=p[i];
i++,k++;
}
while(j<=r)
{
tmp[k]=p[j];
j++,k++;
}
for(i=l;i<=r;i++)p[i]=tmp[i];
}
int ans[N];
void cdq(int l,int r)
{
if(l==r)return ;
int mid = (l+r)>>1;
cdq(l,mid);cdq(mid+1,r);
int i,j;
for(i=l,j=mid+1;j<=r;j++)
{
while(p[i].b<=p[j].b&&i<=mid)
{
bit.up(p[i].c,p[i].w);
i++;
}
p[j].f+=bit.down(p[j].c);
}
for(i=i-1;i>=l;i--)bit.up(p[i].c,-p[i].w);
Sort(l,r);
}
bool vmp(node x,node y)
{
return x.a==y.a&&x.b==y.b&&x.c==y.c;
}
int main()
{
n=rd(),k=rd();
for(int i=1;i<=n;i++)
tmp[i].read();
sort(tmp+1,tmp+1+n,cmp);
int k=0;
tmp[0].a=-1;
for(int i=1;i<=n;i++)
{
if(vmp(tmp[i],tmp[i-1]))
{
p[k].w++;
}else
{
k++;
p[k] = tmp[i];
p[k].w = 1;
}
}
cdq(1,k);
for(int i=1;i<=k;i++)ans[p[i].f+p[i].w-1]+=p[i].w;
for(int i=0;i<n;i++)
printf("%d\n",ans[i]);
return 0;
}