区间染色问题
将一个区间内的点分别染色，问共有多少种颜色可以被看到(已经被染色的点可以被覆盖这个区间的颜色所覆盖)
例题:poj 2527
线段树的每个节点用一个懒标记维护当前区间是否被某个颜色完全覆盖，其子节点的值都为当前节点的值,这样也可以将原来被染色的点但是会被覆盖的点覆盖掉
没有覆盖到的点的值为0，颜色的范围[1,n]
查询的时候如果当前节点被某个颜色完全覆盖，则直接返回1，否则递归下去，看左右子树的颜色值
小技巧：
为了防止区间离散化之前不连续，而离散化之后连续的情况。我们看离散化序列，如果相邻两个数的值之差大于1，则在这俩数中间插入一个数。
// Problem: Just a Hook
// Contest: Virtual Judge - HDU
// URL: https://vjudge.net/problem/HDU-2528
// Memory Limit: 32 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include<iostream>
#include<cstring>
#include<queue>
#include<algorithm>
#include<cmath>
#include<stack>
#include<vector>
#include<map>
#include<set>
using namespace std;
#define x first
#define y second
typedef pair<int,int> PII;
typedef long long LL;
const int N=2e5+10;
int T,n;
vector<int> all;
vector<PII> pos;
bool st[N];
struct node{
int l,r;
int fla;
}tr[N*3];
void disc(){
sort(all.begin(),all.end());
all.erase(unique(all.begin(),all.end()),all.end());
for(int i=1;i<n;i++){
if(all[i]-all[i-1]!=1) all.push_back(all[i]-1);
}
sort(all.begin(),all.end());
}
int getloc(int x){
return lower_bound(all.begin(),all.end(),x)-all.begin();
}
void pushdown(int u){
node &root=tr[u],&left=tr[u<<1],&right=tr[u<<1|1];
if(root.fla){
left.fla=root.fla;
right.fla=root.fla;
root.fla=0;
}
}
void build(int u,int l,int r){
tr[u].l=l;
tr[u].r=r;
tr[u].fla=0;
if(l==r){
return ;
}else{
int mid=(tr[u].l+tr[u].r)>>1;
build(u<<1,l,mid),build(u<<1|1,mid+1,r);//防止原来不连续的点离散化之后连续
}
}
void modify(int u,int l,int r,int num){
if(tr[u].l>=l&&tr[u].r<=r){
tr[u].fla=num;
return ;
}
pushdown(u);
int mid=(tr[u].l+tr[u].r)>>1;
if(l<=mid) modify(u<<1,l,r,num);
if(r>mid) modify(u<<1|1,l,r,num);
}
int query(int u){
if(tr[u].fla){
if(!st[tr[u].fla]){
return st[tr[u].fla]=1;
}
return 0;
}
if(tr[u].l==tr[u].r) return 0;
return query(u<<1)+query(u<<1|1);
}
int main(){
scanf("%d",&T);
while(T--){
all.clear();
pos.clear();
all.push_back(-0x3f3f3f3f);
scanf("%d",&n);
for(int i=1;i<=n;i++){
st[i]=0;
int l,r;
scanf("%d%d",&l,&r);
PII now;
now.x=l,now.y=r;
pos.push_back(now);
all.push_back(l);
all.push_back(r);
}
disc();//离散化
int len=all.size()-1;
build(1,1,len);
for(int i=0;i<n;i++){
int l=getloc(pos[i].x),r=getloc(pos[i].y);
// printf("%d %d\n",l,r);
modify(1,l,r,i+1);//染色
}
printf("%d\n",query(1));
}
return 0;
}