D - Mayor's posters——线段树区间覆盖+离散化

叁歲伎倆 2022-06-11 09:39 147阅读 0赞

Think:  
1知识点：线段树区间覆盖+离散化  
2题意分析：竞选人需要在墙上贴宣传海报，海报高度相同宽度不一定相同，按照时间轴会出现覆盖，给定按照时间轴海报的起始位置和终止位置，询问在最终状态会展现多少海报，n(\[1, 10000\])，(li, ri)(\[1, 10000000\])，参考前辈博客，因l(ri-li+1)与n差值较大，因此需要离散化  
eg1：  
离散化前坐标：\[1,6\] \[1.7\] \[2,10\] \[8 18\]  
排序：1 1 2 6 7 8 10 18  
离散化： 1 2 3 4 5 6 7  
离散化后坐标：\[1,3\] \[1,4\] \[2,6\] \[5,7\]  
进而再逆着判断，这样只需判断当前结点区间是否已经覆盖即可  
3反思：注意数组不要开的过小

[vjudge题目链接][vjudge]

以下为Accepted代码

/*线段树区间覆盖+离散化*/
    #include <cstdio>
    #include <cstring>
    #include <algorithm>
    
    using namespace std;
    
    const int N = 11400;
    
    struct Node{
        int id, x;
    }node[N<<1];
    
    struct Tree{
        int l, r, vis;
    }tree[N<<3];
    
    int flag;
    
    void Build(int l, int r, int rt);/*初始建树*/
    void find(int L, int R, int rt);/*区间覆盖信息查询*/
    void Updata(int rt);/*树结点信息更新*/
    bool cmp1(struct Node a, struct Node b);
    bool cmp2(struct Node a, struct Node b);
    
    int main(){
        int T, n, i, ans;
        scanf("%d", &T);
        while(T--){
            scanf("%d", &n);
            for(i = 1; i <= n<<1; i += 2){
                scanf("%d %d", &node[i].x, &node[i+1].x);
                node[i].id = node[i+1].id = i;
            }
            sort(node+1, node+1+(n<<1), cmp1);
            int pre = 0, cnt = 0;
            for(i = 1; i <= n<<1; i++){
       /*离散化*/
                if(node[i].x == pre){
                    node[i].x = cnt;
                }
                else {
                    pre = node[i].x;
                    node[i].x = ++cnt;
                }
            }
            Build(1, n<<1, 1);/*2倍n——why?*/
            sort(node+1, node+1+(n<<1), cmp2), ans = 0;
            for(i = 1; i <= n<<1; i += 2){
       /*逆贴，判断查询区间是否已经覆盖即可*/
                flag = 0;
                find(node[i].x, node[i+1].x, 1);
                if(flag) ans++;
            }
            printf("%d\n", ans);
        }
        return 0;
    }
    bool cmp1(struct Node a, struct Node b){
        return a.x < b.x;
    }
    bool cmp2(struct Node a, struct Node b){
        if(a.id != b.id) return a.id > b.id;
        else return a.x < b.x;
    }
    void Build(int l, int r, int rt){
       /*初始建树*/
        tree[rt].l = l;
        tree[rt].r = r;
        tree[rt].vis = 0;
        if(tree[rt].l == tree[rt].r)
            return;
        int mid = (l+r)>>1;
        Build(l, mid, rt<<1);
        Build(mid+1, r, rt<<1|1);
    }
    void find(int l, int r, int rt){
       /*区间覆盖信息查询*/
        if(tree[rt].vis)
            return;
        if(tree[rt].l == l && tree[rt].r == r){
            tree[rt].vis = 1, flag = 1;
            return;
        }
        int mid = (tree[rt].l+tree[rt].r)>>1;
        if(r <= mid)
            find(l, r, rt<<1);
        else if(l > mid)
            find(l, r, rt<<1|1);
        else {
            find(l, mid, rt<<1);
            find(mid+1, r, rt<<1|1);
        }
        Updata(rt);
    }
    void Updata(int rt){
       /*树结点信息更新*/
        tree[rt].vis = tree[rt<<1].vis & tree[rt<<1|1].vis;
    }

[vjudge]: https://vjudge.net/contest/163011#problem/D