1 /*  2 题意：给你n*m的棋盘，有些棋盘被一些矩形覆盖，求放进一个长为M，宽为1的矩形的方案数  3   4 离散，线段树 +扫描线   5 分析：最直接得想法，对于每一层统计空白连续的长度然后统计放的方案数，不过编程复杂度有点高  6 要分别记录下每个区间左边连续最长空白长度和右边最长连续空白长度，  7 然后count[rt]=count[r<<1]+count[rt<<1|1]+{跨两段的个数}   8   9 一个好想法：当以y为分层标准时，统计竖着放的方案数，那么把每个矩形都向下延伸M-1个单位， 10 那么剩下的每一个空位都对应一种方法，直接矩形并求面积就好，问题得到转化； 11  12 一些细节：扫描线的细节处非常有意思; 13 首先题目给我们的数据是对应一段区间的，比如矩形[2,2,2,2]表示长宽都为1的矩形,为了方便，我们把它转化成 14 [1,1,2,2]这样在统计的时候直接相减就可以了，  15 */ 16 #include
     
       17 #include
      
        18 #include
       
         19 #include
        
          20 #include
         
           21 #include
          
            22 #include
           
             23 #include
            
              24 #define lson l,m,rt<<1 25 #define rson m+1,r,rt<<1|1 26 #define Find(i) lower_bound(LX.begin(),LX.begin()+n1,i)-LX.begin() 27 using namespace std; 28 const int NN=100000+10; 29 typedef long long LL; 30 struct Edge{ 31 int hi,ls,rs,s; 32 Edge(){} 33 Edge(int a,int b,int c,int e):hi(a),ls(b),rs(c),s(e){} 34 bool operator < (const Edge &p)const{ 35 return hi
             
               E; 39 vector
              
                LX; 40 int len[NN<<2],cov[NN<<2]; 41 int W,H,N,M,n1; 42 int x[NN/2],y[NN/2],x2[NN/2],y2[NN/2]; 43 LL ans; 44 void pushup(int l,int r,int rt){ 45 if (cov[rt]>=1){ 46 len[rt]=(LX[r+1]-LX[l]); 47 }else if (l==r) len[rt]=0; 48 else len[rt]=len[rt<<1]+len[rt<<1|1]; 49 } 50 void update(int L,int R,int v,int l,int r,int rt){ 51 if (L<=l && r<=R){ 52 cov[rt]+=v; 53 if (cov[rt]>=1) len[rt]=(LX[r+1]-LX[l]); 54 else if (l==r) len[rt]=0; 55 else len[rt]=len[rt<<1]+len[rt<<1|1]; 56 return ; 57 } 58 int m=(l+r)>>1; 59 if (L<=m) update(L,R,v,lson); 60 if (m< R) update(L,R,v,rson); 61 pushup(l,r,rt); 62 } 63 64 void work(){ 65 E.clear();LX.clear(); 66 E.push_back(Edge(max(0,H-M+1),0,W,1)); 67 E.push_back(Edge(H,0,W,-1)); 68 LX.push_back(0);LX.push_back(W);//最后面要加入一个大矩形 69 for (int i=0;i