MnZn求条,cdq板子都不会了。
查看原帖
MnZn求条,cdq板子都不会了。
907667
thousands_of_years楼主2025/1/23 21:45

样例都没有通过,但就是看不出来哪错了

#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read()
{
	int x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9')
	{
		if(ch=='-') f=-1;
		ch=getchar();
	}
	while(ch>='0' &&ch<='9')
	{
		x=x*10+ch-'0';
		ch=getchar();
	}
	return x*f;
}
const int M=1e6+9,N=1e6+9;
int n,k;
struct Node{
	int a,b,c,sum,ans;
	bool bo;
}e[N],a[N];
int ans[N];
bool cmp(Node aa,Node bb)
{
	if(aa.a==bb.a)
	{
		if(aa.b==bb.b)
		{
			return aa.c<bb.c;
		}
		return aa.b<bb.b;
	}
	return aa.a<bb.a;
}
void cdq2(int l,int r)
{
	if(l==r) return ;
	int mid=l+r>>1;
	cdq2(l,mid);
	cdq2(mid+1,r);
	int i=l,j=mid+1,cnt=0,pos=0;
	while(i<=mid || j<=r)
	{
		if( (e[i].c<=e[j].c|| j>r )&& i<=mid)
		{
			a[++cnt]=e[i];
			pos+=(e[i].bo^1)*e[i].sum;
			i++;
		}
		else
		{
			e[j].ans+=(e[j].bo*pos);
			a[++cnt]=e[j];
			j++;
		}
	}
	for(int i=1;i<=cnt;i++)
	e[i+l-1]=a[i];
}
void cdq1(int l,int r)
{
	if(l==r) return ;
	int mid=l+r>>1;
	cdq1(l,mid);
	cdq1(mid+1,r);
	int i=l,j=mid+1,cnt=0;
	while(i<=mid || j<=r)
	{
		if( (e[i].b<=e[j].b || j>r)&& i<=mid)
		{
			a[++cnt]=e[i];
			a[cnt].bo=0;
			i++;
		}
		else
		{
			a[++cnt]=e[j];
			a[cnt].bo=1;
			j++;
		}
	}
	for(int i=1;i<=cnt;i++)
	e[i+l-1]=a[i];
	cdq2(l,r);
}
int po[N];
signed main()
{
	n=read(),k=read();
	for(int i=1;i<=n;i++)
	{
		e[i].a=read();
		e[i].b=read();
		e[i].c=read();
	}
	sort(e+1,e+1+n,cmp);
	int len=0,lenn=0,qp=n;
	for(int l=1,r=1;r<=n;l=r)
	{
		while(e[l].a==e[r].a && e[l].b==e[r].b&& e[l].c==e[r].c && r<=n)
		{
			r++;len++;
		}
		e[++lenn].sum=len;
		e[lenn].a=e[l].a;
		e[lenn].b=e[l].b;
		e[lenn].c=e[l].c;
		len=0;
	}
	n=lenn;
//	for(int i=1;i<=n;i++)
//	cout<<e[i].a<<e[i].b<<e[i].c<<e[i].sum<<endl; 
	cdq1(1,n);
//	for(int i=1;i<=n;i++)
//	cout<<e[i].ans<<endl;
	for(int i=1;i<=n;i++)
	po[e[i].ans+e[i].sum-1]+=e[i].sum;
	for(int i=0;i<qp;i++)
	{
		cout<<po[i]<<endl;
	}
}
2025/1/23 21:45
加载中...