重叠的装饰

https://www.nowcoder.com/practice/a502e49967b44036918d93ff43be1930?tpId=98&tqId=32871&tPage=3&rp=3&ru=/ta/2019test&qru=/ta/2019test/question-ranking

题目难度：四星
考察点：线段树、区间覆盖、离散化

方法：线段树、区间覆盖

1.分析：

这道题是一个线段树区间覆盖类型的题目，通过题目我们知道，在贴海报的过程中，后面贴的海报会影响前面的海报，即前面的海报会被覆盖。所以这其实就是一个区间的更新，即来一个区间[l,r]，我们对其进行update。所需要的知识就是线段数的区间更新。这一类题目也可以理解为是线段的互相覆盖，在更新过程中，动态的获取线段的并或者是区间的个数等等信息。那么在这里说一下怎么进行的区间覆盖，对于第i个区间[l,r]来说，相当于是利用i来表示覆盖的海报，所以就是相当于对[l,r]进行覆盖，即即如果满足条件的话 lazy[root] = i，进行lazy标记，所谓的lazy标记就是指在递归的过程中，如果当前区间被需要修改的区间完全覆盖，那么就要停止递归，并且在上面做一个标记。当我们套完线段树lazy区间修改模板时，发现竟然段错误了。这是为什么呢？这是由于输入的区间太大，所以不能用线段树来完全的表示，如果想用线段树来完全的表示就会MLE，所以怎么办呢？

这里介绍一个神奇的算法离散化，是一个可以节省空间的神奇算法，离散化是对一堆元素进行操作，通过改变他们的大小，但不改变他们的大小关系来达到节省空间，减低时空复杂度的。举个例子:

现在有一个数组{4,8,10,20}，我们可以计算用一个下标为{1, 2, 3, 4}的数组来表示，我们可以用一个更小的数来表达这种大小的关系。

比如说现在有一个数组{4,8,10,6}，下标为{1, 2, 3, 4}，首先对其进行排序得到:

数组值： 4 6 8 10

下标值： 1 4 2 3

经过离散化之后得到：

数组值： 4 6 8 10

下标值： 1 4 2 3

离散化： 1 2 3 4

在将其转到原序列之后：

数组值： 4 8 10 6

离散化后： 1 4 2 3

其实在这道题中，我们就可以采用STL的方法来进行离散化，将所有的区间的左右端点放在一个数组中，然后排序去重，最后在进行lower_bound找到对应的端点所在的下标即可，具体可详见代码。

算法步骤：

(1). 输入n和相应的n个区间，

(2). 将得到的区间排序去重，进行离散化

(3). 构造线段树，进行区间覆盖

(4). 输出结果。

2.复杂度分析：

时间复杂度：O(nlog(n))
空间复杂度：O(n)

3.代码：

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e6+5;
int lazy[MAXN*3];
bool book[MAXN*3];
void pushdown(int root){
    if(lazy[root] != -1){
        lazy[root<<1] = lazy[root];
        lazy[root<<1|1] = lazy[root];
        lazy[root] = -1;
    }
}
void update(int L, int R, int flag, int l, int r, int root){
    if(L<=l && R>=r){
        lazy[root] = flag;
        return;
    }
    pushdown(root);
    int mid = (l + r)>>1;
    if(L <= mid) update(L,R,flag,l,mid,root<<1);
    if(R > mid) update(L,R,flag,mid+1,r,root<<1|1);
}
struct Node {
    int x, y;
    Node(){}
    Node(int xx, int yy) {x = xx, y = yy;}
}a[MAXN];
int query(int l, int r, int root){
    if(lazy[root] != -1){
        if(book[lazy[root]]) return 0;
        book[lazy[root]] = true;
        return 1;
    }
    if(l == r) return 0;
    int mid = (l + r)>>1, ans = 0;
    ans += query(l,mid,root<<1);
    ans += query(mid+1,r,root<<1|1);
    return ans;
}
int main(){
    memset(lazy, -1, sizeof(lazy));
    int n; cin>>n;
    vector<int> vec;
    for(int i=0; i<n; i++) {
        int x, y; cin>>x>>y;
        a[i] = Node(x, y);
        vec.push_back(x);
        vec.push_back(y);
    }
    sort(vec.begin(), vec.end());
    vec.erase(unique(vec.begin(), vec.end()), vec.end());
    for(int i=1; i<=n; i++) {
        int l = lower_bound(vec.begin(), vec.end(), a[i-1].x)-vec.begin()+1;
        int r = lower_bound(vec.begin(), vec.end(), a[i-1].y)-vec.begin()+1;
        update(l, r, i, 1, 3*n,1);
    }
    cout<<query(1, 3*n, 1);
    return 0;
}