题意：
n（n<=10000) 个人依次贴海报,给出每张海报所贴的范围 li，ri（1<=li<=ri<=10000000) 。求出最后还能看见多少张海报。
思路：
由于 li ri 都比较大，所以用离散化压缩一下空间，这里可以把所有的 li ri 都放在一个结构体数组 b[i] 中排序 再离散化。
不同的人涂的不同颜色的海报，颜色分别用1-n标记。
add数组就是Lazy数组。 1. 涂第一种颜色所有节点 rt ，都使它的add[rt]为当前颜色，说明这个节点包含的左右区间的范围都被涂了这种颜色。 2. 第二种颜色来涂的时候，如果经过第一种已经涂过的节点rt，就把这个点的add[rt]传给add[rt<<1]和add[rt<<1|1]，再把这个点add[rt]=0。如果第二种颜色的区间包括这个节点的区间，那么就涂成这个第二种颜色，如果没包括这个区间，就放着add[rt]=0了（如果我没理解错的话。。） ，继续遍历左右子区间，直到涂了颜色。 重复这样操作。
最后的Built函数，是遍历一遍线段树中所有的节点，记录add[rt]有几个不同的值，就是答案。注意：如果找到一个节点已经涂了颜色，就说明这个节点包含的区间已经涂了这个颜色，就直接return，不用管这个节点的子节点了。
我也是瞎写瞎猜的
#include<iostream>
#include<cstdio>
#include <cctype>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<string>
#include<cmath>
#include<set>
#include<vector>
#include<stack>
#include<queue>
#include<map>
using namespace std;
#define ll long long
#define mem(a,x) memset(a,x,sizeof(a))
#define se second
#define fi first
const ll mod=1e9+;
const int INF= 0x3f3f3f3f;
const int N=1e5+; int add[N<<];
int n,m;
int a[N<<];
int vis[N<<];
struct node
{
int v,p;
}b[N<<];
int ans=; bool cmp(node x,node y)
{
return x.v<y.v;
} void push_down(int rt)
{
if(add[rt])
{
add[rt<<]= add[rt];
add[rt<<|]= add[rt];
add[rt]=;
}
}
void Built(int l,int r,int rt)
{
if(add[rt])
{
if(!vis[add[rt]])
{
ans++;
vis[add[rt]]=;
}
return;
}
int m=l+r>>;
Built(l,m,rt<<);
Built(m+,r,rt<<|);
} void update(int x,int y,int c,int l,int r,int rt)
{
if(x<=l && r<=y)
{
add[rt]=c;
return;
}
push_down(rt);
int m=l+r>>;
if(x<=m) update(x,y,c,l,m,rt<<);
if(m<y) update(x,y,c,m+,r,rt<<|);
} int main()
{
int T,z;
cin>>T;
while(T--)
{
ans=;
mem(vis,);
//mem(add,0); scanf("%d",&n);
for(int i=;i<=n<<;i++)
{
scanf("%d",&z);
b[i].v=z; b[i].p=i;
}
sort(b+,b++n*,cmp);
int cnt=;
for(int i=;i<=n<<;i++)
{
if(b[i].v != b[i-].v)
cnt++;
a[b[i].p]=cnt;
} //离散化完毕 for(int i=;i<=n<<;i+=)
{
update(a[i], a[i+], (i+)/, ,cnt,); //每张海报涂色不同
}
Built(,n,);
cout<<ans<<endl;
}
}
离散化+线段树+lazy