POJ – 2528 Mayor’s posters ([线段树] 区间离散化+区间修改+区间染色)

• 将区间[l,r]中的值修改为x
• 注意 这里的l , r因为题意的原因恰好可以对应“点”而不用设置开闭

• 1~10  1~4  6~10
• 离散化时 X[ 1 ] = 1, X[ 2 ] = 4, X[ 3 ] = 6, X[ 4 ] = 10

• 第一张海报时：1~4被染为1；
• 第二张海报时：1~2被染为2，3~4仍为1；
• 第三张海报时：3~4被染为3，1~2仍为2。
• 输出2，但是应该输出3

//在区间修改时，有lazy标记的区间 其lazy标记就就是区间里面的同一值 
#include<algorithm>
#include <iostream>
#include  <fstream>
#include  <cstdlib>
#include  <cstring>
#include  <cassert>
#include   <cstdio>
#include   <vector>
#include   <string>
#include    <cmath>
#include    <queue>
#include    <stack>
#include      <set>
#include      <map>
using namespace std;
#define P(a,b,c) make_pair(a,make_pair(b,c))
#define rep(i,a,n) for (int i=a;i<=n;i++)
#define per(i,a,n) for (int i=n;i>=a;i--)
#define CLR(vis) memset(vis,0,sizeof(vis))
#define MST(vis,pos) memset(vis,pos,sizeof(vis))
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef pair<int,pair<int,int> >pii;
typedef long long ll;
typedef unsigned long long ull;
const ll mod = 1000000007;
const int INF = 0x3f3f3f3f;
ll gcd(ll a, ll b) {
	return b ? gcd(b, a%b) : a;
}
template<class T>inline void gmax(T &A, T B) {
	(A<B)&&(A=B);//if(B>A)A=B;
}
template<class T>inline void gmin(T &A, T B) {
	(A>B)&&(A=B);//if(B<A)A=B;
}
template <class T>
inline bool scan_d(T &ret) {
	char c;
	int sgn;
	if(c=getchar(),c==EOF) return 0; //EOF
	while(c!='-'&&(c<'0'||c>'9')) c=getchar();
	sgn=(c=='-')?-1:1;
	ret=(c=='-')?0:(c-'0');
	while(c=getchar(),c>='0'&&c<='9') ret=ret*10+(c-'0');
	ret*=sgn;
	return 1;
}
inline void outt(int x) {
	if(x>9) outt(x/10);
	putchar(x%10+'0');
}
const int maxn = 1e5+10;
struct SegmentTree {
	int l,r;
	long long add;
#define l(x) tree[x].l
#define r(x) tree[x].r
//#define sum(x) tree[x].sum
#define add(x) tree[x].add
} tree[maxn*4];
int vis[maxn<<3],ans,n;
int li[maxn*2],ri[maxn*2],lsh[maxn<<2];
void build(int p,int l,int r) {
	l(p)=l,r(p)=r;
	add(p)=-1;//注意初始化位置 
	if(l==r) {
		return ;
	}
	int mid=(l+r)/2;//只有这里的一半是直接用传入的l，r，但实际上这里的l，r就是下面的p.l,p.r
	build(p*2,l,mid);
	build(p*2+1,mid+1,r);
}
//延迟标记代表：该节点已经被修改，但子节点尚未被更新
void spread(int p) {
	if(add(p)!=-1) {
		add(p*2)=add(p*2+1)=add(p);
		add(p) = -1;//清除p节点的标记
	}
}
void change(int p,int l,int r,int d) {
	if(l<=l(p) && r>=r(p)) { //完成覆盖
		add(p)=d;//给节点打延迟标记
		return ;
	}
	spread(p); 
	int mid=(l(p)+r(p))/2;
	if(l<=mid)change(p*2,l,r,d);
	if(r>mid)change(p*2+1,l,r,d);
}
void ask(int p,int l,int r) {
	if(add(p)!=-1){
		if(!vis[add(p)])vis[add(p)]=1,ans++;
		return;
	}
	if(l(p)==r(p)){
		return;
	}
	spread(p);
	ask(p*2,l,r);
	ask(p*2+1,l,r);
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        memset(vis,0,sizeof(vis));
        int tot=0;
        for(int i=0;i<n;i++)
        {
            scanf("%d%d",&li[i],&ri[i]);
            lsh[tot++]=li[i];
            lsh[tot++]=ri[i];
        }
        sort(lsh,lsh+tot);
        int mm=unique(lsh,lsh+tot)-lsh;//排序后消除相邻相同元素 
        int tt=mm;
        for(int i=1;i<tt;i++)
        {
            if(lsh[i]-lsh[i-1]>1)
                lsh[mm++]=lsh[i-1]+1;//相邻大于1插入一个离散化坐标 
        }
        sort(lsh,lsh+mm);
        build(1,1,mm);
        for(int i=0;i<n;i++)
        {
            int x=lower_bound(lsh,lsh+mm,li[i])-lsh;
            int y=lower_bound(lsh,lsh+mm,ri[i])-lsh;
            change(1,x+1,y+1,i);
        }
        ans=0;
        ask(1,1,mm);
        printf("%d\n",ans);
    }
    return 0;
}