题意：无限大的棋盘上，在横向和纵向上被包围的白子会变成黑子，求最终黑子个数？

分析：

首先这个棋盘十分的大，但已给黑点的个数为1e5，我们需要离散化，所谓的离散化就是数组下标的重新定义。

这里给出离散化函数，返回的是离散化后数组的个数

1 int compress(int *p,int N) 2 { 3     vector
      
        ps(N); 4     for (int i = 0; i < N; ++i)ps[i] = p[i]; 5     sort(ps.begin(), ps.end()); 6     ps.erase(unique(ps.begin(), ps.end()), ps.end()); 7     for (int i = 0; i < N; ++i) 8     { 9         p[i] = 1 + distance(ps.begin(), lower_bound(ps.begin(), ps.end(), p[i]));10     }11     return ps.size();12 }
      

扫描线算法：

扫描线算法其实是计算机几何里面的算法,这里引用

基本思想

        按扫描线顺序，计算扫描线与多边形的相交区间，再用要求的颜色显示这些区间的象素，即完成填充工作。

对于一条扫描线填充过程可以分为四个步骤：

    (1)  求交：计算扫描线与多边形各边的交点

    (2)  排序：把所有交点按 x 坐标递增顺序来排序

    (3)  配对：确定扫描线与多边形的相交区间，第一个与第二个，第三个与第四个等等，每对交点代表扫描线与多边形的一个相交区间

    (4)  填充：显示相交区间的象素

那么对于这道题目来说我们如何使用？

首先构造扫描线，这里使用Y轴，X轴其实一样的

对于每一条扫描线上的点按x坐标排序，然后得到n个区间，我们需要统计在这个区间里面有多少白色的点可以变为黑点

条件是上下都被黑点包围(左右已经符合)

如何判断上下有没有黑点呢？这里巧妙的使用了一个bool数组used，used[i]表示x=i这条竖线上是否已经出现过黑点

由于扫描线算法中扫描线是按y从小到大枚举的，所以如果之前有出现过黑点，加上当前扫描的点也是黑点，那么这个区间一定是被黑点包围的。

现在来处理区间统计问题，这是树状数组的强项。(区间加减+区间求和)

实际上这里只用到了区间加减+单点查询，都差不多

现在给出算法:

首先离散化，然后构造扫描线。

接着按y从小到大枚举扫描线，对于每条扫描线的点按x从小到大排序，遍历所有的点可以得到n个区间[a[i-1],a[i]]

对于区间[a[i-1],a[i]],当前遍历到a[i]，如果竖轴x=a[i]上used[x]=true 那么需要将答案加上当前竖轴上区间的白点个数query(x,x),否认设置used[x]=true(因为当前遍历的就是黑点),计算完该区间以后一定要记得将该区间的树状数组清掉，因为树状数组维护的区间和，如果不清会导致重复计算(两条扫描线之间的点),

至于更新的话很简单，就是把区间（a[i-1],a[i]）都加上1,因为区间中都是满足左右被黑点包围的白点。（注意不要越界）

最后上代码：

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 #include 
          
            6 #include 
           

&v = line[i];77 sort(v.begin(),v.end());78 for(vector

::iterator j = v.begin();j!=v.end();++j){79 int x = *j;80 ll s = T.query(x,x);81 if(used[x])ans+=s;82 else used[x]=true;83 T.update(x,x,-s);84 if(j!=v.end()-1)T.update(x+1,*(j+1)-1,1);85 }86 }87 printf("%lld\n",ans);88 }89 }