题目原网址:http://poj.org/problem?id=1177
题目中文翻译:
解题思路:
总体思路:
1.沿X轴离散化建树
2.按Y值从小到大排序平行与X轴的边,然后顺序处理
如果遇到矩形下面那条边则插入到线段树中,遇到矩形上面的边则将相应的边删除掉
根据线段树当前的状态统计长度
第二点是本题的核心思想,偶再举个例:
第一次求出的部分很好理解.
第二次求出的为什么会少了中间那部分.那是因为插入的新线段覆盖了第一条,此时线段树返回的长度是新的那一条的长度,将这个值再减去上次的就少了中间那部分
第三次因为是矩形的上边,所以要删除在那条长的线段.此时的线段树返回的则是第一次的长度,将此值减去第二次返回值,再取其负值就是红色X轴那部分了
最后那条X轴的,再补上就行了.
需要注意的就是离散化以后一定要去掉重复元素，否则会出错的。
转载自:传送门
AC代码:
#include<cstdio>
#include<iostream>
#include<algorithm> using namespace std; struct kkk {
int l,r;//线段树表示区间范围
int cnt;//有效长度
int lf,rf;//实际左右端点
int numseg;//分支数,一个分支对应两条竖线
int c;//记录覆盖情况
bool lc,rc;//左右半覆盖情况
}s[]; struct ll {
int y;
int x1,x2;
int f;//表示出入边,入边为1,出边为-1(自己想想为什么)
}l[]; int x[]; bool cmp(ll a,ll b) {
return a.y < b.y;
} void build(int i,int le,int r) {//建树
s[i].l = le;
s[i].r = r;
s[i].lf = x[le];
s[i].rf = x[r];
s[i].cnt = ;
s[i].numseg = ;
s[i].c = ;
s[i].lc = s[i].rc = false;
if(le + == r) return ;
int mid = (le + r) / ;
build(i << ,le,mid);
build((i << ) | ,mid,r);
} void calen(int i) {//计算长度
if(s[i].c > ) {
s[i].cnt = s[i].rf - s[i].lf;
s[i].numseg = ;
s[i].lc = s[i].rc = true;
return ;
}
if(s[i].l + == s[i].r) {
s[i].cnt = ;
s[i].numseg = ;
s[i].lc = s[i].rc = false;
}
else {
s[i].cnt = s[i<<].cnt + s[(i<<)|].cnt;
s[i].lc = s[i<<].lc;
s[i].rc = s[(i<<)|].rc;
s[i].numseg = s[i<<].numseg + s[(i<<)|].numseg;
if(s[i<<].rc&&s[(i<<)|].lc) s[i].numseg--;
}
} void update(int i,ll e) {
if(s[i].lf == e.x1 && s[i].rf == e.x2) {
s[i].c += e.f;
calen(i);
return ;
}
if(e.x2 <= s[i<<].rf) update(i << ,e);
else if(e.x1 >= s[(i<<)|].lf) update((i<<) | ,e);
else {
ll temp = e;
temp.x2 = s[i<<].rf;
update(i << ,temp);
temp = e;
temp.x1 = s[i<<|].lf;
update((i<<)|,temp);
}
calen(i);
} int main()
{
int x1,y1,x2,y2;
int n;
while(scanf("%d",&n) == ) {
int t = ;
for(int i = ;i < n; i++) {
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
l[t].x1 = x1;
l[t].x2 = x2;
l[t].y = y1;
l[t].f = ;
x[t++] = x1;
l[t].x1 = x1;
l[t].x2 = x2;
l[t].y = y2;
l[t].f = -;
x[t++] = x2;
}
sort(l,l+t,cmp);
sort(x,x+t);
int m = unique(x,x+t) - x;
build(,,m-);
int ans = ;
int last = ;
for(int i = ;i < t - ; i++) {
update(,l[i]);
ans += s[].numseg * * (l[i+].y - l[i].y);
ans += abs(s[].cnt - last);
last = s[].cnt;
}
update(,l[t-]);
ans += abs(s[].cnt - last);
printf("%d\n",ans);
}
return ;
}