欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

51nod 1555 布丁怪 分治

程序员文章站 2022-05-08 17:56:09
...

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

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

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

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

题解:

容易想到分治,关键是如何算经过mid的答案。对于每个点(xi,yi),令a[yi]=xi,问题可以转化为经过mid的子串有多少个满足maxmin+1等于子串长度。还是分类讨论,把最大值和最小值在mid同侧和异侧分开讨论,利用最大最小值的单调性来维护答案,如果不想复制黏贴的话可以把原序列反过来再做一遍,但是要注意此时mid的取值,不然会出现重复计算的情况。

代码:

#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define pa pair<int,int>
const int Maxn=300010;
const int inf=2147483647;
int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
    return x*f;
}
int n,a[Maxn],mn[Maxn],mx[Maxn],cnt[Maxn<<1];LL ans=0;
bool fir=true;
void solve(int l,int r)
{
    if(l>=r)return;
    int mid=l+r>>1,j=mid;
    if(!fir&&(r-l+1)&1)mid--,j--;
    solve(l,mid);solve(mid+1,r);
    mn[mid+1]=inf;mx[mid+1]=-inf;
    LL tmp=ans;
    for(int i=mid;i>=l;i--)
    {
        mn[i]=min(mn[i+1],a[i]),mx[i]=max(mx[i+1],a[i]);
        if(mx[i]-mn[i]==j-i&&j>mid)ans++;
        while(j<r&&a[j+1]>mn[i]&&a[j+1]<mx[i])
        {
            j++;
            if(mx[i]-mn[i]==j-i)ans++;
        }
    }
    mn[mid+1]=mx[mid+1]=a[mid+1];
    for(int i=mid+2;i<=r;i++)mn[i]=min(mn[i-1],a[i]),mx[i]=max(mx[i-1],a[i]);
    j=mid;
    int L=mid+1,R=mid;
    for(int i=mid;i>=l;i--)
    {
        while(R<r&&mx[R+1]<mx[i])R++,cnt[mn[R]+R]++;
        while(L<=r&&mn[L]>mn[i])cnt[mn[L]+L]--,L++;
        ans+=(LL)(max(cnt[mx[i]+i],0));
    }
    while(L<=r)cnt[mn[L]+L]--,L++;
    while(R<r)R++,cnt[mn[R]+R]++;
}
int main()
{
    n=read();
    for(int i=1;i<=n;i++)
    {
        int x=read(),y=read();
        a[y]=x;
    }
    solve(1,n);
    for(int i=1;i<=(n>>1);i++)swap(a[i],a[n-i+1]);
    fir=false;
    solve(1,n);
    printf("%lld",ans+(LL)(n));
}