【POJ】2528 Mayor's posters 题解

题目大意

在只考虑长度的情况下，先后放置 $n$ 个海报，每个海报的范围是 $[l, r]$ 会覆盖下面的海报，问最后能看到几个海报。

题目链接

思路

我们可以用一个数组来表示整个区间，每次放新的海报（第 $i$ 张），就把对应区间的数字改为 $i$。

而这种区间修改我们可以直接用线段树来做（珂朵莉树也可以）

而由于区间范围比较大，我们要离散化区间。

另外需要注意的是，由于是区间覆盖问题，所以普通离散化会出问题，比如：

$[1,6],[1,3],[5,6]$ 离散化后会变为 $[1,4],[1,2],[3,4]$，这样一来，原来第一个区间就会被完全覆盖。

这是因为，离散化操作让不相邻的点变得相邻了，这在普通问题中没有什么影响，但是在区间覆盖问题上就变得很关键了。所以我们要在离散化数组中，插入 $r[i]+1$，防止后续不相邻的点在离散化后和它相邻（$l[i], r[i]$ 是否相邻没有什么影响）。

线段树中的 tag 就相当于懒标记，表示这个区间的数被修改成了同一个数，那么查询的时候就不用下放了，因为我们是统计有多少个海报。

代码

#include <cstdio>
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;

const int maxN = 1e5 + 7;

struct Tree {
    int l, r, color, tag;
}t[maxN << 4];

int T, n, l[maxN], r[maxN], vis[maxN], ans;

vector<int> pos;

inline int getPos(int x)
{
    return lower_bound(pos.begin(), pos.end(), x) - pos.begin(); 
}

void build(int l, int r, int num)
{
    t[num].l = l; t[num].r = r;
    t[num].color = 0;
    t[num].tag = -1;
    if(l == r)
        return ;
    int mid = (l + r) >> 1;
    build(l, mid, num << 1);
    build(mid + 1, r, num << 1 | 1);
}

void spread(int num)
{
    if(t[num].tag != 0) {
        t[num << 1].color = t[num].color;
        t[num << 1 | 1].color = t[num].color;
        t[num << 1].tag = t[num << 1 | 1].tag = 1;
        t[num].tag = 0;
    }
}

void change(int l, int r, int num, int x)
{

    if(l <= t[num].l && r >= t[num].r) {
        t[num].color = x;
        t[num].tag = 1;    
        return ;
    }
    spread(num);
    int mid = (t[num].l + t[num].r) >> 1;
    if(l <= mid)
        change(l, r, num << 1, x);
    if(r > mid)
        change(l, r, num << 1 | 1, x);
}

void query(int l, int r, int num)
{
    if(t[num].tag == -1)
        return ;
    if(t[num].tag != 0) {
        if(!vis[t[num].color] && t[num].color != 0) {
            ++ans;
            vis[t[num].color] = 1;
        }
        return ;
    }
    int mid = (l + r) >> 1;
    query(l, r, num << 1); query(l, r, num << 1 | 1);
}

int main()
{
    scanf("%d", &T);
    while(T--) {
        scanf("%d", &n);
        ans = 0;
        memset(vis, 0, sizeof vis);
        pos.clear(); pos.push_back(0);
        for(int i = 1; i <= n; ++i) {
            scanf("%d%d", &l[i], &r[i]);
            pos.push_back(l[i]);
            pos.push_back(r[i]);
            pos.push_back(r[i] + 1);
        }
        sort(pos.begin(), pos.end());
        pos.erase(unique(pos.begin(), pos.end()), pos.end());
        int len = pos.size() , cnt = 0;
        build(1, len, 1);
        for(int i = 1; i <= n; ++i) {
            l[i] = getPos(l[i]); r[i] = getPos(r[i]);
            change(l[i], r[i], 1, ++cnt);
        }
        query(1, len, 1);
        printf("%d\n", ans);
    }
    return 0;
}