20分求助QAQ
查看原帖
20分求助QAQ
542905
WannaYellow楼主2022/11/22 11:39
#include<bits/stdc++.h>
#include <stdio.h>

using i8=char;		using u8=unsigned char;
using i16=short;	using u16=unsigned short;
using i32=int;		using u32=unsigned int;
using i64=long long;using u64=unsigned long long;
using i128=__int128;using u128=unsigned __int128;
using f32=float; 	using f64=double;				using f128=long double;

template<typename T> inline void read(T &x){
	char ch=getchar(),f=0;
	x=0;
	while(ch<'0'||ch>'9')f|=(ch=='-'),ch=getchar();
	while(ch>='0'&&ch<='9')(x=x*10+(ch-'0')),ch=getchar();
	x=(f?-x:x);
}
template<typename T,typename ...Ts> void read(T &x,Ts &...xs){read(x); read(xs...); }
char fostk[50]; u8 cntfostk;
template<typename T> inline void write(T x){
	if(x<0)putchar('-'),x=-x;
	while(x>9)fostk[++cntfostk]='0'+x%10,x/=10;
	fostk[++cntfostk]=x+'0';
	while(cntfostk)putchar(fostk[cntfostk--]);
}
template<typename T> void writesp(T x){write(x); putchar(' '); }
template<typename T> void writeln(T x){write(x); putchar('\n'); }
template<typename T> void writelns(T x){writeln(x); }
template<typename T,typename ...Ts> void write(T x,Ts ...xs){writesp(x); write(xs...); }
template<typename T,typename ...Ts> void writeln(T x,Ts ...xs){write(x,xs...); putchar('\n'); }
template<typename T,typename ...Ts> void writelns(T x,Ts ...xs){writeln(x); writelns(xs...); }
#define i32 i64
i32 n;
struct Line{
	i32 x1,x2,y,f;
	friend bool operator<(const Line &x,const Line &y){
		return x.y<y.y;
	}
}li[800005];
i32 lshlen,lsh[800005];
struct SegmentTree{
	struct Node{
		i32 lz,sum;
	}nod[200005<<4];
	i32 cntnode,rt;
	#define mid ((l+r)>>1)
	inline i32 ls(i32 x){return x<<1;}
	inline i32 rs(i32 x){return x<<1|1;}
	void build(i32 x,i32 l,i32 r){
		// fprintf(stderr,"x:%d\n",x);
		// fflush(stderr);
		if(l==r)return;
		build(ls(x),l,mid);
		build(rs(x),mid+1,r);
	}
	void update(i32 x,i32 l,i32 r){
		if(nod[x].lz)nod[x].sum=::lsh[r+1]-::lsh[l];
		else if(l==r)nod[x].sum=0;
		else nod[x].sum=nod[ls(x)].sum+nod[rs(x)].sum;
		// fprintf(stderr,"update nod[x:%d].sum:%d nod[x:%d].lz:%d\n",x,nod[x].sum,x,nod[x].lz);
		// fflush(stderr);
	}
	void modi(i32 x,i32 l,i32 r,i32 mark){
		nod[x].lz+=mark;
		if(nod[x].lz)nod[x].sum=::lsh[r+1]-::lsh[l];
		else nod[x].sum=0;
		update(x,l,r);
	}
	void modify(i32 x,i32 l,i32 r,i32 ml,i32 mr,i32 mark){
		// fprintf(stderr,"modify x:%lld l:%lld r:%lld ml:%lld mr:%lld mark:%lld\n",
			// x,l,r,ml,mr,mark);
		// fflush(stderr);
		if(ml<=l&&r<=mr)modi(x,l,r,mark);
		else{
			if(ml<=mid)modify(ls(x),l,mid,ml,mr,mark);
			if(mr>mid)modify(rs(x),mid+1,r,ml,mr,mark);
			update(x,l,r);
		}
	}
	i32 query(/*i32 x,i32 l,i32 r,i32 ql,i32 qr*/){
		// if(ql<=l&&r<=qr)return nod[x].sum;
		// i32 re=0;
		// if(ql<=mid)re+=query(ls(x),l,mid,ql,qr);
		// if(qr>mid)re+=query(rs(x),mid+1,r,ql,qr);
		return nod[1].sum;
	}
}T;
int main(){
#ifdef LOCAL
	freopen("test.in","r",stdin);
	freopen("test.out","w",stdout);
	freopen("test.err","w",stderr);
#endif
	// fprintf(stderr,"QAQ\n");
	// fflush(stderr);
	read(n);
	for(i32 i=1;i<=n;i++){
		i32 x1,y1,x2,y2;
		read(x1,y1,x2,y2);
		lsh[(i<<1)-1]=x1,lsh[i<<1]=x2;
		li[(i<<1)-1]={
			x1,x2,y1,1
		};
		li[i<<1]={
			x1,x2,y2,-1
		};
	}
	// fprintf(stderr,"out read\n");
	// fflush(stderr);
	std::sort(lsh+1,lsh+1+(n<<1));
	lshlen=std::unique(lsh+1,lsh+1+(n<<1))-lsh-1;
	std::sort(li+1,li+1+(n<<1));
	for(i32 i=1;i<=(n<<1);i++){
		li[i].x1=std::lower_bound(lsh+1,lsh+1+(n<<1),li[i].x1)-lsh;
		li[i].x2=std::lower_bound(lsh+1,lsh+1+(n<<1),li[i].x2)-lsh;
	}
	// fprintf(stderr,"out lshlen:%d\n",lshlen);
	// fflush(stderr);
	i64 ans=0;
	T.build(1,1,lshlen-1);
	// fprintf(stderr,"out cntnode:%d\n",T.cntnode);
	// fflush(stderr);
	// fprintf(stderr,"li[1].x1:%lld li[1].x2-1:%lld li[1].f:%lld\n",li[1].x1,li[1].x2-1,li[1].f);
	T.modify(1,1,lshlen-1,li[1].x1,li[1].x2-1,li[1].f);
	for(i32 i=2;i<=(n<<1);i++){
		ans+=T.query()*(li[i].y-li[i-1].y);
		// fprintf(stderr,"ans:%lld T.query():%lld*(li[i:%lld].y:%lld-li[i-1%lld].y:%lld):%lld:%lld\n",
			// ans,T.query(),i,li[i].y,i-1,li[i-1].y,li[i].y-li[i-1].y,T.query()*(li[i].y-li[i-1].y));
		T.modify(1,1,lshlen-1,li[i].x1,li[i].x2-1,li[i].f);
	}
	write(ans);
	return 0;
}
2022/11/22 11:39
加载中...