全Wa线段树,码风不佳,见谅
查看原帖
全Wa线段树,码风不佳,见谅
1061810
lllyyhhh楼主2025/8/5 11:16
#include<bits/stdc++.h>
using namespace std;
struct ddd{
	long long x1,x2,y;
	long long p;
	bool operator <(const ddd tmp)const{
		if( y != tmp.y)
			return y < tmp.y;
		return p > tmp.p;
	} 
}a[ 1600010 ];
long long x[ 1600010 ];
struct ppp{
	long long l , r , dd , tap;
}c[ 1600010 ];
void init( long long i , long long L , long long R ){
	c[ i ].l = L;
	c[ i ].r = R;
	c[ i ].dd = 0;
	c[ i ].tap = 0;
	if( L == R ){
		return ;
	}
	long long mid = L + R >> 1;
	init( i * 2 , L , mid );
	init( i * 2 + 1 , mid + 1 , R );
}
void pushup( long long i ){
	if(	!c[ i ].tap ){
		if( c[ i ].l == c[ i ].r ){
			c[ i ].dd = 0;
		}else{
			c[ i ].dd = c[ i * 2 ].dd + c[ i * 2 + 1 ].dd;
		}
	}else{
		c[ i ].dd = x[ c[ i ].r + 1 ] - x[ c[ i ].l ];
//		cout << c[ i ].dd << ' ' << x[ c[ i ].r + 1 ] << ' ' << x[ c[ i ].l ] << '\n'; 
	}
}
void add( long long i , long long L , long long R , long long d ){
	if( L <= x[ c[ i ].l ] && x[ c[ i ].r + 1 ] <= R ){
		c[ i ].tap += d;
		pushup(i);
		return ;
	}
	long long mid = x[ c[ i ].l ] + x[ c[ i ].r + 1 ] >> 1;
	if( L <= mid && c[ i ].r - c[ i ].l > 0 )add( i * 2 , L , R , d);
	if( R > mid  && c[ i ].r - c[ i ].l > 0 )add( i * 2 + 1 , L , R , d);
	pushup(i);
}
int main(){
	long long n;
	cin >> n;
	for(long long i = 1 ; i <= n ; i ++ ){
		long long q,w,e,r;
		cin >> q >> w >> e >> r;
		if( q > e )swap( q , e );
		if( w > r )swap( w , r );
		a[ i * 2 - 1 ].x1 = q;
		a[ i * 2 - 1 ].x2 = e;
		a[ i * 2 - 1 ].y = w;
		a[ i * 2 - 1 ].p = 1;
		a[ i * 2 ].x1 = q;
		a[ i * 2 ].x2 = e;
		a[ i * 2 ].y = r;
		a[ i * 2 ].p = -1;
		x[ i * 2 - 1 ] = q;
		x[ i * 2 ] = e;
	}
	n *= 2;
	sort( a + 1 , a + n + 1 );
	sort( x + 1 , x + n + 1 );
	long long tt = unique( x + 1 , x + n + 1 ) - x - 1;
	init( 1 , 1 , tt - 1 );
	long long tot = 0;
//	for(long long i = 1 ; i <= tt ; i ++ ){
//		cout << x[ i ] << ' ';
//	}
//	cout << "\n-----------------\n";
//	for(long long i = 1 ; i <= n ; i ++ ){
//		int xp = lower_bound( x + 1 , x + tt + 1 , a[ i ].x1 ) - x - 1 ;
//		int xq = lower_bound( x + 1 , x + tt + 1 , a[ i ].x2 ) - x - 1 ;
//		a[ i ].x1 = xp;
//		a[ i ].x2 = xq;
//		cout << a[ i ].x1 << ' ' << a[ i ].x2 << '\n';
//	}
	for(long long i = 1 ; i < n ; i ++ ){
//		cout <<a[ i ].x1 << ' ' << a[ i ].x2 <<' ' << a[ i ].p << ' ' << a[ i ].y << '\n';
		add( 1ll , a[ i ].x1 , a[ i ].x2 , a[ i ].p );
		tot += ( a[ i + 1 ].y - a[ i ].y ) * ( c[ 1 ].dd);
//		for(long long j = 1 ; j < 4 * tt ; j ++ ){
//			cout << c[ j ].l << ' ' << c[ j ].r <<' ' << c[ j ].dd <<' ' << c[ j ].tap <<'\n'; 
//		} 
//		cout << "---------------------------\n"; 
	}
	cout << tot;
	return 0;
}
2025/8/5 11:16
加载中...