求调
查看原帖
求调
587959
ydkxj楼主2024/10/9 21:15
#include<iostream>
#include<algorithm>
#include<cmath>
#define ls rt<<1
#define rs rt<<1|1
using namespace std;
struct tree{
	int num,sum,lenth;
	bool flag,frag;
}t[100005];
struct edge{
	int l,r,h,val;
}e[100005];
int cnt,ans,maxn=-1e9,minn=1e9,last,n;
void addedge(int l,int r,int h,int v){
	e[++cnt].l=l;
	e[cnt].r=r;
	e[cnt].h=h;
	e[cnt].val=v;
}
void push_up(int rt,int l,int r){
	if(t[rt].sum){
		t[rt].lenth=r-l+1;
		t[rt].num=1;
		t[rt].frag=t[rt].flag=1;
	}
	if(l==r){
		t[rt].lenth=0;
		t[rt].num=0;
		t[rt].flag=t[rt].frag=0;
	}
	else {
		t[rt].lenth=t[ls].lenth+t[rs].lenth;
		t[rt].num=t[ls].num+t[rs].num;
		if(t[ls].frag&&t[rs].flag)t[rt].num--;
		t[rt].flag=t[ls].flag;
		t[rt].frag=t[rs].frag;
	}
}
void add(int rt,int l,int r,int from,int to,int value){
    if(l>=from&&r<=to){
        t[rt].sum+=value;
        push_up(rt,l,r);
        return;
    }
    int mid=(r+l)>>1;
    if(from<=mid)add(ls,l,mid,from,to,value);
    if(to>mid)add(rs,mid+1,r,from,to,value);
    push_up(rt,l,r);
}
bool cmp(edge a,edge b){
	if(a.h==b.h)return a.val>b.val;
	return a.h<b.h; 
}
int abs1(int x){
	if(x<0)return -x;
	return x;
}
int main(){
//	int n,maxn=-1e9,minn=1e9,ans=0,last=0;
	cin>>n;
	int x,y,x1,y1;
	for(int i=1;i<=n;i++){
		cin>>x>>y>>x1>>y1;
		maxn=max(maxn,max(x,x1));
		minn=min(minn,min(x,x1));
		addedge(x,x1,y,1);
		addedge(x,x1,y1,-1);
	}
	if(minn<=0){
		for(int i=1;i<=cnt;i++){
			e[i].l+=-minn+1;
			e[i].r+=-minn+1;
		}
		maxn-=minn;
	}
	sort(e+1,e+1+cnt,cmp);
	for(int i=1;i<=cnt;i++){
		add(1,1,maxn,e[i].l,e[i].r-1,e[i].val);
		while(e[i].h==e[i+1].h&&e[i].val==e[i+1].val){
			i++;
			add(1,1,maxn,e[i].l,e[i].r-1,e[i].val);
		}
		ans+=abs(t[1].lenth-last);
		last=t[1].lenth;
//		cout<<t[1].lenth<<" ";
		ans+=t[1].num*2*(e[i+1].h-e[i].h);
	}
	cout<<ans;
	return 0;
}
2024/10/9 21:15
加载中...