为什么用了优化还是TLE
查看原帖
为什么用了优化还是TLE
142549
hbhz_zcy楼主2021/8/11 11:19

前两个点AC,其他8个TLE,已用线段树优化
code

#include<iostream>
#include<cstdio>
#include<algorithm> 
#define LL long long
using namespace std;
const int maxn=1e5+10;
struct nodea{int x,ya,yb,k;}a[maxn*2];
struct nodef{int l,r,h,v;}f[maxn*8];//h=fugaishu
int n,lsy[maxn*2],sumy;LL ans;//DianXianDuanShu:(l,l):l->l+1;
bool cmp(nodea x,nodea y){return x.x<y.x;}
void pushup(int t){
	f[t].v=f[t<<1].v+f[t<<1|1].v;
	f[t].h=f[t<<1].h|f[t<<1|1].h?-1:0;
}
void pushdown(int t){
	if(f[t].h<0)  return;
	f[t<<1].h=f[t<<1|1].h=f[t].h;
	if(f[t].h){
		f[t<<1].v=lsy[f[t<<1].r+1]-lsy[f[t<<1].l];
		f[t<<1|1].v=lsy[f[t<<1|1].r+1]-lsy[f[t<<1|1].l];
	}
	f[t].h=-1;
	return;
}
void build(int t,int l,int r){
	f[t].l=l,f[t].r=r;
	if(l==r)  return;
	int m=(l+r)/2;
	build(t<<1,l,m);
	build(t<<1|1,m+1,r);
	return;
}
void add(int t,int ul,int ur,int v){
	int l=f[t].l,r=f[t].r;
	if(ul<=l&&r<=ur&&f[t].h!=-1){
		f[t].h+=v;
		if(f[t].h)  f[t].v=lsy[r+1]-lsy[l];
		else f[t].v=0;
		return;
	}
	pushdown(t);
	int m=(l+r)/2;
	if(ul<=m)  add(t<<1,ul,ur,v);
	if(ur>m)  add(t<<1|1,ul,ur,v);
	pushup(t);
	return;
}
void beonly(int ul,int ur){//QuChong
	int px=ul,py=ul+1;
	for(;py<=ur;py++)
		if(lsy[px]!=lsy[py])  lsy[++px]=lsy[py];
	sumy=px-1;//besides 0
	for(;px<=py;px++)  lsy[px]=0;
	return;
}
int efy(int x,int l,int r){//ErFen y
	if(l==r)  return l;
	int m=(l+r)/2;
	if(x<=lsy[m])  return efy(x,l,m);
	return efy(x,m+1,r);
}
void ts(){
	for(int i=1;i<=2*sumy;i++)
		printf("%d:%d %d %d %d\n",i,f[i].l,f[i].r,f[i].h,f[i].v);
		printf("\n");
}
int main(){//only beonly y
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		int xa,ya,xb,yb;scanf("%d%d%d%d",&xa,&ya,&xb,&yb);
		a[2*i-1].x=xa;a[2*i].x=xb;
		a[2*i-1].ya=a[2*i].ya=ya;a[2*i-1].yb=a[2*i].yb=yb;
		a[2*i-1].k=1;a[2*i].k=-1;
		lsy[2*i]=ya;lsy[2*i-1]=yb;
	}
	sort(lsy+1,lsy+1+2*n);beonly(1,2*n+1);
	for(int i=1;i<=2*n;i++){
		a[i].ya=efy(a[i].ya,1,sumy);
		a[i].yb=efy(a[i].yb,1,sumy);
	}
	sort(a+1,a+1+2*n,cmp);build(1,1,sumy);
	for(int i=1;i<=2*n;i++){
		ans+=1LL*f[1].v*(a[i].x-a[i-1].x);
		add(1,a[i].ya,a[i].yb-1,a[i].k);
	}
	printf("%lld\n",ans);
	return 0;
}
2021/8/11 11:19
加载中...