蓝桥杯2022年第十三届JAVAB组省赛真题最大子矩阵

 这题应该有更简单的方法做&＃xff0c;本人太懒&＃xff0c;直接暴力线段树&＃43;优先队列了&＃xff0c;刚好卡时间过

#include
#include
#include
#include
#include
using namespace std;
typedef long long LL;
typedef pairpii;
const int mod &＃61; 1e9 &＃43; 7 , INF &＃61; 0x3f3f3f3f , N &＃61; 1e5 &＃43; 10;int g[100][2 * N];
int n,m;
int limit;
struct edge1
{int v;int id;bool operator <(const edge1 & w)const{if (v !&＃61; w.v)return v w.id;}
};
struct edge2
{int v;int id;bool operator <(const edge2 & w)const{if (v !&＃61; w.v)return v > w.v;return id > w.id;}
};
struct Node
{int l,r;int minv;int maxv;
}tr[N * 4];void push_up(int x)
{tr[x].minv &＃61; min(tr[x <<1].minv,tr[x <<1 | 1].minv);tr[x].maxv &＃61; max(tr[x <<1].maxv,tr[x <<1 | 1].maxv);
}
void build(int x,int l,int r)
{tr[x] &＃61; {l,r};if (l &＃61;&＃61; r){int w &＃61; g[(r - 1) % n &＃43; 1][(r - 1) / n &＃43; 1];tr[x] &＃61; {l,r,w,w};return;}int mid &＃61; l &＃43; r >> 1;build(x <<1,l,mid);build(x <<1 | 1,mid &＃43; 1,r);push_up(x);
}int queryMin(int x,int l,int r)
{if (tr[x].l >&＃61; l && tr[x].r <&＃61; r)return tr[x].minv;int mid &＃61; tr[x].l &＃43; tr[x].r >> 1;int minv &＃61; INF;if (l <&＃61; mid)minv &＃61; queryMin(x <<1,l,r);if (r > mid)minv &＃61; min(minv,queryMin(x <<1 | 1,l,r));return minv;
}int queryMax(int x,int l,int r)
{if (tr[x].l >&＃61; l && tr[x].r <&＃61; r)return tr[x].maxv;int mid &＃61; tr[x].l &＃43; tr[x].r >> 1;int maxv &＃61; -1;if (l <&＃61; mid)maxv &＃61; queryMax(x <<1,l,r);if (r > mid)maxv &＃61; max(maxv,queryMax(x <<1 | 1,l,r));return maxv;
}void init()
{cin >> n >> m;for (int i &＃61; 1 ; i <&＃61; n ; i &＃43;&＃43;)for (int j &＃61; 1 ; j <&＃61; m ; j &＃43;&＃43;) cin >> g[i][j];cin >> limit;build(1,1,n * (m &＃43; 1));
}int getMin(int i1,int j1,int i2,int j2)
{int a &＃61; i1 &＃43; n * (j1 - 1);int b &＃61; i2 &＃43; n * (j2 - 1);return queryMin(1,a,b);
}int getMax(int i1,int j1,int i2,int j2)
{int a &＃61; i1 &＃43; n * (j1 - 1);int b &＃61; i2 &＃43; n * (j2 - 1);return queryMax(1,a,b);
}int main()
{init();int res &＃61; 0;for (int i1 &＃61; 1 ; i1 <&＃61; n ; i1 &＃43;&＃43;)for (int i2 &＃61; i1 ; i2 <&＃61; n ; i2 &＃43;&＃43;){priority_queue q1;priority_queue q2;for (int l &＃61; 1,r &＃61; 1; r <&＃61; m ; r &＃43;&＃43;){int maxv &＃61; getMax(i1,r,i2,r);int minv &＃61; getMin(i1,r,i2,r);if (maxv - minv > limit){while (q1.size())q1.pop();while (q2.size())q2.pop();l &＃61; r &＃43; 1;continue;}while (q1.size() && q1.top().v <&＃61; maxv)q1.pop();q1.push({maxv,r});while (q2.size() && q2.top().v >&＃61; minv)q2.pop();q2.push({minv,r});while (q1.top().v - q2.top().v > limit){l &＃43;&＃43;;while (q1.size() && q1.top().id }