https://blog.csdn.net/sadnohappy/article/details/52199051

https://www.cnblogs.com/12mango/p/7465667.html

耐心看完这两篇博客相信你已经大概理解了。

以下是我自己的一些理解，

首先

$n^3$算法

---

 

无脑维护前缀和

MLE+TLE

 1 #include<bits/stdc++.h>
 2 #define ll long long
 3 #define A 10100
 4 using namespace std;
 5 ll a[A][A];
 6 bool b[A][A];
 7 ll n,m,ans=0;
 8 const int L=1<<20|1;
 9 char buffer[L],*S,*T;
10 #define getchar() ((S==T&&(T=(S=buffer)+fread(buffer,1,L,stdin),S==T))?EOF:*S++)
11 inline int Read(){
12     register int ret;
13     register char r;
14     while(r=getchar(),r<'0'||r>'9');ret=r-48;
15     while(r=getchar(),r>='0'&&r<='9')ret=ret*10+r-48;
16     return ret;
17 }
18 void dfs(ll k)
19 {
20     if(k==n) return ;
21     for(ll i=1;i<=n-k+1;i++)
22         for(ll j=1;j<=n-k+1;j++){
23             if(a[i+k-1][j+k-1]+a[i-1][j-1]-a[i-1][j+k-1]-a[i+k-1][j-1]==k)
24                 ans++/*,printf("k=%lld i=%lld j=%lld a[%lld][%lld]=%lld a[%lld][%lld]=%lld a[%lld][%lld]=%lld a[%lld][%lld]=%lld\n",k,i,j,i+k-1,j+k-1,a[i+k-1][j+k-1],i-1,j-1,a[i-1][j-1],i-1,j+k-1,a[i-1][j+k-1],i+k-1,j-1,a[i+k-1][j-1])*/;
25         }
26     dfs(k+1);
27 }
28 int main()
29 {
30     scanf("%lld",&n);
31     for(ll i=1;i<=n;i++)
32         {
33             ll xx=Read(),yy=Read();
34             b[xx][yy]++;
35         }
36     for(ll i=1;i<=n;i++)
37         for(ll j=1;j<=n;j++)
38         {a[i][j]=a[i-1][j]+a[i][j-1]-a[i-1][j-1]+b[i][j];}
39 //    cout<<a[2][4]<<endl;
40     dfs(2);
41     cout<<ans+n+1<<endl;
42 }

$n^2$

---

 略微思考，发现可以把它转换为一维的，行列不重复，所以可以用一个a数组存下来值 a[i]就下标代表第一行，具体存的数就代表第j列

那么我们发现从a[i]-a[j]中a中最大值减a中最小如果为j-i那么就符合题目中所说的子矩阵

维护ST表或单调队列维护，严格$n^2$

约55--64分，看你常数大小

减减枝91

$n\times log n$

---

 

一个非常玄学做法，

建议结合代码来看，虽然我知道你不想看代码

玄学二分加桶

这还是我第一次遇到这样的题

事实上该做法是$n^2$的一个优化，思路和它类似a[i]-a[j]中a中最大值减a中最小如果为j-i那么就符合题目中所说的子矩阵。

那么我们二分一个区间时有如下情况

1，当前枚举区间最大值最小值都在mid左面

2，当前枚举区间最大值最小值都在mid右面

3，最小值在左面，最大值在右面

4，最大值在右面，最小值在左面

对于1，我们要做的是扫一遍mid以左就完了，我们max-min+i就是当前区间，要判断j是否>mid 因为即使符合<=mid的情况也会在二分时解决（因为全部在左区间），我们找的最大值最小值都在mid左面，并不一定全在左面，有部分在右面

对于2，做法同1

对于3，我们首先先找到了mid以左最小，以及最大，设mid以左最小minl，最大maxl

我们定义两个指针一个minn指针，一个maxx指针，当前指针都指向mid 因为maxx<=maxl我们要满足3最大值在右面只能往右搜。我们需要找到minn>minl最大位置（因为minn往右搜只会越来越小满足单调性），maxx>ml最小位置（maxx越搜只会越来越大满足单调性）。

找到指针指向位置我们可以断定mid--maxx之间所有方案都不符合3，mid--minn之间可能符合3。

宗上那么maxx--minn之间值可能符合3;

对于”“思路和它类似a[i]-a[j]中a中最大值减a中最小如果为j-i那么就符合题目中所说的子矩阵”“  这句话 移项

maxx-r==minn-l   我们在桶里存maxx-r 然后找到minn-l对应就完了。

对于4，做法同3

以下是本人丑陋的代码

 1 #include<bits/stdc++.h>
 2 #define ll long long
 3 #define A 1100000
 4 using namespace std;
 5 ll lmax[A],lmin[A],rmax[A],rmin[A],tong[A],a[A],n; 
 6 ll work(ll l,ll r,ll mid){
 7     ll w=0;
 8     lmax[mid]=a[mid];lmin[mid]=a[mid];
 9     rmax[mid+1]=a[mid+1];rmin[mid+1]=a[mid+1];
10     for(ll i=mid-1;i>=l;i--){
11         lmax[i]=max(lmax[i+1],a[i]);
12         lmin[i]=min(lmin[i+1],a[i]);
13     }
14     for(ll i=mid+2;i<=r;i++){
15         rmax[i]=max(rmax[i-1],a[i]);
16         rmin[i]=min(rmin[i-1],a[i]);
17     }
18     for(ll i=l;i<=mid;i++){
19         ll j=i+lmax[i]-lmin[i];
20         if(j>mid&&rmax[j]<lmax[i]&&rmin[j]>lmin[i]) w++;
21     }
22     ll p1=mid+1,p2=mid;
23     while(p1<=r&&rmax[p1]<lmax[l]) tong[rmax[p1]-p1]--,p1++;
24     while(p2<r&&rmin[p2+1]>lmin[l]) p2++,tong[rmax[p2]-p2]++;
25     for(ll i=l;i<=mid;i++){
26         while(p1>mid+1&&rmax[p1-1]>lmax[i]) p1--,tong[rmax[p1]-p1]++; 
27         while(p2>mid&&rmin[p2]<lmin[i]) tong[rmax[p2]-p2]--,p2--;
28         w+=max(tong[lmin[i]-i],0ll);
29     }
30     for(ll i=mid+1;i<=r;i++){
31         tong[rmax[i]-i]=0;
32     }
33     return w;
34 }
35 ll solve(ll l,ll r){
36     if(l==r) return 1;
37     ll mid=(l+r)>>1;
38     ll zz=solve(l,mid)+solve(mid+1,r);
39     zz+=work(l,r,mid);
40     reverse(a+l,a+r+1);
41     if((r-l+1)&1) mid--;
42     zz+=work(l,r,mid);
43     reverse(a+l,a+r+1);
44     return zz;
45 }
46 int main(){
47     scanf("%lld",&n);
48     for(ll i=1;i<=n;i++){
49         ll xx,yy;
50         scanf("%lld%lld",&xx,&yy);
51         a[xx]=yy;
52     }
53     cout<<solve(1,n);
54 }