过不了样例,求调
查看原帖
过不了样例,求调
349824
WsW_花逝爆零人楼主2024/7/31 14:48
#include<bits/stdc++.h>
using namespace std;
#define ls(x) (x<<1)
#define rs(x) (x<<1|1)
typedef long long ll;

int n;
int xx1,yy1,xx2,yy2;
struct line{
	int lx,rx,y;
	int tag;
};
bool cmp(line A,line B){return A.y<B.y;}

vector<line>l;
vector<int>X;

struct pit{
	int l,r;
	int cnt,len;
}tr[400003];

void build(int p,int l,int r){
	tr[p]={l,r,0,0};
	if(l==r)return;
	int mid=l+r>>1;
	build(ls(p),l,mid);
	build(rs(p),mid+1,r);
}

void pushup(int p){
	if(tr[p].cnt)tr[p].len=X[tr[p].r+1]-X[tr[p].l];
	else tr[p].len=tr[ls(p)].len+tr[rs(p)].len;
}

void change(int p,int l,int r,int ad){
//	cout<<p<<'\n';
	if(l<=tr[p].l&&tr[p].r<=r){
		tr[p].cnt+=ad;
		pushup(p);
		return;
	}
	if(l<=tr[ls(p)].r)change(ls(p),l,r,ad);
	if(tr[rs(p)].l<=r)change(rs(p),l,r,ad);
	pushup(p);
}

int main(){
//	ios::sync_with_stdio(0);
//	cin.tie(0);cout.tie(0);
	
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>xx1>>yy1>>xx2>>yy2;
		X.push_back(xx1);
		X.push_back(xx2);
		l.push_back({xx1,xx2,yy1,1});
		l.push_back({xx1,xx2,yy2,-1});
	}
	
	sort(X.begin(),X.end());
	sort(l.begin(),l.end(),cmp);
	X.erase(unique(X.begin(),X.end()),X.end());
	
	build(1,1,X.size()-1);
	ll ans=0;
	for(int i=0;i+1<l.size();i++){
		int lft=lower_bound(X.begin(),X.end(),l[i].lx)-X.begin();
		int rig=lower_bound(X.begin(),X.end(),l[i].rx)-X.begin();
		change(1,lft+1,rig,l[i].tag);
		ans+=(ll)tr[1].len*(l[i+1].y-l[i].y);
	}
	cout<<ans;
	return 0;
}
2024/7/31 14:48
加载中...