先来个简单的
BZOJ1342 Sound静音问题https://www.lydsy.com/JudgeOnline/problem.php?id=1342
image.png
注意理解：
用单调增加的队列维护最小值
i 从1到 n 枚举，每一个 a[i] 都会加入队列，但 a[i] 加入队列前会重复在队尾比 a[i] 大的元素删除，也就是说，比 a[i] 小的元素一定是安全的。而该队列单增，则最小值一定是队首元素。当队首元素不在当前区间时，删除队首元素后，新的队首元素一定是当前区间的最小值。
用单调减小的队列维护最大值
同理。
#include<bits/stdc++.h>
using namespace std;
static const int Maxn = 1000010;
int a[Maxn], q1[Maxn], q2[Maxn], id1[Maxn], id2[Maxn];
int main()
{
int n, m, c, l1, l2, r1, r2, flag = 0;
//cin >> n >> m >> c;
scanf("%d%d%d", &n, &m, &c);
for(int i = 1; i <= n; i++) cin >> a[i];
l1 = l2 = 1;
r1 = r2 = 0;
for(int i = 1; i <= n; i++){
while(l1 <= r1 && i - id1[l1] >= m) l1++;
while(l2 <= r2 && i - id2[l2] >= m) l2++;
while(l1 <= r1 && a[i] <= q1[r1]) r1--;
while(l2 <= r2 && a[i] >= q2[r2]) r2--;
q1[++r1] = q2[++r2] = a[i];
id1[r1] = id2[r2] = i;
if(i >= m && q2[l2] - q1[l1] <= c){
//cout << i - m + 1 << endl;
printf("%d\n", i - m + 1);
flag = 1;
}
}
if(!flag) printf("NONE");//cout << "NONE" << endl;
return 0;
}
居然会卡cin和cout？？？长见识了
单调队列升级版
BZOJ1047 理想的正方形 https://www.lydsy.com/JudgeOnline/problem.php?id=1047
这道题其实也就是用好多好多单调队列。。。
先用单调队列找到每一行（记为h）从位置 i 开始的n个元素中的最大值和最小值，记为 Max[h][i] 和 Min[h][i];
然后用单调队列找到每一列（记为k）区间n内Max[i][k]的最大值和Min[i][k]的最小值，用二者之差来更新ans。
#include<bits/stdc++.h>
using namespace std;
int M[1010][1010], Max[1010][1010], Min[1010][1010];
int q1[1010], q2[1010], id1[1010], id2[1010];//q1递增单调队列，维护Min
int main(){
int a, b, n, l1, l2, r1, r2, ans =2e9;
cin >> a >> b >> n;
for(int i = 1; i <= a; i++)
for(int j = 1; j <= b; j++) scanf("%d", &M[i][j]);
for(int h = 1; h <= a; h++){
memset(q1, 0, sizeof(q1));
memset(q2, 0, sizeof(q2));
memset(id1, 0, sizeof(id1));
memset(id2, 0, sizeof(id2));
l1 = l2 = 1, r1 = r2 = 0;
for(int i = 1; i <= b; i++){
while(l1 <= r1 && i - id1[l1] >= n) l1++;
while(l2 <= r2 && i - id2[l2] >= n) l2++;
while(l1 <= r1 && q1[r1] >= M[h][i]) r1--;
while(l2 <= r2 && q2[r2] <= M[h][i]) r2--;
id1[++r1] = id2[++r2] = i;
q1[r1] = q2[r2] = M[h][i];
if(i >= n){
Max[h][i - n + 1] = q2[l2];
Min[h][i - n + 1] = q1[l1];
}
}
}
for(int k = 1; k <= b - n + 1; k++){
memset(q1, 0, sizeof(q1));
memset(q2, 0, sizeof(q2));
memset(id1, 0, sizeof(id1));
memset(id2, 0, sizeof(id2));
l1 = l2 = 1; r1 = r2 = 0;
for(int i = 1; i <= a; i++){
while(l1 <= r1 && i - id1[l1] >= n) l1++;
while(l2 <= r2 && i - id2[l2] >= n) l2++;
while(l1 <= r1 && q1[r1] >= Min[i][k]) r1--;
while(l2 <= r2 && q2[r2] <= Max[i][k]) r2--;
id1[++r1] = id2[++r2] = i;
q1[r1] = Min[i][k];
q2[r2] = Max[i][k];
if(i >= n) ans = min(q2[l2] - q1[l1], ans);
}
}
cout << ans << endl;
return 0;
}
初始化初始化初始化！！！
