题意：很多张海报贴在墙上 求可以看到几张海报 看那两张图就行了 第一张俯视图
思路：最多2W个不同的数 离散化一下 然后成段更新 a[rt] = i代表这个区间是第i张报纸 更新玩之后一次query cover[i]=1代表可以看到第i张报纸
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int maxn = 20010;
int a[maxn<<2];
int cover[maxn<<2];
struct Point
{
int x, id, v;
}b[maxn];
int n;
bool cmp1(Point a, Point b)
{
return a.x < b.x;
}
bool cmp2(Point a, Point b)
{
return a.id < b.id;
}
void build(int l, int r, int rt)
{
a[rt] = 0;
//printf("%d %d\n", l, r);
if(l+1 == r)
return;
int m = (l + r) >> 1;
build(l, m, rt<<1);
build(m, r, rt<<1|1);
}
void update(int x, int y, int l, int r, int rt, int num)
{
if(l == x && r == y)
{
a[rt] = num;
return;
}
int m = (l + r) >> 1;
if(a[rt])
{
a[rt<<1] = a[rt];
a[rt<<1|1] = a[rt];
a[rt] = 0;
}
if(y <= m)
update(x, y, l, m, rt<<1, num);
else if(x >= m)
update(x, y, m, r, rt<<1|1, num);
else
{
update(x, m, l, m, rt<<1, num);
update(m, y, m, r, rt<<1|1, num);
}
}
void query(int l, int r, int rt)
{
if(l+1 == r || a[rt])
{
cover[a[rt]] = 1;
//printf("%d\n", a[rt]);
return;
}
int m = (l + r) >> 1;
if(a[rt])
{
a[rt<<1] = a[rt];
a[rt<<1|1] = a[rt];
a[rt] = 0;
}
query(l, m, rt<<1);
query(m, r, rt<<1|1);
}
int main()
{
int T;
scanf("%d", &T);
while(T--)
{
scanf("%d", &n);
for(int i = 0; i < n; i++)
{
scanf("%d %d", &b[i<<1].x, &b[i<<1|1].x);
b[i<<1|1].x++;
b[i<<1].id = i<<1;
b[i<<1|1].id = i<<1|1;
}
sort(b, b+2*n, cmp1);
int now = b[0].x;
int sum = 1;
for(int i = 0; i < 2*n; i++)
{
if(b[i].x != now)
{
now = b[i].x;
sum++;
}
b[i].v = sum;
}
sort(b, b+2*n, cmp2);
//printf("%d\n", sum);
//memset(a, 0, sizeof(a));
build(1, sum, 1);
//puts("sdsf");
for(int i = 0; i < n; i++)
{
//printf("**%d %d\n", b[i<<1].v, b[i<<1|1].v);
update(b[i<<1].v, b[i<<1|1].v, 1, sum, 1, i+1);
//puts("ddsf");
}
memset(cover, 0, sizeof(cover));
query(1, sum, 1);
int ans = 0;
for(int i = 1; i <= n; i++)
if(cover[i])
ans++;
printf("%d\n", ans);
}
return 0;
}