【线段树 扫描线】洛谷 P5490 【模板】扫描线
2021-03-15 22:09:00 # ACM

题链

对于$mark$的引入:
如果不引入直接加，会出现某段区间被重复加的现象，要保证若某段区间被覆盖，则只需要加一次。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#include <bits/stdc++.h>
#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
//#pragma GCC optimize("O2")
using namespace std;
#define LL long long
#define ll long long
#define ULL unsigned long long
#define ls rt<<1
#define rs rt<<1|1
#define one first
#define two second
#define MS 100009
#define INF 1e18
#define mod 99999997
#define Pi acos(-1.0)
#define Pair pair<LL,LL>
#define eps 1e-9

LL n,m,k;
struct node{
	LL xl,xr,y,g;
}line[MS*2];  	// 记录一排排的线 
LL hx[MS*2];    // 对 x 轴上的坐标 hash 
LL mark[MS<<3]; // 标记区间是否被覆盖 
LL sum[MS<<3];  // 主要用sum[1]计算被覆盖区间的总和 
LL tli,thx;

bool cmp(node a,node b){
	return a.y < b.y;
}

void push_up(int rt,int l,int r){
	if(mark[rt]) sum[rt] = hx[r+1] - hx[l];
	else if(l == r) sum[rt] = 0;
	else sum[rt] = sum[ls] + sum[rs];
}

void update(int L,int R,int l,int r,int rt,LL val){
	if(L <= l && r <= R){
		mark[rt] += val;
		push_up(rt,l,r);
		return;
	}
	int m = l+r>>1;
	if(m >= L) update(L,R,l,m,ls,val);
	if(m <  R) update(L,R,m+1,r,rs,val);
	push_up(rt,l,r);
}

int main(){
	//ios::sync_with_stdio(false);
	cin >> n;
	for(int i=1;i<=n;i++){
		LL x1,y1,x2,y2;
		cin >> x1 >> y1 >> x2 >> y2;
		hx[++tli] = x1;
		line[tli] = {x1,x2,y1,1};
		hx[++tli] = x2;
		line[tli] = {x1,x2,y2,-1};
	}
	sort(hx+1,hx+tli+1);
	sort(line+1,line+tli+1,cmp);
	thx = 1;
	for(int i=2;i<=tli;i++){
		if(hx[i] != hx[i-1]) hx[++thx] = hx[i];
	}
	LL ans = 0;
	for(int i=1;i<tli;i++){
		LL l = lower_bound(hx+1,hx+thx+1,line[i].xl) - hx;
		LL r = lower_bound(hx+1,hx+thx+1,line[i].xr) - hx -1;
		update(l,r,1,thx-1,1,line[i].g);
		ans += sum[1]*(line[i+1].y - line[i].y);
	}
	cout << ans << endl;
	
	

	return 0;
}

Prev
2021-03-15 22:09:00 # ACM
Next