[HAOI2007] 理想的正方形 (单调队列)

题目链接

Solution

MD,经过这道题,算是掌握单调队列了...

可以先预处理出点 \((i,j)\) 往上 \(n\) 的最大值和最小值.

然后再横着做一遍单调队列即可.

Code

#include<bits/stdc++.h>

#define in(x) x=read();

#define ll long long

#define N 1001

using namespace std;

ll read()

{

	char ch=getchar(); ll f=1,w=0;

	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

	while(ch>='0'&&ch<='9'){w=w*10+ch-'0';ch=getchar();}

	return f*w;

}

ll Mx[N][N],Mn[N][N];

ll a,n,m,w[N][N];

ll ans=0x3f3f3f3f3f;

int main()

{

	in(n); in(m); in(a);

	for(int i=1;i<=n;i++)

	for(int j=1;j<=m;j++)

	in(w[i][j]);

 	for(int j=1;j<=m;j++)

    {

        int head=1,tail=0,q[N];

        for(int i=1;i<=n;i++)

        {

            while(head<=tail&&w[q[tail]][j]>=w[i][j]) tail--;

            q[++tail]=i;

            while(q[tail]-q[head]>=a) head++;

            Mn[j][i]=w[q[head]][j];

        }

        head=1;tail=0;

        for(int i=1;i<=n;i++)

        {

            while(head<=tail&&w[q[tail]][j]<=w[i][j]) tail--;

            q[++tail]=i;

            while(q[tail]-q[head]>=a) head++;

            Mx[j][i]=w[q[head]][j];

        }

    }

    for(int i=a;i<=n;i++)

    {

        int h=1,t=0,H=1,T=0;

       	ll minn,maxx,q1[N],q2[N];

        for(int j=1;j<=m;j++)

        {

            while(h<=t&&Mn[q1[t]][i]>=Mn[j][i]) t--;

            while(H<=T&&Mx[q2[T]][i]<=Mx[j][i]) T--;

            q1[++t]=j;q2[++T]=j;

            while(q1[t]-q1[h]>=a) h++;

            while(q2[T]-q2[H]>=a) H++;

            minn=Mn[q1[h]][i];

            maxx=Mx[q2[H]][i];

            if(j>=a)

            ans=min(ans,maxx-minn);

        }

    }

    cout<<ans;

}

巴特西

[HAOI2007] 理想的正方形 (单调队列)

题目链接

Solution

Code

最新文章

热门文章