RMQ-洛谷P2216 [HAOI2007] 理想的正方形

https://www.luogu.org/problem/show?pid=2216

一開始我想了個前墜和，後來發現有bug；

過了一個月發現是二維線段樹水題，但好像二維線段樹太麻煩；

然後看了題解；

1.二維倍增RMQ

2.單調隊列*2；

那我都打一打把；

二維倍增RMQ

ma[i][j][k]表示

i,j——————i+(1<< k)-1,j+(1<< k)-1)

的最大值

然後直接無腦RMQ；

注意一下區間邊界要不要+1要不要-1；

這種問題模拟即可

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#define Ll long long
using namespace std;
int ma[][][],mi[][][];
int n,m,q,x,y,z,ans;
int RMQ(int x,int y,int xx,int yy){
    return max(max(ma[x][y][z],ma[xx-(<<z)+][yy-(<<z)+][z]),max(ma[x][yy-(<<z)+][z],ma[xx-(<<z)+][y][z]))-
           min(min(mi[x][y][z],mi[xx-(<<z)+][yy-(<<z)+][z]),min(mi[x][yy-(<<z)+][z],mi[xx-(<<z)+][y][z]));
}
int main()
{
    scanf("%d%d%d",&n,&m,&q);
    for(int i=;i<=n;i++)
    for(int j=;j<=m;j++){
        scanf("%d",&x);
        ma[i][j][]=mi[i][j][]=x;
    }
    for(int k=;(<<k)<=min(n,m);k++)
    for(int i=;i<=n-(<<k)+;i++)
    for(int j=;j<=m-(<<k)+;j++){
        ma[i][j][k]=max(max(ma[i][j][k-],ma[i+(<<(k-))][j+(<<(k-))][k-]),
                        max(ma[i][j+(<<(k-))][k-],ma[i+(<<(k-))][j][k-]));
        mi[i][j][k]=min(min(mi[i][j][k-],mi[i+(<<(k-))][j+(<<(k-))][k-]),
                        min(mi[i][j+(<<(k-))][k-],mi[i+(<<(k-))][j][k-]));
    }
    ans=e9;
    z=;
    while((<<(z+))<q)z++; 
    for(int i=;i<=n-q+;i++)
    for(int j=;j<=m-q+;j++)ans=min(ans,RMQ(i,j,i+q-,j+q-));
    printf("%d",ans);
}
           

單調隊列*2

本來以為很水，然後打了40分種；

錯誤1是+1-1搞錯了，檢查了好半天；

是以關于區間邊界的這種一定要預先算好；

然後是複制優先隊列時數組搞錯了；

….

當然的，時空複雜度，單調隊列明顯優于RMQ

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#define Ll long long
using namespace std;
int a[][],mi[][],ma[][],q[1001];
int n,m,p,l,r,ans;
int main()
{
    scanf("%d%d%d",&n,&m,&p);
    for(int i=;i<=n;i++)
    for(int j=;j<=m;j++)scanf("%d",&a[i][j]);
    for(int i=;i<=n;i++){
        l=;r=;q[0]=;a[i][]=e9+;
        for(int j=;j<p;j++){
            while(r>=l&&a[i][q[r]]<=a[i][j])r--;
            q[++r]=j;
        }
        for(int j=p;j<=m;j++){
            while(r>=l&&a[i][q[r]]<=a[i][j])r--;
            q[++r]=j;
            while(q[l]+p-<j)l++;       
            ma[i][j-p+]=a[i][q[l]];
        }
        l=;r=;q[0]=;a[i][]=-e9;
        for(int j=;j<p;j++){
            while(r>=l&&a[i][q[r]]>=a[i][j])r--;
            q[++r]=j;
        }
        for(int j=p;j<=m;j++){
            while(r>=l&&a[i][q[r]]>=a[i][j])r--;
            q[++r]=j;
            while(q[l]+p-<j)l++;       
            mi[i][j-p+]=a[i][q[l]];
        }
    }
    for(int j=;j<=m-p+;j++){
        l=;r=;q[0]=;a[][j]=e9+;
        for(int i=;i<p;i++){
            while(r>=l&&ma[q[r]][j]<=ma[i][j])r--;
            q[++r]=i;
        }
        for(int i=p;i<=n;i++){
            while(r>=l&&ma[q[r]][j]<=ma[i][j])r--;
            q[++r]=i;
            while(q[l]+p-<i)l++;       ;
            ma[i-p+][j]=ma[q[l]][j];
        }
        l=;r=;q[0]=;a[][j]=-e9;
        for(int i=;i<p;i++){
            while(r>=l&&mi[q[r]][j]>=mi[i][j])r--;
            q[++r]=i;
        }
        for(int i=p;i<=n;i++){
            while(r>=l&&mi[q[r]][j]>=mi[i][j])r--;
            q[++r]=i;
            while(q[l]+p-<i)l++;       
            mi[i-p+][j]=mi[q[l]][j];
        }
    }
//  cout<<endl;for(int i=;i<=n;i++){
//  for(int j=;j<=m;j++)cout<<ma[i][j]<<' ';cout<<endl;}
    ans=e9;
    for(int i=;i<=n-p+;i++)
    for(int j=;j<=m-p+;j++)ans=min(ans,ma[i][j]-mi[i][j]);
    printf("%d",ans);
}