题目:http://poj.org/problem?id=2528
题意:有一面墙,被等分为1QW份,一份的宽度为一个单位宽度。现在往墙上贴N张海报,每张海报的宽度是任意的,
但是必定是单位宽度的整数倍,且<=1QW。后贴的海报若与先贴的海报有交集,后贴的海报必定会全部或局部覆盖
先贴的海报。现在给出每张海报所贴的位置(左端位置和右端位置),问张贴完N张海报后,还能看见多少张海报?
(离散化)+ 线段树
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = +;
int n, cnt;
int map[*maxn][], ans, f[*maxn];
struct node
{
int l, r, n; //n代表是哪种颜色
} a[*maxn];
struct node2
{
int point, num; //原来点的编号, 新编的号
} s[*maxn];
void init(int l, int r, int i) //建树
{
a[i].l = l;
a[i].r = r;
a[i].n = ;
if(l != r)
{
int mid = (l+r)/;
init(l, mid, *i);
init(mid+, r, *i+);
}
}
void insert(int i, int l, int r, int m)//从第i个点,查找区间【l,r】,并把颜色标记为m
{
if(a[i].l == l && a[i].r == r)
{
a[i].n = m;
return;
}
int mid = (a[i].l+a[i].r)/;
if(a[i].n>) //颜色已有,对其子树赋值
{
a[*i].n = a[i].n;
a[*i+].n = a[i].n;
a[i].n = ;
}
if(l >= a[*i+].l)
insert(*i+, l, r, m);
else if(r <= a[*i].r)
insert(*i, l, r, m);
else
{
insert(*i, l, mid, m);
insert(*i+, mid+, r, m);
}
}
void solve(int i)
{
if(a[i].n)
{
if(!f[a[i].n])
{
ans++;
f[a[i].n] = ;
}
return;
}
solve(*i);
solve(*i+);
}
int cmp(node2 x, node2 y)
{
return x.point<y.point;
} int main()
{
int t, i, tmp, cnt;
scanf("%d", &t);
while(t--)
{
scanf("%d", &n);
for(i = ; i < n; i++)
{
scanf("%d%d", &map[i][], &map[i][]);
s[i*].point = map[i][];
s[i*+].point = map[i][];
s[*i].num = -(i+);
s[*i+].num = i+;
}
sort(s, s+*n, cmp);
tmp = s[].point;
cnt = ;
for(i = ; i < *n; i++)
{
if(tmp != s[i].point)
{
cnt++;
tmp = s[i].point;
}
if(s[i].num < )
map[-s[i].num-][] = cnt;
else
map[s[i].num-][] = cnt;
}
init(, cnt, );
for(i = ; i < n; i++)
insert(, map[i][], map[i][], i+);
memset(f, , sizeof(f));
ans = ;
solve();
printf("%d\n",ans);
}
return ;
}