题目描述:

布丁怪这一款游戏是在一个n×n 的矩形网格中进行的，里面有n个网格有布丁怪，其它的一些格子有一些其它的游戏对象。游戏的过程中是要在网格中移动这些怪物。如果两个怪物碰到了一起，那么他们就会变成一个更大的怪物。（谁叫他们是布丁呢？）

据统计，如果每一行每一列都只有一个布丁怪，那么这样的布局是比较吸引玩家的。

所以为了产生多种多样的有趣布局，我们会从一个 n×n 的有趣的地图中选取一个k×k (1≤k≤n)子矩形作为地图，而且这个子地图中恰好有k个布丁怪。

现在请你计算一下一个n×n 的有趣布局中，有多少种子地图是有趣的。

解题报告:

用时3h,2WA

这一题开始想着优化\(O(n^2)\)的暴力，并没有成功，然后请教大佬，得知是分治,然后花了3h才弄出这个分治，分治函数里必须数线性的，所以考虑怎么算贡献，发现只需要讨论最大值和最小值分别再\((l,mid)\)还是\((mid+1,r)\)

首先是全部在左边的，那么就可以确定右端点的位置，全在右边的同理

难点在于分别在左右两端的:

我们考虑左边是最小值，右边是最大值

那么对于\(R-L=Max-Min\)这个式子我们可以拆成：\(R-Max=L-Min\)就可以把\(R-Max\)放进桶里，然后统计\(L-Min\)即可，然后我就傻逼的放进了桶里，并没有维护左边最小值小于右边最小值，左边最大值小于右边最大值这两个条件，然后答案大了许多,所以要开两个单调指针维护左边最小值小于右边最小值，左边最大值小于右边最大值这两个条件，注意数组要偏移

对于左边是最大值，右边是最小值的情况同理:

维护\(R+Min=L+Max\)即可

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #define RG register#define il inline#define iter iterator#define Max(a,b) ((a)>(b)?(a):(b))#define Min(a,b) ((a)<(b)?(a):(b))using namespace std;const int N=4e5+5;struct node{ int x,y; bool operator <(const node &r)const{ return x
          
           >1; solve(l,mid);solve(mid+1,r); L[mid]=a[mid].y,R[mid]=a[mid].y; for(int i=mid-1;i>=l;i--){ L[i]=Min(L[i+1],a[i].y); R[i]=Max(R[i+1],a[i].y); } L[mid+1]=a[mid+1].y;R[mid+1]=a[mid+1].y; for(int i=mid+2;i<=r;i++){ L[i]=Min(L[i-1],a[i].y); R[i]=Max(R[i-1],a[i].y); } int j,k; for(int i=mid;i>=l;i--){ k=R[i]-L[i]+1; j=mid+(k-(mid-i+1)); if(j<=mid || j>r)continue; if(R[j]>=L[i] && R[j]<=R[i] && L[j]>=L[i] && L[j]<=R[i]) ans++; } for(int i=mid+1;i<=r;i++){ k=R[i]-L[i]+1; j=mid-(k-(i-mid+1)); if(j>=mid+1 || j
           
            =L[i] && R[j]<=R[i] && L[j]>=L[i] && L[j]<=R[i]) ans++; } int pr=mid+1,pl=mid+1; for(int i=mid;i>=l;i--){ while(pr<=r && L[i]
            
             R[pl])t[R[pl]-pl+mov]--,pl++; ans+=t[L[i]-i+mov]; } for(int i=pl;i
             
              =l && L[i]
              
               pr && R[i]>R[pl])t[R[pl]+pl]--,pl--; ans+=t[L[i]+i]; } for(int i=pl;i>pr;i--)t[R[i]+i]--;}void work(){ scanf("%d",&n); for(int i=1;i<=n;i++){ scanf("%d%d",&a[i].x,&a[i].y); } sort(a+1,a+n+1); solve(1,n); printf("%lld\n",ans);}int main(){ work(); return 0;}