全部re ?为啥为啥
查看原帖
全部re ?为啥为啥
44988
IU李知恩的粉丝楼主2020/7/16 22:15
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ri register int
#define rll register long long
#define For(i,a,b) for(int i=a;i<=b;++i)
#define IOS std::ios::sync_with_stdio(false)
#define L(a) a<<1
#define R(a) a<<1|1
#define P pair<int,int>
#define re read()
#define lowbit(x) ((x)&-(x))
#define Pi 3.1415926

//#define LOCAL orz
inline int read()
{
    int x=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
    return x*f;
}

const int dx[4]={0,-1,0,1};
const int dy[4]={-1,0,1,0};
// const int dx[8]={-2,-1,1,2,2,1,-1,-2};
// const int dy[8]={1,2,2,1,-1,-2,-2,-1};
const int inf=0x3f3f3f3f;
const int mod=1e9+7;
//const int ll=9e18;

const double eps=1e-5;
const int maxn=1e6+10;


struct Node{
	ll l,r;
	ll cnt;
	ll sum;
}tr[maxn<<3];
vector<ll> v;
struct node{
	ll x1,x2,h;
	int flag;
	bool operator<(const node &a) const{
		return h<a.h;
	}
}line[maxn<<3];
void build(int x,int l,int r){
	tr[x].l=l,tr[x].r=r;
	tr[x].cnt=0;tr[x].sum=0;
	if(l==r){
		return;
	}
	int mid=(l+r)>>1;
	build(L(x),1,mid);
	build(R(x),mid+1,r);
}
void pushup(int x){
	
	int l=tr[x].l,r=tr[x].r;
	if(tr[x].cnt) 	tr[x].sum=v[r]-v[l-1];
	else	tr[x].sum=tr[L(x)].sum+tr[R(x)].sum;
}

void update(int x,ll l,ll r,int c){

	if(l<=tr[x].l&&tr[x].r<=r){
		tr[x].cnt+=c;
		pushup(x);
		return;
	}
	ll mid=(tr[x].r+tr[x].l)>>1;
	if(l<=mid) update(L(x),l,r,c);
	if(r>mid) update(R(x),l,r,c);
	pushup(x);
}


int main(){

#ifdef LOCAL
    freopen("in.in","r",stdin);
    freopen("out.out","w",stdout);
#endif



	int n;
	n=re;
	ll ans=0;
	int k=0;
	ll maxc=0;
	For(i,1,n){
		ll x1,y1,x2,y2;
		scanf("%lld%lld%lld%lld",&x1,&y1,&x2,&y2);
		maxc=max(maxc,x2);
		v.push_back(x1);
		v.push_back(x2);
		line[++k]=(node){x1,x2,y1,1};
		line[++k]=(node){x1,x2,y2,-1};
	}
	sort(v.begin(),v.end());
	v.erase(unique(v.begin(),v.end()),v.end());
	sort(line+1,line+1+k);
	build((ll)1,(ll)1,lower_bound(v.begin(),v.end(),maxc)-v.begin());
	For(i,1,k-1){
		int l=lower_bound(v.begin(),v.end(),line[i].x1)-v.begin()+1;
		int r=lower_bound(v.begin(),v.end(),line[i].x2)-v.begin();
		update(1,l,r,line[i].flag);
		ans+=tr[1].sum*(line[i+1].h-line[i].h);
	}
	printf("%lld",ans);
}
2020/7/16 22:15
加载中...