Mayor‘s posters POJ - 2528

题目链接

思路转载

题意：
按给出先后放置n 个海报(会相互覆盖），每个海报的范围是[ l , r ]会覆盖下面的海报，问最后能看到几个海报；

思路：

看到这题可以想到这就是区间染色线段树，一般这种题，在处理, L ,R 区间和query 函数与一般不同，且需要理解懒标记的跟新；

由于区间范围比较大，我们需要离散化区间。(由于题目求最后看到几个区间，故这里离散化不会改变覆盖关系）

但是我们按普通离散化会有问题，

例如 [1 , 6] , [1 , 3] , [5 , 6] 离散化后会变为 [1?, 4] , [1 , 2] , [3 , 4], 这样一来，原来第一个区间就会被完全覆盖。
这是因为，离散化操作让不相邻的点变得相邻了，这在普通问题中没有什么影响，但是在区间覆盖问题上就变得很关键了。
所以我们要在离散化数组中，插入r [ i ] + 1 ,防止后续点不相邻的点在离散化后和它相邻。

(l [ i ] , r [ i ] )是否相邻没有什么影响

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

！！！这种问题一般都是无论是对于根节点查询, 还是区间查询, 查询的条件都只是, 这个点是不是有懒标记的, 有懒标记返回即可且只在更新的时候, 我们下放懒标记,?查询的时候不需要下放懒标记.

#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
using namespace std;
const int N = 1e5 + 10;
bool st[N];
int l[N], r[N];
int ans;
struct node
{
    int l, r;
    int color;
    int tag;
} tr[N << 2];
void change(int u, int k)
{
    tr[u].color = k;
    tr[u].tag = 1;
}
void pushdown(int u) // 向下传递时，-1也能进入，所以tag==-1,代表着这段区间完全没有用过
{
    if (tr[u].tag)
    {
        change(u << 1, tr[u].color);
        change(u << 1 | 1, tr[u].color);
        tr[u].tag = 0;
    }
}
void build(int u, int l, int r)
{
    tr[u] = {l, r, 0, -1};//一般区间染色问题，一开始设成-1，以便与后续query中，不递归无用区间
    if (l == r)
        return;
    int mid = l + r >> 1;
    build(u << 1, l, mid);
    build(u << 1 | 1, mid + 1, r);
}
void modify(int u, int l, int r, int k)
{
    if (tr[u].l >= l && tr[u].r <= r)
    {
        change(u, k);
        return;
    }
    pushdown(u);
    int mid = tr[u].l + tr[u].r >> 1;
    if (l <= mid)
        modify(u << 1, l, r, k);
    if (r > mid)
        modify(u << 1 | 1, l, r, k);
}
void query(int u, int l, int r)
{
    if (tr[u].tag == -1) // 防止无限递归，所以加上这个限制，后者下面的，当然前者更优
        return;
    // if (l == r)
    //   return;
    if (tr[u].tag != 0) // 如果区间存在标记，懒标记在最上面最长的那一层，说明这一段区间都相同，不用递归了
    {
        if (!st[tr[u].color] && tr[u].color != 0)
        {
            ans++;
            st[tr[u].color] = 1;
        }
        return;
    }
    query(u << 1, l, r), query(u << 1 | 1, l, r);
}
void solve()
{
    int n;
    int cnt = 0;
    ans = 0;
    scanf("%d", &n);
    for (int i = 0; i <= 1e5; i++)
        st[i] = 0;
    vector<int> t;
    t.push_back(0);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d%d", &l[i], &r[i]);
        t.push_back(l[i]);
        t.push_back(r[i]);
        t.push_back(r[i] + 1);
    }
    sort(t.begin(), t.end());
    t.erase(unique(t.begin(), t.end()), t.end());
    build(1, 1, t.size());
    for (int i = 1; i <= n; i++)
    {
        int fl = lower_bound(t.begin(), t.end(), l[i]) - t.begin();
        int fr = lower_bound(t.begin(), t.end(), r[i]) - t.begin();
        modify(1, fl, fr, ++cnt);
    }
    query(1, 1, t.size());
    printf("%d\n", ans);
}
int main()
{
    int T;
    T = 1;
    scanf("%d", &T);
    for (int cases = 1; cases <= T; ++cases)
    {
        // cout<<"Case #"<<cases<<": ";
        solve();
    }
    return 0;
}