【详解】Mayor's posters POJ - 2528(线段树区间染色离散化) ⭐⭐⭐⭐

最新推荐文章于 2025-04-23 20:29:15 发布

Suprit

最新推荐文章于 2025-04-23 20:29:15 发布

阅读量656

点赞数 1

分类专栏： # 数据结构

本文链接：https://blog.csdn.net/a1097304791/article/details/89740365

版权

数据结构专栏收录该内容

51 篇文章

订阅专栏

Mayor’s posters POJ - 2528

n（n<=10000) 个人依次贴海报,给出每张海报所贴的范围li，ri（1<=li<=ri<=10000000) 。求出最后还能看见多少张海报。

Input

第一行: 样例个数T
第二行: 贴海报的人n
第三行: 每个人贴海报的范围
接下来n行: 每个人贴海报的范围

Output

对于每一个输入，输出最后可以看到的海报张数。下面这个图是样例解释在这里插入图片描述

Examples

Sample Input
1
5
1 4
2 6
8 10
3 4
7 10
Sample Output
4

Hint

题意:

题解:

针对线段树区间染色的问题这里不再赘述, 可以参考博客
重点说以下离散化的问题.
离散化经常与线段树混合使用, 对于一些比较大的数据, 我们通过区间压缩映射, 过滤掉其中一些无用的区间.
例如对于本题来说, 10000000这个数太大了, 铁定超时.
而我们仔细考虑, 因为最大只有1000个人贴海报, 所以即时每个人贴的海报的区间都不一样, 最多最多也就只有2000个区间, 这个时候, 我们完全可以对区间进行压缩, 因为我们只关心最后能看到几张海报, 而不关心具体的范围.
例如对于样例来说, 我们将其排序
1 2 3 4 6 7 8 10 (样例)
1 2 3 4 5 6 7 8 (压缩, 其实就是下标对应)
然后依次操作, 每次更新二分搜索新的区间即可.

但是!
这么做还有一个问题, 就是由于我们是紧紧挨着压缩的, 所以可能会存在错误覆盖的问题
例如对于数据
3
1 10
1 3
7 10
我们压缩过后应该就变为
1 4
1 2
3 4
可这样的话我们目测一下, 就只有2个区间可以看到了, 第一个被盖住了. 而真正的答案应该是3才对
这是我们应该在离散化数组c中存储时考虑将每次的右边界r+1也存入, 这样就可以有效避免错误覆盖的问题

经验小结:

灵活使用离散化
数组最好开大点, 开小了莫名RE

#include <cstdio>
#include <cstring>
#include <algorithm>
#define lc p<<1,s,mid
#define rc p<<1|1,mid+1,e
#define mid ((s+e)>>1)
#define CLR(A) memset(A,0,sizeof(A))
using namespace std;
 
const int N = 20005;
int col[N * 4], vis[N];
int le[N], ri[N], c[N * 2], ans;
 
void pushdown(int p)
{
    if(col[p] == -1) return;
    col[p << 1] = col[p << 1 | 1]  = col[p];
    col[p] = -1;
}
 
void update(int p, int s, int e, int l, int r, int v)
{
    if(s >= l && e <= r)
    {
        col[p] = v;
        return;
    }
    pushdown(p);
    if(l <= mid) update(lc, l, r, v);
    if(r > mid) update(rc, l, r, v);
}
 
void query(int p, int s, int e)
{
    if(col[p] != -1)
    {
        if(!vis[col[p]])
            vis[col[p]] = 1, ++ans;
        return;
    }
    query(lc);
    query(rc);
}
 
int compress(int n) //离散化
{
    int k = 0;
    for(int i = 0; i < n; ++i)
    {
        c[k++] = le[i];
        c[k++] = ri[i];
        c[k++] = ri[i] + 1;
    }
    sort(c, c + k);
    return unique(c, c + k) - c - 1;
}
 
int main()
{
    int cas, m, n, l, r;
    scanf("%d", &cas);
    while(cas--)
    {
        scanf("%d", &m);
        for(int i = 0; i < m; ++i)
            scanf("%d%d", &le[i], &ri[i]);
        n = compress(m);
 
        ans = 0;
        CLR(col), CLR(vis);
        for(int i = 0; i < m; ++i)
        {
            l = lower_bound(c, c + n, le[i]) - c + 1;
            r = lower_bound(c, c + n, ri[i]) - c + 1;
            update(1, 1, n, l, r, i + 1);
        }
        vis[0] = 1;
        query(1, 1, n);
        printf("%d\n", ans);
    }
    return 0;
}