出了些奇怪的问题,求求dalao帮忙看看吧
查看原帖
出了些奇怪的问题,求求dalao帮忙看看吧
111349
bobzbh楼主2023/1/30 22:18
//我很好奇为啥我第一个样例跟答案一模一样但是是WA
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
#define ls(x) (x<<1)
#define rs(x) ((x<<1)+1)
#define N 100100
using namespace std;
long long y[2*N],all=0,len=0;
long long ans=0;
struct operate
{
	long long val,tag,minn;
	//minn 表示区间内部最小值,方便统计区间是否需要累计算入答案 
}tree[4*N];
//个人习惯性线段树写法 
void push_down(long long p,long long l,long long r)
{
	long long lson=ls(p),rson=rs(p),val=tree[p].tag,mid=(l+r)>>1;
	tree[lson].val+=(mid-l)*val;
	tree[rson].val+=(r-mid)*val;
	tree[lson].tag+=val;
	tree[rson].tag+=val;
	tree[p].tag=0;
	tree[lson].minn+=val;
	tree[rson].minn+=val;
}
void push_up(long long p)
{
	long long lson=ls(p),rson=rs(p);
	tree[p].val=tree[lson].val+tree[rson].val;
	tree[p].minn=min(tree[lson].minn,tree[rson].minn);
}
void add(long long p,long long l,long long r,long long pl,long long pr,long long val)
{
	if(r<=pl||l>=pr)
	{
		return ;
	}
	if(l>=pl&&r<=pr)
	{
		tree[p].val+=(r-l)*val;
		tree[p].tag+=val;
		tree[p].minn+=val;
		return ;
	}
	push_down(p,l,r);
	long long mid=(l+r)>>1,lson=ls(p),rson=rs(p);
	add(lson,l,mid,pl,pr,val),add(rson,mid,r,pl,pr,val);
	push_up(p);
}
long long find_(long long p,long long l,long long r)
{
	if(tree[p].minn>0)
	{
		return y[r]-y[l];
	}
	if(r-l==1)
	{
		return 0;
	}
	push_down(p,l,r);
	long long mid=(l+r)>>1,lson=ls(p),rson=rs(p);
	return find_(lson,l,mid)+find_(rson,mid,r);
}
struct node
{
	long long l,r,x,val;
}ope[2*N];
//离散化排序 
bool cmp(node a,node b)
{
	if(a.x==b.x)
	{
		return a.val<b.val;
	}
	return a.x<b.x;
}
signed main()
{
	cin.tie(0),cout.tie(0);
	ios::sync_with_stdio(false);
	long long n,tot=0;
	cin>>n;
	for(long long i=1; i<=n; ++i)
	{
		long long x1,x2,y1,y2;
		cin>>x1>>y1>>x2>>y2;
		y[++all]=y1;
		y[++all]=y2;
		ope[++tot].l=min(y1,y2);
		ope[tot].r=max(y1,y2);
		ope[tot].x=min(x1,x2);
		ope[tot].val=1;
		ope[++tot].l=ope[tot-1].l;
		ope[tot].r=ope[tot-1].r;
		ope[tot].x=max(x1,x2);
		ope[tot].val=-1;
	}
	sort(ope+1,ope+1+tot,cmp);
	sort(y+1,y+1+all);
	len=unique(y+1,y+1+all)-y-1;
	for(long long i=1; i<=tot-1; ++i)
	{
		long long xlen=ope[i+1].x-ope[i].x,l=lower_bound(y+1,y+1+len,ope[i].l)-y,r=lower_bound(y+1,y+1+len,ope[i].r)-y;
		add(1,0,len,l,r,ope[i].val);
		ans+=find_(1,0,len)*xlen;
	}
	cout<<ans;
	return 0;
}
2023/1/30 22:18
加载中...