求助,RE+TLE
查看原帖
求助,RE+TLE
217233
SqrtSecond楼主2021/10/22 09:29
#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int read()
{
	char ch=getchar();int x=0,r=1;
	while(ch<'0'||ch>'9'){if(ch=='-')r=0;ch=getchar();}
	while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
	return r?x:-x;
}
int n,m,a[4001000],sum[4001000],num[4001000],lazy[4001000],len;
int w[4001000];
void pushup(int rt)
{
	sum[rt]=sum[rt<<1]+sum[rt<<1|1];
	if(num[rt<<1]!=num[rt<<1|1]||num[rt<<1]==-1)num[rt]=-1;
	else num[rt]=num[rt<<1];
}
void build(int l,int r,int rt)
{
    lazy[rt]=-1e18;
	if(l==r)
	{
		sum[rt]=a[l];
		return;
	}
	int mid=(l+r)>>1;
	build(l,mid,rt<<1);
	build(mid+1,r,rt<<1|1);
	pushup(rt);
}
void pushdown(int rt,int ln,int rn)
{
    if(lazy[rt]==-1e18)return;
	lazy[rt<<1]+=lazy[rt];
	lazy[rt<<1|1]+=lazy[rt];
	if(num[rt<<1]!=-1){if(num[rt<<1]==0)sum[rt<<1]+=ln;num[rt<<1]+=lazy[rt];}
	if(num[rt<<1|1]!=-1){if(num[rt<<1|1]==0)sum[rt<<1|1]+=rn;num[rt<<1|1]+=lazy[rt];}
	lazy[rt]=-1e18;
}
void update(int L,int R,int x,int l=1,int r=len,int rt=1)
{
    if(r<L||R<l)return;
	if(L<=l&&r<=R&&num[rt]!=-1)
	{
		if(num[rt]==0)sum[rt]+=w[r+1]-w[l];
		num[rt]+=x;
		if(num[rt]==0)sum[rt]-=w[r+1]-w[l];
		if(lazy[rt]==-1e18)lazy[rt]=0; 
		lazy[rt]+=x;
//		cout<<l<<" "<<r<<" "<<num[rt]<<"  "<<sum[rt]<<endl; 
		return;
	}
	int mid=(l+r)>>1;
	pushdown(rt,w[mid+1]-w[l],w[r+1]-w[mid+1]);
	update(L,R,x,l,mid,rt<<1);
	update(L,R,x,mid+1,r,rt<<1|1);
	pushup(rt);
//	cout<<l<<" "<<r<<" "<<num[rt]<<" a "<<sum[rt]<<endl;
}
int query(int L,int R,int l=1,int r=len,int rt=1)
{
	if(L<=l&&r<=R)return sum[rt];
    if(r<L||R<l)return 0;
	int mid=(l+r)>>1;
	pushdown(rt,mid-l+1,r-mid);
	int ans=0;
	ans+=query(L,R,l,mid,rt<<1);
    ans+=query(L,R,mid+1,r,rt<<1|1);
	return ans;
}
struct seg
{
	int l,r,h,w,kl,kr;
	bool operator <(const seg b)const
	{
		return h<b.h;
	}
}s[1001000];
int ans;
signed main()
{
    n=read();
    for(int i=1;i<=n;++i)
    {
    	s[2*i-1].l=s[2*i].l=read();s[2*i-1].h=read();
    	s[2*i-1].r=s[2*i].r=read();s[2*i].h=read();
    	s[2*i-1].w=1;s[2*i].w=-1;
	}
	for(int i=1;i<=n;++i)w[2*i-1]=s[2*i].l,w[2*i]=s[2*i].r;
	w[2*n+1]=1e9;
	sort(w+1,w+2*n+1);
	len=unique(w+1,w+2*n+1)-w-1;
	for(int i=1;i<=2*n;++i)
	{
		s[i].kl=lower_bound(w+1,w+2*n+1,s[i].l)-w;
		s[i].kr=lower_bound(w+1,w+2*n+1,s[i].r)-w;
	}
	sort(s+1,s+2*n+1);
	build(1,len,1);
	for(int i=1;i<=2*n;++i)
	{
//		cout<<s[i].kl<<" "<<s[i].kr<<" "<<s[i].w<<" "<<s[i].h<<endl;
		ans+=(s[i].h-s[i-1].h)*sum[1];
		update(s[i].kl,s[i].kr-1,s[i].w);
//		printf("%lld\n",ans);
	}
	printf("%lld",ans);
}
2021/10/22 09:29
加载中...