题目链接
题意：
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;
}