只过样例,WA0pts求调
查看原帖
只过样例,WA0pts求调
477821
toolong114514楼主2023/12/31 08:49
#include<algorithm>
#include<iostream>
using namespace std;
#define int long long
const int N=1e6+10;
struct ccf{
	int x1,x2,y,mark;
}line[4*N];
bool cmp(ccf pre,ccf nxt){
	return pre.y<nxt.y;
}
struct node{
	int l,r,len,cnt,laz;
}tree[4*N];
int xl[N];
void build(int pos,int lft,int rgt){
	tree[pos].l=lft;
	tree[pos].r=rgt;
	if(lft==rgt){
		tree[pos].len=xl[lft+1]-xl[lft];
		return;
	}
	int mid=(lft+rgt)/2;
	build(pos*2,lft,mid);
	build(pos*2+1,mid+1,rgt);
	tree[pos].len=tree[pos*2].len+tree[pos*2+1].len;
}
void push_down(int pos){
	tree[pos*2].cnt+=tree[pos].laz;
	tree[pos*2+1].cnt+=tree[pos].cnt;
	tree[pos*2].laz+=tree[pos].laz;
	tree[pos*2+1].laz+=tree[pos].laz;
	tree[pos].laz=0;
}
void upd(int pos,int lft,int rgt,int x){
	if(lft<=tree[pos].l&&tree[pos].r<=rgt){
		tree[pos].cnt+=x;
		tree[pos].laz+=x;
		return;
	}
	if(rgt<tree[pos].l||tree[pos].r<lft) return;
	push_down(pos);
	upd(pos*2,lft,rgt,x);
	upd(pos*2+1,lft,rgt,x);
	tree[pos].cnt=min(tree[pos*2].cnt,tree[pos*2+1].cnt);
}
int ask(int pos,int lft,int rgt){
	if(lft<=tree[pos].l&&tree[pos].r<=rgt){
		if(tree[pos].cnt) return tree[pos].len;
		else if(lft==rgt) return 0;
	}
	if(rgt<tree[pos].l||tree[pos].r<lft) return 0;
	push_down(pos);
	return ask(pos*2,lft,rgt)+ask(pos*2+1,lft,rgt);
}
int n,k,last,ans;
int find(int x){
	int ll=1,rr=k;
	while(ll<=rr){
		int mid=(ll+rr)/2;
		if(xl[mid]==x) return mid;
		else if(xl[mid]>x) rr=mid-1;
		else ll=mid+1;
	}
}
signed main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		int xx1,xx2,yy1,yy2;
		cin>>xx1>>yy1>>xx2>>yy2;
		xl[2*i]=xx1;
		xl[2*i-1]=xx2;
		if(xx1>xx2) swap(xx1,xx2);
		if(yy1>yy2) swap(yy1,yy2);
		line[2*i-1]={xx1,xx2,yy1,1};
		line[2*i]={xx1,xx2,yy2,-1};
	}
	sort(line+1,line+2*n+1,cmp);
	sort(xl+1,xl+2*n+1);
	k=unique(xl+1,xl+2*n+1)-xl;
	last=line[1].y;
	build(1,1,k-1);
	for(int i=1;i<=2*n;i++){
		ans+=ask(1,1,k-1)*(line[i].y-last);
		upd(1,find(line[i].x1),find(line[i].x2)-1,line[i].mark);
		last=line[i].y;	
	}
	cout<<ans;
	return 0;
}
2023/12/31 08:49
加载中...