Mayor's posters

题目

有一面墙，现在有M张海报要贴，海报的高度和墙的高度一样，每张海报会给出区间范围[l,r]，问最终墙上可见的海报有多少张？
墙的宽度:

分析

首先这题的墙的范围很大，所以必须离散化，然后在离散化之后的数据上建立线段树。

要点

这题对于染色后连续的区间[l,r]有可能离散化会在建立线段树的时候分开，所以最好在区间[l,r]中间加一个点[l,mid,r]，这样如果染色[l,r]，就会pushdown到[l,mid],[mid+1,r]。 但是数据比较谁水，不加也能过

AC代码（无插点）插点也很简单

#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <string>
#include <cmath>
#include <set>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const ll maxn = 1e5+10;

ll T,M;
set<int> st;
struct node{
    ll l,r,tag;//tag: 海报标记
}tr[4*maxn];
int arr[1000010],tail;//用于离散化
int op[1000010][2];
void pushup(ll u){
    node &fa = tr[u],&L = tr[u*2],&R = tr[u*2+1];
    if(L.tag == R.tag){//海报往上传递
        fa.tag = L.tag;
    }else{
        fa.tag = 0;
    }
}
void pushdown(ll u){
    node &fa = tr[u],&L = tr[u*2],&R = tr[u*2+1];
    if(fa.tag){ //海报往下覆盖
        L.tag = fa.tag;
        R.tag = fa.tag;
    }
}
void build(ll u,ll l,ll r){
    if(l == r){
        tr[u] = {l,r,1};
    }else{
        tr[u] = {l,r};
        ll mid = (l+r)>>1;
        build(u*2,l,mid);
        build(u*2+1,mid+1,r);
        pushup(u);
    }
}
void modify(ll u,ll l,ll r,ll tag){
    if(tr[u].l>=l && tr[u].r<=r){
        tr[u].tag = tag;
    }else{
        pushdown(u);
        ll mid = tr[u].l+tr[u].r>>1;
        if(l<=mid) modify(u*2,l,r,tag);
        if(r>mid) modify(u*2+1,l,r,tag);
        pushup(u);
    }
}
void query(ll u,ll l,ll r){
    if(tr[u].tag){
        st.insert(tr[u].tag);
    }else{
        query(u*2,l,r);
        query(u*2+1,l,r);
    }
}

int ind(int x){
    return lower_bound(arr,arr+tail,x)-arr + 1;//因为线段树管理的下标我是1开始的，所以+1
}
int main(){
    cin>>T;
    while(T--){
        st.clear();
        tail = 0;
        scanf("%lld",&M);
        for(int i = 0;i<M;i++){
            scanf("%d%d",&op[i][0],&op[i][1]);
            arr[tail++] = op[i][0];
            arr[tail++] = op[i][1];
        }
        sort(arr,arr+tail);
        tail = unique(arr,arr+tail)-arr; 
        build(1,1,tail);
        int tag = 1;
        for(int i = 0;i<M;i++){
            modify(1,ind(op[i][0]),ind(op[i][1]),tag); 
            tag++;
        }
        query(1,1,tail);
        cout<<st.size()<<endl;
    }

    return 0;
}