扫描线18ptsRE玄关求调
查看原帖
扫描线18ptsRE玄关求调
1023793
yaodiguoan楼主2024/7/30 21:22

recordrecord

#include <bits/stdc++.h>
using namespace std;
//#pragma GCC optimize(2)
//#pragma GCC optimize(3, "Ofast", "inline")
#define hh putchar('\n')
#define kg putchar(' ')
#define debug puts("debug")
#define int long long
//#define int __int128
namespace quickread{
	template<typename T> void read(T &x){
		x=0;char c=getchar();T neg=0;
		while(!isdigit(c)) neg|=!(c^'-'),c=getchar();
		while(isdigit(c)) x=(x<<3)+(x<<1)+(c^48),c=getchar();
		if(neg) x=(~x)+1;
	}
	template<typename T> void write(T x){
		if(x<0) putchar('-'),x=~x+1;
		if(x>9) write(x/10);
		putchar(x%10^48);
	}
	inline string readstr(){
    	char ch=getchar();string str="";
		while(!isalnum(ch)) ch=getchar();
		while(isalnum(ch)){str+=ch;ch=getchar();}
		return str;
	}
	inline char readchar(){
		char ch=getchar();
		while(!isalnum(ch)) ch=getchar();
		return ch;
	}
}
using namespace quickread;
const int N=1e6+10,inf=2147483647;
int n,m,ans,sx,sy,ex,ey,dot[N];
struct Line{int lx,rx,y,mark;};
bool operator < (Line A,Line B){return A.y<B.y;}
Line line[N<<4];
namespace Segment_tree{
	struct node{int l,r,value,tag;};
	node segment_tree[N];
	#define ls (p<<1)
	#define rs (p<<1|1)
	#define mid (l+r>>1)
	void push_up(int p){
		int l=segment_tree[p].l,r=segment_tree[p].r;
		if(!segment_tree[p].tag) return segment_tree[p].value=segment_tree[ls].value+segment_tree[rs].value,void();
		segment_tree[p].value=dot[r+1]-dot[l];
	}
	void build(int l,int r,int p){
		segment_tree[p]=node{l,r,0,0};
		if(l==r) return;
		build(l,mid,ls),build(mid+1,r,rs);
	}
	void update(int lt,int rt,int p,int x){
		int l=segment_tree[p].l,r=segment_tree[p].r;
		if(lt>dot[r+1]||rt<=dot[l]) return;
		if(lt<=dot[l]&&dot[r+1]<=rt) return segment_tree[p].tag+=x,push_up(p),void();
		update(lt,rt,ls,x),update(lt,rt,rs,x);
		push_up(p);
	}
}using namespace Segment_tree;
signed main(){
//	ios::sync_with_stdio(0);
//	cin.tie(0);cout.tie(0);
	read(n);
	for(int i=1;i<=n;++i){
		read(sx),read(sy),read(ex),read(ey);
		dot[(i<<1)-1]=sx,dot[i<<1]=ex;
		line[(i<<1)-1]=Line{sx,ex,sy,1},line[i<<1]=Line{sx,ex,ey,-1};
	}n<<=1;
	sort(line+1,line+n+1),sort(dot+1,dot+n+1);
	m=unique(dot+1,dot+n+1)-dot-1;
	build(1,m-1,1);
	for(int i=1;i<n;++i){
		update(line[i].lx,line[i].rx,1,line[i].mark);
		ans+=segment_tree[1].value*(line[i+1].y-line[i].y);
	}
	write(ans);
	return 0;
}
2024/7/30 21:22
加载中...