样例都过不了求助
查看原帖
样例都过不了求助
1066565
Zhang_xiangyou楼主2024/7/3 22:10
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
long long c,e,n,w,h,r,q,tot,ans,raw[200005];
long long lsh[MAXN],cnt,num[MAXN],val[200005][2];
struct node
{
	long long x,y,s,z;
}a[200005];

bool cmp(node a,node b)
{
	return a.x < b.x;
}

struct noded
{
	long long l,r;
	long long sum,add,len;
	#define l(x) tree[x].l
	#define r(x) tree[x].r
	#define sum(x) tree[x].sum
	#define add(x) tree[x].add
	#define len(x) tree[x].len
}tree[1000005];

void build(long long p,long long x,long long y)
{
	l(p) = x;
	r(p) = y;
	if (x == y)
	{
		return; 
	}
	int mid = (l(p)+r(p))/2;
	build(p*2,x,mid);
	build(p*2+1,mid+1,y);
}

void spread(long long p)
{
	if (add(p)) 
	{
		sum(p*2) += add(p); 
		sum(p*2+1) += add(p);
		sum(p) = sum(p);
		add(p*2) += add(p);
		add(p*2+1) += add(p);
		add(p) = 0; 
		if (sum(p))
		{
			len(p) = raw[r(p)+1]-raw[l(p)];   
		}
		else
		{
			len(p) = len(p*2+1) +len(p*2);
		}
	} 
}

void change(long long p,long long x,long long y,long long d)
{
	if (x <= l(p) && r(p) <= y)
	{
		sum(p) += d;
		add(p) += d;
		if (sum(p))
		{
			len(p) = raw[r(p)+1]-raw[l(p)];   
		}
		else
		{
			len(p) = len(p*2+1) +len(p*2);
		}
		return;
	}
	spread(p);
	int mid = (l(p)+r(p))/2;
	if (x <= mid) change(p*2,x,y,d);
	if (y > mid) change(p*2+1,x,y,d);
	if (sum(p))
	{
		len(p) = raw[r(p)+1]-raw[l(p)];   
	}
	else
	{
		len(p) = len(p*2+1) +len(p*2);
	}
}

int main()
{
	cin >> n;
	for (long long i=1;i<=n;i++)
	{
		scanf("%lld%lld%lld%lld",&r,&q,&c,&e);
		a[++tot] = node{r,q,c,1};
		raw[tot] = q;
		a[++tot] = node{e,q,c,-1};
		raw[tot] = e; 
	}
	sort(raw+1,raw+tot+1);
	cnt = unique(raw+1,raw+tot+1)-(raw+1);
	for (long long i=1;i<=cnt;i++)
	{
		val[i][0] = lower_bound(raw+1,raw+cnt+1,a[i].y)-raw;
		val[i][1] = lower_bound(raw+1,raw+cnt+1,a[i].s)-raw;
	}
	build(1,1,cnt-1); 
	sort(a+1,a+cnt+1,cmp);
	for (long long i=1;i<cnt;i++)
	{
		change(1,val[i][0],val[i][1],a[i].z);
		ans += tree[1].len*(a[i+1].x-a[i].x);
	}
	cout<<ans;
	return 0;
}
2024/7/3 22:10
加载中...