为什么CDQ会TLE
查看原帖
为什么CDQ会TLE
965755
u______n楼主2024/1/2 09:27
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=4000015;
int read()
{
	int f=1,x=0;
	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;
}
struct Data
{
	int a;
	int b;
	int val;
	int f;
	int to;
	int gx;
	bool inr;
}p[N];
int ans[N];
int tot=0;
bool cmp1(Data g1,Data g2)
{
	if(g1.a!=g2.a)
	{
		return g1.a<g2.a;
	}
	return g1.val>g2.val;
}
bool cmp2(Data g1,Data g2)
{
	if(g1.b!=g2.b)
	{
		return g1.b<g2.b;
	}
	return g1.val>g2.val;
}
void cdq(int l,int r)
{
	if(l==r)
	return ;
	int mid=(l+r)/2;
	sort(p+l,p+r+1,cmp1);
	cdq(l,mid);
	cdq(mid+1,r);
	for(int i=mid+1;i<=r;i++)
	p[i].inr=1;
	sort(p+l,p+r+1,cmp2);
	int now=0;
	for(int i=l;i<=r;i++)
	{
		if(!p[i].inr)
		{
		now+=p[i].val;
		p[i].gx+=p[i].val;
		}
		if(p[i].val==0&&p[i].inr)
		{
			ans[p[i].to]+=p[i].f*now;
			p[i].gx=p[i].f*now;
		}
	}
//	cout<<l<<" "<<r<<" "<<"_________________"<<endl;
	for(int i=l;i<=r;i++)
	{
/*	if(p[i].val)
	cout<<"add"<<endl;
	else
	cout<<"query"<<endl;
	cout<<" a: "<<p[i].a<<" b: "<<p[i].b<<endl;
	if(!p[i].val)
	{
	cout<<" val: "<<p[i].val<<" f: "<<p[i].f<<" to: "<<p[i].to<<" "<<endl;
	}
	cout<<" inr: "<<p[i].inr<<" gx: "<<p[i].gx<<endl;*/
	
	p[i].inr=0;
	p[i].gx=0;
	}
}
signed main(){
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		tot++;
		//cin>>p[tot].a>>p[tot].b;
		p[tot].a=read();
		p[tot].b=read();
		p[tot].val=1;
	}
	for(int i=1;i<=m;i++)
	{
		int a,b,c,d;
	//	cin>>a>>b>>c>>d;
		a=read(),b=read(),c=read(),d=read();
		p[++tot].a=a-1;
		p[tot].b=b-1;
		p[tot].val=0;
		p[tot].f=1;
		p[tot].to=i;
		
		p[++tot].a=a-1;
		p[tot].b=d;
		p[tot].val=0;
		p[tot].f=-1;
		p[tot].to=i;
		
		p[++tot].a=c;
		p[tot].b=b-1;
		p[tot].val=0;
		p[tot].f=-1;
		p[tot].to=i;
		
		p[++tot].a=c;
		p[tot].b=d;
		p[tot].val=0;
		p[tot].f=1;
		p[tot].to=i;
	}
	sort(p+1,p+tot+1,cmp1);
	cdq(1,tot);
	for(int i=1;i<=m;i++)
	cout<<ans[i]<<endl;
	return 0;
}

是我写假了还是常数太大了?

2024/1/2 09:27
加载中...