作者:滚猪儿 | 来源:互联网 | 2023-10-10 04:05
这题应该有更简单的方法做,本人太懒,直接暴力线段树+优先队列了,刚好卡时间过
#include
#include
#include
#include
#include
using namespace std;
typedef long long LL;
typedef pairpii;
const int mod = 1e9 + 7 , INF = 0x3f3f3f3f , N = 1e5 + 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 }