POJ

题意：
n（n<=10000)个人依次贴海报,给出每张海报所贴的范围li，ri（1<=li<=ri<=10000000) 。求出最后还能看见多少张海报。

分析1

离散化：典型的区间染色问题，可以用线段树求解，但是如果直接建一般的线段树树，会超内存，而且时间复杂度相当危险，可以考虑离散化，但是又有一个坑点就是离散化会破坏区间的连续性。
比如，数据
1
3
1 4
1 1
4 4
这个答案明显是3，但是直接离散化的话答案会输出2；
因此我们再输入排序去重后，需要在临时数组里加入一条语句，之后再排一下序，最后lower_bound() 离散化

if(temp[i]-temp[i-1]>1) temp[++tot]=temp[i-1]+1; //temp[]是用于离散化的临时数组，tot是总数

这样就能解决上面例子区间丢失连续性的问题
（有可能你认为把上面数据里的 1 1改成 1 2 会卡掉这个方法，但是这是必不可能的，因为这个方法是在已经排序去重后使用的，没有理解可以手动模拟一下）；

代码

#include<cstdio>
#include<cctype>
#include<algorithm>
#include<queue>
#include<cstring>
using namespace std;
typedef long long LL;
const int N=100000+5;
const int inf=0x3f3f3f3f;
#define ls (i<<1)
#define rs (i<<1|1)
int tree[N<<2],lazy[N<<2];
int L[N],R[N],temp[N<<2],tot,len,ans;
bool vis[N];
void init()
{
    memset(tree,0,sizeof(tree) );
    memset(lazy,0,sizeof(lazy) );
    memset(vis,0,sizeof(vis) );
    tot=len=ans=0;
}
void pushdown(int i,int l,int r)
{
    lazy[ls]=lazy[rs]=lazy[i];
    tree[ls]=tree[rs]=lazy[i];
    lazy[i]=0;
}
void update(int i,int l,int r,int ll,int rr,int v)
{
    if(ll<=l&&r<=rr)
    {
        lazy[i]=v;
        tree[i]=v;
        return;
    }
    if(lazy[i] ) pushdown(i,l,r);
    int mid=(l+r)>>1;
    if(mid>=ll) update(ls,l,mid,ll,rr,v);
    if(mid<rr) update(rs,mid+1,r,ll,rr,v);
    if(tree[ls]==tree[rs] ) tree[i]=tree[ls];
    else
        tree[i]=-1;
}
void query(int i,int l,int r,int ll,int rr)
{
    if(ll<=l&&r<=rr&&tree[i]!=-1)
    {
        if(tree[i]&&!vis[tree[i] ]) ans++;
        vis[tree[i] ]=1;
        return;
    }
    if(lazy[i] ) pushdown(i,l,r);
    int mid=(l+r)>>1;
    if(mid>=ll) query(ls,l,mid,ll,rr);
    if(mid<rr) query(rs,mid+1,r,ll,rr);
}
int read()
{
    int x=0,f=1;
    char ch=getchar();
    while(!isdigit(ch) )
    {
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(isdigit(ch) )
    {
        x=10*x+ch-'0';
        ch=getchar();
    }
    return x*f;
}
int main()
{
    int T=read();
    while(T--)
    {
        init();
        int n;
        n=read();
        for(int i=1;i<=n;i++)
        {
            L[i]=read();
            R[i]=read();
            temp[++tot]=L[i];
            temp[++tot]=R[i];
        }
        sort(temp+1,temp+tot+1);
        len=unique(temp+1,temp+tot+1)-temp;
        int m=len;
        for(int i=1;i<m;i++)
            if(temp[i+1]-temp[i]>1) temp[++len]=temp[i]+1,tot++;

        sort(temp+1,temp+len+1);
        for(int i=1;i<=n;i++)
        {
            L[i]=lower_bound(temp+1,temp+len+1,L[i] )-temp;
            R[i]=lower_bound(temp+1,temp+len+1,R[i] )-temp;
            update(1,1,len,L[i],R[i],i);
        }
        query(1,1,len,1,len);
        printf("%d
",ans);
    }
    return 0;
}

分析2

浮水法：由于是从前往后覆盖，答案由后面的海报先决定，那如果我们从后往前处理，前面海报的操作便不会对后面造成影响（可以节省时间和空间），故只需通过0 1 两种状态来判断是否被覆盖，用一个标记flag，如果当前区间没被覆盖且当前区间在目标区间内，则flag=1，更新结束后ans++。

实现方法：只需要一个更新函数即可，不需要lazy延时标记。

代码

#include<cstdio>
#include<cctype>
#include<algorithm>
#include<queue>
#include<cstring>
using namespace std;
typedef long long LL;
const int N=10000000+5;
const int inf=0x3f3f3f3f;
#define ls (i<<1)
#define rs (i<<1|1)
bool tree[N<<2],flag;  //1表示已经被后贴的海报覆盖
int L[10005],R[10005];
void update(int i,int l,int r,int ll,int rr)
{
    if(tree[i]) return;  //如果后贴的海报已经覆盖
    if(ll<=l&&r<=rr)
    {
        tree[i]=flag=1;
        return;
    }
    //printf("%d %d
",l,r);
    int mid=(l+r)>>1;
    if(mid>=ll)
        update(ls,l,mid,ll,rr);
    if(mid<rr)
        update(rs,mid+1,r,ll,rr);
    tree[i]=tree[ls]&&tree[rs];
}
int read()
{
    int x=0,f=1;
    char ch=getchar();
    while(!isdigit(ch) )
    {
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(isdigit(ch) )
    {
        x=10*x+ch-'0';
        ch=getchar();
    }
    return x*f;
}
int main()
{
    int T=read();
    while(T--)
    {
        int n;
        n=read();
        int maxn=0;
        for(int i=1;i<=n;i++)
        {
            L[i]=read();
            R[i]=read();
            maxn=max(maxn,R[i] );
        }
        int ans=0;
        for(int i=n;i>=1;i--) //浮水法，先处理最后的
        {
            flag=0;
            update(1,1,maxn,L[i],R[i] );
           // printf("%d %d %d
",L[i],R[i],flag);
            if(flag) ans++;
        }
        printf("%d
",ans);
        memset(tree,0,sizeof(tree) );
    }
    return 0;
}

分析1

分析2

相关推荐