刚刚在做poj2528。想起来以前傲妹让我们写的那一道usaco题，两道题都是在平面【直线】上用矩形【线段】覆盖，最后计算有几个矩形【线段】没有被完全覆盖。

usaco那道题n只有1000，但是大家都被这种题目吓傻了纷纷去写线段树，写出来的效率还都是O(n^2logn)的。当时我写的O(nlogn)的扫描线线段树，没考虑一种特殊情况导致整个算法是错的，但是数据弱居然也有80分。现在想来这题的最优算法应该是nlogn的扫描线线段树，每个节点储存该线段当前的矩形及被当前矩形覆盖的最上矩形。

这算法效率是最优的但是写起来很麻烦。当时被傲妹给出的标程之短震惊了。

矩形切割的想法很简单，即矩形与矩形相交的并也可以分割为若干个矩形。用递归来写很方便。矩形切割的想法在一维上的实现，即线段切割，在线段树七题里莫诺瑞根那道题的效率比线段树还高。

矩形\线段切割的最坏效率O(n^2)，但是能导致这种最坏效率的数据需要手工构造，确实比较麻烦。出题人一般也不会蛋疼到去刻意卡这种算法吧。【跟spfa还能用的理由差不多

想起来很简单，但是判断相交那里有很多种情况要考虑，貌似比较麻烦。后来发现，排除掉相离的情况，剩下的情况比较少，用4条语句每次考虑一条边的相交情况即可。

poj2528用线段切割写起来只有25行，235MS1A。效率不怎么样但是确实短。

#include <cstdio>
int l[10001],r[10001],n,ans=0;
bool sf(int A,int B,int dep)
{
    if(dep==n+1)return true;
    if(B<l[dep]||A>r[dep]) return sf(A,B,dep+1);
    bool f=false;
    if(A<l[dep]){f=f|sf(A,l[dep]-1,dep+1);A=l[dep];}
    if(r[dep]<B) f=f|sf(r[dep]+1,B,dep+1);
    return f;
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        ans=0;
        scanf("%d",&n);
        for(int i=1;i<=n;i++) scanf("%d %d",&l[i],&r[i]);
        for(int i=n;i>=1;i--) if(sf(l[i],r[i],i+1)) ++ans;
        printf("%d\n",ans);
    }
}