社区讨论

有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 条回复,欢迎继续交流。

正在加载回复...