1. 题目

传送门＝￣ω￣＝
题意：
依次张贴 n 张海报，新张贴的会覆盖之前的海报。给你每个海报覆盖的区间，问你最后还能看见几个海报。

n<=10^4,1<=坐标<=10^7

boshi&kb 已然用线段树 ac 了%%%%%

2. 题解

用 map 离散化一下。等于把每个端点（包括左端点、右端的）从小到大排序，再把它们的位置改为它们在排序后的序列中的位置（比如排第一的位置改为 1）。
然后从最后张贴的一张海报开始，一张一张张贴上去。数列初始为 0，每次对当前海报所在区间求和，如果得到的和小于区间内元素个数（l-r+1），那么说明还有没被覆盖的，也就是在数列中为 0 的数字。那么 ans++。再把这个海报所在区间的元素全部设为 1。
最后输出 ans。
记得清空数组、map。

说白了就是区间覆盖&区间求和
而且覆盖只可能覆盖成 1

EASY,RIGHT?

我用的是分块，复杂度：n√n，然而比线段树块——常数小啊！

代码：

#include <cstdio>
#include <map>
#include <cmath>
#include <cstring>
#define bi(a) ((a-1)/sqn+1)
using namespace std;
typedef pair<int,int> pii;typedef map<int,int> mii;
int n,sqn,arr[20100],sum[300],atag[300];
pii p[10100];
mii mp;
inline int getsum(int l,int r)
{
    int ans=0;
    for(int i=l;i<=min(r,bi(l)*sqn);i++)if(atag[bi(i)]||arr[i])ans++;
    if(bi(l)!=bi(r))for(int i=(bi(r)-1)*sqn+1;i<=r;i++)ans+=atag[bi(i)]|arr[i];
    for(int i=bi(l)+1;i<bi(r);i++)ans+=sum[i];
    return ans;
}
inline void update(int l,int r)
{
    for(int i=l;!atag[bi(l)]&&i<=min(r,bi(l)*sqn);i++)
        sum[bi(i)]+=(arr[i]^1),arr[i]=1;
    for(int i=(bi(r)-1)*sqn+1;bi(l)!=bi(r)&&!atag[bi(r)]&&i<=r;i++)
        sum[bi(i)]+=(arr[i]^1),arr[i]=1;
    for(int i=bi(l)+1;i<bi(r);i++)sum[i]=sqn,atag[i]=1;
}
int main()
{
    int c,i,ans;
    scanf("%d",&c);
    while(c--)
    {
        memset(arr,0,sizeof(arr)),memset(sum,0,sizeof(sum));
        memset(atag,0,sizeof(atag)),mp.clear(),ans=0;
        scanf("%d",&n),sqn=sqrt(n);
        for(i=1;i<=n;i++)
            scanf("%d%d",&p[i].first,&p[i].second),
            mp[p[i].first]=mp[p[i].second]=0;
        i=1;
        for(mii::iterator it=mp.begin();it!=mp.end();it++,i++)it->second=i;
        for(i=1;i<=n;i++)p[i].first=mp[p[i].first],p[i].second=mp[p[i].second];
        for(i=n;i>=1;i--)
            ans+=getsum(p[i].first,p[i].second)<p[i].second-p[i].first+1,
            update(p[i].first,p[i].second);
        printf("%d\n",ans);
    }
    return 0;
}