#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;
}
标签:rt,yy,cnt,int,len,i64,扫描线,模板
From: https://www.cnblogs.com/Kescholar/p/18199853