题意

布丁怪这一款游戏是在一个n×n 的矩形网格中进行的，里面有n个网格有布丁怪，其它的一些格子有一些其它的游戏对象。游戏的过程中是要在网格中移动这些怪物。如果两个怪物碰到了一起，那么他们就会变成一个更大的怪物。（谁叫他们是布丁呢？）
据统计，如果每一行每一列都只有一个布丁怪，那么这样的布局是比较吸引玩家的。
所以为了产生多种多样的有趣布局，我们会从一个 n×n 的有趣的地图中选取一个k×k (1≤k≤n)子矩形作为地图，而且这个子地图中恰好有k个布丁怪。
现在请你计算一下一个n×n 的有趣布局中，有多少种子地图是有趣的。

题解

O(n^3)

暴力枚举k和每一个点就可以了

O(n^2)

稍作思考，你就会发现一个结论，就是一个合法的正方形，四边一定会有布丁怪的存在，于是你暴力枚举两个布丁怪作为两个边界就可以了

O(nlog^2n)

这里有一个很妙的模型转化
就是等价于求一个序列里面有多少个子串的值是连续的
这个的话可以直接分治来做
讨论的时候用一下树状数组或者排序搞一搞

O(nlogn)

两个指针一起扫过去就可以了，开一个桶维护一下
具体看代码

CODE:

#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long LL;
const int N=300005;
int n;
int a[N];
LL ans=0;
int maxx[N],minn[N];
LL cnt[N*2];
void solve (int l,int r)
{if (l==r) {ans++;return ;}int mid=(l+r)>>1;solve(l,mid);solve(mid+1,r);maxx[mid]=a[mid];minn[mid]=a[mid];for (int u=mid-1;u>=l;u--){maxx[u]=max(maxx[u+1],a[u]);minn[u]=min(minn[u+1],a[u]);}maxx[mid+1]=a[mid+1];minn[mid+1]=a[mid+1];for (int u=mid+2;u<=r;u++){maxx[u]=max(maxx[u-1],a[u]);minn[u]=min(minn[u-1],a[u]);}//max-min=i-jfor (int u=l;u<=mid;u++)//最大值和最小值都在这一边{int i=maxx[u]-minn[u]+u;if (i>mid&&i<=r&&maxx[i]<=maxx[u]&&minn[i]>=minn[u]) ans++;}for (int u=mid+1;u<=r;u++)//最大值和最小值都在这一边{//j=i-max+minint i=u-maxx[u]+minn[u];if (i<=mid&&i>=l&&maxx[i]<=maxx[u]&&minn[i]>=minn[u]) ans++;}int L=mid+1,R=mid+1; for (int u=mid;u>=l;u--)//只有最小值在这一边{//j-min=i-maxwhile (R<=r&&minn[R]>=minn[u])  {cnt[R-maxx[R]+N]++;R++;}while (L<R&&maxx[L]<=maxx[u])   {cnt[L-maxx[L]+N]--;L++;}ans=ans+cnt[u-minn[u]+N];}for (int u=L;u<R;u++)   cnt[u-maxx[u]+N]--;L=mid+1,R=mid+1; for (int u=mid;u>=l;u--)//只有最大值在这一边{//j+max=i+minwhile (R<=r&&maxx[R]<=maxx[u])  {cnt[R+minn[R]]++;R++;}while (L<R&&minn[L]>=minn[u])   {cnt[L+minn[L]]--;L++;}ans=ans+cnt[u+maxx[u]];}for (int u=L;u<R;u++)   cnt[u+minn[u]]--;return ;
}
int main()
{memset(cnt,0,sizeof(cnt));scanf("%d",&n);for (int u=1;u<=n;u++){int x,y;scanf("%d%d",&x,&y);a[x]=y;}solve(1,n);printf("%lld\n",ans);return 0;
}