社区讨论
有BUG吗?为什么全部TLE
P3810【模板】三维偏序 / 陌上花开参与者 2已保存回复 1
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 1 条
- 当前快照
- 1 份
- 快照标识符
- @mi7w3xr1
- 此快照首次捕获于
- 2025/11/21 04:34 4 个月前
- 此快照最后确认于
- 2025/11/21 04:34 4 个月前
C
#include<bits/stdc++.h>
using namespace std;
const int N=100008;
int n,k,cnt[N],nn,c,tr[N];
struct lll{int a,b,c,w,ans;}d[N];
inline int read()
{
int res=0,flg=1;
char ch=getchar();
while(ch>'9'&&ch<'0'){if(ch=='-') flg=-1; ch=getchar();}
while(ch<='9'&&ch>='0') res=res*10+ch-'0',ch=getchar();
return flg*res;
}
bool cmpx(lll x,lll y)
{
return (x.a==y.a?(x.b==y.b?x.c<y.c:x.b<y.b):x.a<y.a);
}
bool cmpy(lll x,lll y)
{
return (x.b==y.b?x.c<y.c:x.b<y.b);
}
int lowbit(int x)
{
return x&(-x);
}
int pls(int x)
{
int res=0;
while(x)
{
res+=tr[x];
x-=lowbit(x);
}
return res;
}
void add(int x,int a)
{
while(x<=nn)
{
tr[x]+=a;
x+=lowbit(x);
}
}
void cdq(int l,int r)
{
if(l>=r) return ;
int mi=(l+r)>>1;
cdq(l,mi), cdq(mi+1,r);
sort(d+l,d+mi+1,cmpy);
sort(d+mi+1,d+r+1,cmpy);
int i=mi+1,j=l;
for(;i<=r;i++)
{
while(d[j].b<=d[i].b&&j<=mi)
add(d[j].c,d[j].w),j++;
d[i].ans+=pls(d[i].c);
}
for(int i=l;i<j;i++)
add(d[i].c,-d[i].w);
}
int main()
{
n=read();k=read();
for(int i=1;i<=n;i++)
d[i].a=read(),d[i].b=read(),d[i].c=read();
sort(d+1,d+n+1,cmpx);
for(int i=1;i<=n;i++)
{
c++;
if(d[i].a!=d[i+1].a||d[i].b!=d[i+1].b||d[i].c!=d[i+1].c)
d[++nn]=d[i],d[nn].w=c,c=0;
}
cdq(1,nn);
for(int i=1;i<=nn;i++)
cnt[d[i].ans+d[i].w-1]+=d[i].w;
for(int i=0;i<n;i++)
printf("%d\n",cnt[i]);
return 0;
}
回复
共 1 条回复,欢迎继续交流。
正在加载回复...