线段树

\(O(nlogn)\)

本来是做过这道题的，原题是POJ2528 Mayor's posters

但是POJ上的数据有问题，导致我以为自己AC了。像这种区间的题尤其要注意离散化时要离散化左右边界

举个洛谷上的例子

当出现这种情况[5,7],[1,5],[7,8]按顺序覆盖的话，就会出问题：

离散化为区间[2,3],[1,2],[3,4]那么按这样覆盖就会把第一张海报覆盖掉，但实际上第一张海报没有完全被覆盖
那该怎么办？solution：在每个离散区间中强行加一个点比如说在[1,5]加上2，[5,7]加上6，[7,8]由于是相邻的所以不要加

这样问题就解决了

回顾这道题，因为是区间修改，所以可以用线段树。查询答案时既可以递归到叶子节点再返回，也可以遇到一个有颜色的区间便返回。在维护上传标记时，若左右儿子颜色相同才上传，否则不上传

这是修改后的代码

#include<bits/stdc++.h>
using namespace std;
#define go(i,a,b) for(int i=(a);i<=(b);++(i))
#define com(i,a,b) for(int i=(a);i>=(b);--(i))
#define mem(a,b) memset((a),(b),sizeof(a))
#define inf 0x3f3f3f3f
#define fin freopen("input.txt","r",stdin)
#define fout freopen("output.txt","w",stdout)
typedef long long ll;
const int maxn=10008;
struct tree{
    int l,r,co;
    #define l(x) t[x].l
    #define r(x) t[x].r
    #define co(x) t[x].co
    #define lson rt<<1
    #define rson rt<<1|1
}t[maxn*8];
int n,m,ans,sad[maxn*2],rk[maxn*2],tot=0,l[maxn],r[maxn],vis[maxn];
bool flag[maxn];

void read(int &x){
    int f=1;char s=getchar();x=0;
    while(!isdigit(s)){if(s=='-') f=-1;s=getchar();}
    while(isdigit(s)){x=(x<<3)+(x<<1)+s-'0';s=getchar();}
    x*=f;
}

void build(int rt,int l,int r){
    l(rt)=l,r(rt)=r;
    if(l==r){
        return;
    }
    int mid=l+r>>1;
    build(lson,l,mid);
    build(rson,mid+1,r);
}

void push_up(int rt){
    if(co(lson)==co(rson)) co(rt)=co(lson);
    else co(rt)=-1;
}
void push_down(int rt){
    if(co(rt)!=-1&&co(rt)!=0){
        co(lson)=co(rt);
        co(rson)=co(rt);
        co(rt)=0;
    }
}

void update(int rt,int x,int y,int val){
    if(l(rt)>=x&&r(rt)<=y){
        co(rt)=val;
        return;
    }
    push_down(rt);
    int mid=l(rt)+r(rt)>>1;
    if(x<=mid) update(lson,x,y,val);
    if(y>mid) update(rson,x,y,val);
    push_up(rt);
}

void get_ans(int rt){
    if(co(rt)>0){
        flag[co(rt)]=1;
        return;
    }
    if(l(rt)==r(rt)) return;
    get_ans(lson),get_ans(rson);
}

int main(){
    //fin;
    int T;read(T);
    while(T--){
        mem(flag,0);
        read(m);
        ans=tot=0;
        mem(vis,0);
        go(i,1,m){
            read(l[i]),read(r[i]);
            sad[++tot]=l[i],rk[tot]=l[i];
            sad[++tot]=r[i],rk[tot]=r[i];
            sad[++tot]=l[i]+1,rk[tot]=l[i]+1;
            sad[++tot]=r[i]+1,rk[tot]=r[i]+1;
            sad[++tot]=l[i]-1,rk[tot]=l[i]-1;
            sad[++tot]=r[i]-1,rk[tot]=r[i]-1;
        }
        sort(sad+1,sad+tot+1);
        tot=unique(sad+1,sad+tot+1)-sad-1;
        go(i,1,m){
            l[i]=lower_bound(sad+1,sad+tot+1,l[i])-sad;
            r[i]=lower_bound(sad+1,sad+tot+1,r[i])-sad;
            int f=1;
        }
        build(1,1,tot);
        go(i,1,m){
            update(1,l[i],r[i],i);
        }
        get_ans(1);
        go(i,1,m) ans+=flag[i];
        printf("%d\n",ans);
    }
    return 0;
}