P1856

发表于 分类于
[IOI1998] [USACO5.5] 矩形周长Picture

[IOI1998] [USACO5.5] 矩形周长Picture

求一个周长并。

实际上一开始想真的有一定难度。

我们同样是作离散化和扫描，垂直于扫描线的线段可以直接通过区间被割断的段数（可以在线段树上维护）来维护处理。

问题是怎么处理平行的这些个线段。

因为重叠等等的问题，这个东西没有想象中那么的容易。

一个好的想法是，分开单个位置上的区间加和区间减操作，然后统计这个操作位置与上一个操作位置之间的竖直线段长度之差。

可以这样想，重叠的线段在这里被处理掉了，不需要再考虑。作差实际上就是把裸露的那几段线段给统计上了。

我也解释不清楚。

所以有没有大爷来救救孩子啊？

时间复杂度 $O(n\log n)$。

代码：

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
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#define ll long long
using namespace std;

const ll N=1e4;

ll n,tot,totx,toty,ans,lastlen;

ll xa[N+5],xb[N+5],ya[N+5],yb[N+5];

ll uqx[N+5],uqy[N+5];

struct sgt{
	ll l,r,cnt,len,num;
	bool lf,rf;
	#define l(x) tree[x].l
	#define r(x) tree[x].r
	#define cnt(x) tree[x].cnt
	#define len(x) tree[x].len
	#define num(x) tree[x].num
	#define lf(x) tree[x].lf
	#define rf(x) tree[x].rf
}tree[N*4+5];

void update(ll p) {
	if(cnt(p)>0) {
		len(p)=uqy[r(p)+1]-uqy[l(p)];
		num(p)=1;lf(p)=1;rf(p)=1;
	}
	else
	if(l(p)==r(p)) {
		len(p)=0;num(p)=0;lf(p)=0;rf(p)=0;
	}
	else {
		len(p)=len(p<<1)+len(p<<1|1);
		num(p)=num(p<<1)+num(p<<1|1);
		lf(p)=lf(p<<1);rf(p)=rf(p<<1|1);
		if(rf(p<<1)&&lf(p<<1|1)) num(p)--;
	}
}

void build(ll p,ll l,ll r) {
	l(p)=l;r(p)=r;
	if(l==r) {return;}
	ll mid=(l+r)>>1;
	build(p<<1,l,mid);build(p<<1|1,mid+1,r);
}

void add(ll p,ll l,ll r,ll k) {
	if(l(p)>=l&&r(p)<=r) {
		cnt(p)+=k;
		update(p);
		return;
	}
	ll mid=(l(p)+r(p))>>1;
	if(l<=mid) add(p<<1,l,r,k);
	if(r>mid) add(p<<1|1,l,r,k);
	update(p);
}

struct node{
	ll l,r,pos,v;
	bool operator < (const node& rhs) const {
		return pos==rhs.pos?(v>rhs.v):(pos<rhs.pos);
	}
}a[N*2+5];

inline ll read() {
	ll ret=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9') {if(ch=='-') f=-f;ch=getchar();}
	while(ch>='0'&&ch<='9') {ret=(ret<<3)+(ret<<1)+ch-'0';ch=getchar();}
	return ret*f;
}

inline void write(ll x) {
	static char buf[22];static ll len=-1;
	if(x>=0) {
		do{buf[++len]=x%10+48;x/=10;}while(x);
	}
	else {
		putchar('-');
		do{buf[++len]=-(x%10)+48;x/=10;}while(x);
	}
	while(len>=0) putchar(buf[len--]);
}

int main() {

	n=read();

	for(ll i=1;i<=n;i++) {
		xa[i]=read();ya[i]=read();xb[i]=read();yb[i]=read();
		uqx[++totx]=xa[i];uqx[++totx]=xb[i];
		uqy[++toty]=ya[i];uqy[++toty]=yb[i];
	}

	sort(uqx+1,uqx+totx+1);totx=unique(uqx+1,uqx+totx+1)-uqx-1;
	sort(uqy+1,uqy+toty+1);toty=unique(uqy+1,uqy+toty+1)-uqy-1;

	for(ll i=1;i<=n;i++) {
		xa[i]=lower_bound(uqx+1,uqx+totx+1,xa[i])-uqx;
		ya[i]=lower_bound(uqy+1,uqy+toty+1,ya[i])-uqy;
		xb[i]=lower_bound(uqx+1,uqx+totx+1,xb[i])-uqx;
		yb[i]=lower_bound(uqy+1,uqy+toty+1,yb[i])-uqy;
		a[++tot].pos=xa[i];a[tot].l=ya[i];a[tot].r=yb[i];a[tot].v=1;
		a[++tot].pos=xb[i];a[tot].l=ya[i];a[tot].r=yb[i];a[tot].v=-1;
	}

	sort(a+1,a+tot+1);

	build(1,1,toty-1);

	for(ll i=1;i<=tot;i++) {
		add(1,a[i].l,a[i].r-1,a[i].v);
		if(a[i].pos==a[i+1].pos&&a[i].v==a[i+1].v) continue;
		ans+=num(1)*2*(uqx[a[i+1].pos]-uqx[a[i].pos]);
		ans+=abs(lastlen-len(1));
		lastlen=len(1);
	}

	write(ans);

	return 0;
}