51nod 1555 布丁怪

题意

布丁怪这一款游戏是在一个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-j
    for (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+min
        int 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-max
        while (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+min
        while (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;
}