Mayor's posters

题意：
输入t组数据，输入n代表有n块广告牌，按照顺序贴上去，输入区间，问贴完以后还有多少块广告牌可以看到（因为有的被完全覆盖了）。
输入：2 4
表示这块广告牌占了第2、3、4个格子。
思路：
这是占格子类型的题，Count the Colors是涂颜色的问题两者有点区别。可以理解为这题是涂[l,r]上的点，而Count the Colors是涂[l,r]上的线段
输入的区间太大，不能直接用线段树求，需要先离散化。
将左右端点离散化，先用数组存每一个端点，排序然后去重，每个端点离散化后的值就是它在数组中的下标。考虑到一个区间两个端的格子被覆盖对它的影响，如果这个区间格子为那么它就被完全覆盖了，如果这个区间长度大于那么它中间的部分还能看到。所以在离散化时，如果，需要加上端点，使得这个区间在离散化后的区间内格子的数量大于2，从而不破坏这个区间的特征。

的作用是“去掉”容器中相邻元素的重复元素（不一定要求数组有序），它会把重复的元素添加到容器末尾（所以数组大小并没有改变），而返回值是去重之后的尾地址，这个尾地址是从前面移过来的第一个重复元素的下标。

只将对应区间涂上对应的颜色(赋值为i)，子区间不管，父区间不涂色。统计时，标记某种颜色是否统计过，一旦发现一个区间涂了色处理完就退出，不必访问子区间。

Code：

#include<algorithm>
#include<cstring>
#include<cstdio>
using namespace std;
typedef long long ll;
const int maxn=1e4+7;
inline ll read() {
    ll s = 0, w = 1;
    char ch = getchar();
    while (ch < 48 || ch > 57) {
        if (ch == '-') w = -1;
        ch = getchar();
    }
    while (ch >= 48 && ch <= 57)
        s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
    return s * w;
}
int tree[maxn<<4],que[maxn<<2],li[maxn],ri[maxn],ans,tot;
bool vis[maxn];
inline void pushdown(int rt) {
    tree[rt<<1]=tree[rt<<1|1]=tree[rt];
    tree[rt]=-1;
}
inline void update(int x,int y,int val,int l,int r,int rt) {
    if(x<=l&&y>=r) {
        tree[rt]=val;
        return;
    }
    int mid=l+r>>1;
    if(~tree[rt]) pushdown(rt);
    if(x<=mid) update(x,y,val,l,mid,rt<<1);
    if(y>mid) update(x,y,val,mid+1,r,rt<<1|1);
}
inline void query(int l,int r,int rt) {
    if(~tree[rt]&&!vis[tree[rt]]) {
        ans+=1;
        vis[tree[rt]]=true;
        return;
    }
    if(l==r) return;
    int mid=l+r>>1;
    if(~tree[rt]) pushdown(rt);
    query(l,mid,rt<<1);
    query(mid+1,r,rt<<1|1);
}
int main() {
    int t=read(),n,mm,tt;
    while(t--) {
        n=read();
        ans=tot=0;
        memset(tree,-1,sizeof tree);
        memset(vis,false,sizeof vis);
        for(int i=1;i<=n;++i) {
            li[i]=read(),ri[i]=read();
            que[tot++]=li[i];
            que[tot++]=ri[i];
        }
        sort(que,que+tot);
        tt=mm=unique(que,que+tot)-que;
        for(int i=1;i<tt;++i) if(que[i]-que[i-1]>1)
            que[mm++]=que[i-1]+1;
        sort(que,que+mm);
        for(int x,y,i=1;i<=n;++i) {
            x=lower_bound(que,que+mm,li[i])-que,y=lower_bound(que,que+mm,ri[i])-que;
            update(x,y,i,0,mm-1,1);
        }
        query(0,mm-1,1);
        printf("%d\n",ans);
    }
    return 0;
}