扫描线模板

#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
const int N = 1e6 + 5;

//本模板是从左往右扫的，从下往上扫同理
#define ls (rt<<1)
#define rs (rt<<1|1)

i64 cover[N * 8]; //存放i节点对应区间覆盖情况的值
i64 n;
i64 len[N * 8];
i64 yy[N * 2]; //存放离散后的y值，下标用lowerbound进行查找
i64 cnt = 0;
struct node {
	i64 x;
	i64 up, down;; //边的y坐标上，y坐标下
	i64 inout;//入边为1，出边为-1
} line[N * 2], u;

bool cmp(node a, node b) {
	if ( a.x == b.x ) return a.inout > b.inout; //一定是加边在前面！！！
	return a.x < b.x;
}

void pushup( i64 l, i64 r, i64 rt ) {
	//pushup其实主要就思考在什么情况，需要更新哪些信息来维护线段树
	if ( cover[rt] > 0 ) len[rt] = yy[r] - yy[l];
	//如果某个节点的cover为正，那么这个点对应区间的长度全为有效的
	else if ( l + 1 == r ) len[rt] = 0; //到了叶子节点
	else len[rt] = len[ls] + len[rs];
}

void update( i64 yl, i64 yr, i64 pd, i64 l, i64 r, i64 rt ) {
	if ( yl > r || yr < l ) return ;
	if ( yl <= l && yr >= r ) {
		cover[rt] += pd;//根据出边入边，加上相应的值
		pushup( l, r, rt );
		return ;
	}
	if ( l + 1 == r ) return ; //到子节点，这句一定要有！！！
	i64 mid = (l + r) >> 1;
	if ( yl <= mid ) {
		update( yl, yr, pd, l, mid, ls );
	}
	if ( yr > mid ) {
		update( yl, yr, pd, mid, r, rs );
		//这里不再是m+1,因为要进入类似[1,2][2,3]的叶子节点
	}

	pushup( l, r, rt );
}

int main() {
	cnt = 0;
	cin >> n;

	//左上角到右下角
	auto get = [&](int x1, int y1, int x2, int y2) {
		u.x = x1; u.down = y1, u.up = y2, u.inout = 1;
		line[ ++cnt ] = u;//给入边赋值
		yy[cnt] = y1;//获得y值

		u.x = x2; u.down = y1, u.up = y2, u.inout = -1;
		line[ ++cnt ] = u;
		yy[cnt] = y2;
	};

	for (i64 i = 1; i <= n; i++) {
		int x, y;
		cin >> x >> y;
		get(0, y - 1, x, y);
		get(x - 1, 0, x, y);
	}

	sort( yy + 1, yy + cnt + 1); //给yy排个序
	sort( line + 1, line + cnt + 1, cmp ); //给line按照x轴方向从左到右排序
	i64 length = unique( yy + 1, yy + cnt + 1 ) - (yy + 1);
	//进行离散化操作，unique返回重复位置指针，减去（头指针+1）是数组开始的地方得到数组长度
	memset( cover, 0, sizeof( cover ) );
	memset( len, 0, sizeof(len) );

	i64 ans = 0;
	for (i64 i = 1; i <= cnt; i++) {
		ans += len[1] * ( line[i].x - line[i - 1].x );
		i64 yl = lower_bound( yy + 1, yy + length + 1, line[i].down ) - yy;
		i64 yr = lower_bound( yy + 1, yy + length + 1, line[i].up ) - yy;
		i64 pd = line[i].inout;
		update( yl, yr, pd, 1, length, 1 );
	}
	cout << ans << '\n';

	return 0;
}