题目链接

http://poj.org/problem?id=2528

解题思路

我参考的大佬代码
我算是照着大佬代码思路自己打了一遍，其中注释掉的代码部分是我自己写的，没大佬的牛逼。
我代码比较好的地方就是离散化用的是经典离散化的方式，好理解点， 离散化入门
大致思路：
因为我们并不考虑具体修改的区域，所以只需要保存每个修改区间左右端点的相对位置；对原来的左右端点的位置进行重新赋值。
构造线段树，包括构造线段树结构体数组的变量及含义，以及在PushDown操作中如何下传标记，在Update操作中如何对线段树结构体数组的变量赋值，等等一些细节问题。
定义Query函数，用于计算不同的海报数。（因为我们并不是直接通过线段树的变量存储的每个区间不同的海报数，所以要通过Query数组实现）

AC代码

#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;

const int N=1e5+10;//开大点，第一次就因为开小了，wa了 

int T,n,x,y,ans,num,a[N],b[N],vis[N];
struct TREE
{
    int l,r;
    int lazy;//lazy=1表示为单***域，lazy=0表示不为单***域 
    int col;//col表示区域颜色，仅在单色时有效，即仅在lazy=1时有效    
}tr[N];

void Build(int i,int l,int r)
{
    tr[i].l=l;
    tr[i].r=r;
    tr[i].lazy=0;//无颜色填充 or 填充颜色存在不同 
    tr[i].col=0;//无颜色为0
    if(l==r) return ;
    int mid=l+r>>1;
    Build(i<<1,l,mid);
    Build(i<<1|1,mid+1,r); 
}
void PushDown(int i)
{
    if(tr[i].lazy==0) return ;//单***域才能下传标记 
    tr[i<<1].lazy=tr[i<<1|1].lazy=tr[i].lazy;
    tr[i<<1].col=tr[i<<1|1].col=tr[i].col;
    tr[i].lazy=0;
}
void Update(int i,int l,int r,int c)
{
    if(tr[i].col==c && tr[i].lazy==1) return ;//小剪枝//访问到的线段树区域已经是单***域且区域颜色与即将被染颜色相同 
    if(l<=tr[i].l && tr[i].r<=r) 
    {
        tr[i].lazy=1;
        tr[i].col=c;
        return ;
    }
    PushDown(i);
    if(tr[i<<1].r>=l) Update(i<<1,l,r,c);
    if(tr[i<<1|1].l<=r) Update(i<<1|1,l,r,c);
}
/*
void Query(int i,int l,int r)
{
    if(tr[i].lazy==1)//为单***域 
    {
        vis[tr[i].col]=1;//标记一下此颜色出现过 
        return ;
    }
    PushDown(i);
    if(tr[i<<1].r>=l) Query(i<<1,l,r);//访问左子树 
    if(tr[i<<1|1].l<=r) Query(i<<1|1,l,r);//访问右子树 
}
*/
int Query(int i)//大佬的还是牛逼！ 
{
    if(tr[i].lazy==1)//为单***域 
    {
        if(vis[tr[i].col]==1) return 0;//若已经访问过此颜色，返回0 
        else {vis[tr[i].col]=1;return 1;}//若未访问过此颜色，标记此颜色并返回1 
    }
    return Query(i<<1)+Query(i<<1|1);//左子树颜色种数+右子树颜色种数 
}
int main()
{
    scanf("%d",&T);
    while(T--)
    {
        memset(vis,0,sizeof vis);
        ans=0,num=0;

        scanf("%d",&n);
        for(int i=1;i<=n;i++)
        {
            scanf("%d%d",&x,&y);
            a[++num]=x;b[num]=x;
            a[++num]=y;b[num]=y;
        }
        //离散化 
        sort(b+1,b+num+1);
        num=unique(b+1,b+num+1)-b-1;
        for(int i=1;i<=(n<<1);i++)
        a[i]=lower_bound(b+1,b+num+1,a[i])-b;

        Build(1,1,num);

        for(int i=1;i<=(n<<1);i+=2)
        Update(1,a[i],a[i+1],(i>>1)+1);
    //    Query(1,1,num);
    //    for(int i=1;i<=num;i++) if(vis[i]==1) ans++;
        ans=Query(1);

        printf("%d\n",ans);
    }
}

类似题目博客

https://blog.nowcoder.net/n/6679ad456dd847098540da8d14563370