首页 > 其他分享 >二维单调队列

二维单调队列

时间:2023-09-16 11:57:28浏览次数:52  
标签:队列 tt hh tot int 二维 最值 include 单调

单调队列通常用来解决区间最值问题。

二维单调队列用来在矩阵中找子矩阵的最值,即求a * b大小的子矩阵中的最大值与最小值。

做法: 我们先预处理出每行滑动窗口长度为b的最值,并将其放到窗口最右侧位置;如0~b - 1窗口的最值放到 下标为b - 1 的位置。

  处理完行后,我们对列进行处理,维护长度为a的滑动窗口,并将最值放到最下侧。  

  

 操作完后的子数组最值就在最右下角处。

 

 

 

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

const int N = 1010;

int n, m, k;
int w[N][N];
int row_min[N][N], row_max[N][N];
int q[N];

void get_min(int a[], int b[], int tot) {
    int hh = 0, tt = -1;
    for(int i = 1; i <= tot; i ++ ) {
        while(hh <= tt && q[hh] < i - k + 1) hh ++ ;
        while(hh <= tt && a[q[tt]] >= a[i]) tt -- ;
        q[ ++ tt] = i;
        b[i] = a[q[hh]];
    }
}

void get_max(int a[], int b[], int tot) {
    int hh = 0, tt = -1;
    for(int i = 1; i <= tot; i ++ ) {
        while(hh <= tt && q[hh] < i - k + 1) hh ++ ;
        while(hh <= tt && a[q[tt]] <= a[i]) tt -- ;
        q[ ++ tt] = i;
        b[i] = a[q[hh]];
    }
}

int main() {
    cin >> n >> m >> k;
    
    for(int i = 1; i <= n; i ++ ) {
        for(int j = 1; j <= m; j ++ ) {
            scanf("%d", &w[i][j]);
        }
    }
    
    for(int i = 1; i <= n; i ++ ) {
        get_min(w[i], row_min[i], m);
        get_max(w[i], row_max[i], m);
    }
    
    int res = 1e9;
    int a[N], b[N], c[N];
    for(int i = k; i <= m; i ++ ) {
        for(int j = 1; j <= n; j ++ ) a[j] = row_min[j][i];
        get_min(a, b, n);
        
        for(int j = 1; j <= n; j ++ ) a[j] = row_max[j][i];
        get_max(a, c, n);
        
        for(int j = k; j <= n; j ++ ) res = min(res, c[j] - b[j]);
    }
    
    cout << res << endl;
    
    return 0;
}

 

 

 

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

typedef long long LL;

const int N = 1010, MOD = 998244353;

int n, m, A, B;
int w[N][N];
int row_max[N][N], row_min[N][N];
int q[N];

void get_min(int a[], int b[], int tot, int k) {
    int hh = 0, tt = -1;
    for(int i = 1; i <= tot; i ++ ) {
        while(hh <= tt && q[hh] < i - k + 1) hh ++ ;
        while(hh <= tt && a[q[tt]] >= a[i]) tt -- ;
        q[ ++ tt] = i;
        b[i] = a[q[hh]];
    }
}

void get_max(int a[], int b[], int tot, int k) {
    int hh = 0, tt = -1;
    for(int i = 1; i <= tot; i ++ ) {
        while(hh <= tt && q[hh] < i - k + 1) hh ++ ;
        while(hh <= tt && a[q[tt]] <= a[i]) tt -- ;
        q[ ++ tt] = i;
        b[i] = a[q[hh]];
    }
}

int main() {
    scanf("%d%d%d%d", &n, &m, &A, &B);
    
    for(int i = 1; i <= n; i ++ ) {
        for(int j = 1; j <= m; j ++ ) {
            scanf("%d", &w[i][j]);
        }
    }
    
    for(int i = 1; i <= n; i ++ ) {
        get_min(w[i], row_min[i], m, B);
        get_max(w[i], row_max[i], m, B);
    }
    
    LL res = 0;
    int a[N], b[N], c[N];
    for(int i = B; i <= m; i ++ ) {
        for(int j = 1; j <= n; j ++ ) a[j] = row_max[j][i];
        get_max(a, b, n, A);
        
        for(int j = 1; j <= n; j ++ ) a[j] = row_min[j][i];
        get_min(a, c, n, A);
        
        for(int j = A; j <= n; j ++ ) res = (res + (LL)b[j] * c[j]) % MOD;
    }
    
    printf("%lld\n", res);
    
    return 0;
}

 

标签:队列,tt,hh,tot,int,二维,最值,include,单调
From: https://www.cnblogs.com/zk6696/p/17706521.html

相关文章

  • 用强化学习构建个性化的二维码
     技术概述AIGC在图像生成领域如火如荼,StableDiffusion加各种LORA,ControlNet,大家玩得不亦乐乎。但是基于扩散模型的方式,仍然存在很多问题,比如抽卡成功率过低,生成图像的细节仍需优化。具体到二维码生成,目前huggingface上的几个ControlNet确实可以生成不错的二维码和语义......
  • 用强化学习构建个性化的二维码
     技术概述AIGC在图像生成领域如火如荼,StableDiffusion加各种LORA,ControlNet,大家玩得不亦乐乎。但是基于扩散模型的方式,仍然存在很多问题,比如抽卡成功率过低,生成图像的细节仍需优化。具体到二维码生成,目前huggingface上的几个ControlNet确实可以生成不错的二维码和语义......
  • 深入研究消息队列06 高级功能
    27Topic分区订阅如何实现动态配置在消息队列里面,因为需要保持架构的简洁度,基于本地文件也是一种常用的方案。比如Kafka和Pulsar就是基于ZooKeeper来实现的动态配置,因为架构中已经集成了ZooKeeper。RocketMQ的Nameserver是一个缓存组件,没有实际的存储和Watch机制,无法......
  • 代码随想录算法训练营第10天| 232.用栈实现队列 ● 225. 用队列实现栈
    栈和队列232.用栈实现队列stack:queue:卡哥代码一个入栈,一个出栈,即可模拟队列的pop操作pop之前要检查出栈是否为空若为空,则排出入栈里所有的元素至出栈中classMyQueue{public:stack<int>stackIn;stack<int>stackOut;MyQueue(){......
  • 3 - 任务调度算法 & 同步与互斥 &队列
    之前的都是按照优先级不同允许抢占(不讲道理),不管你在做什么,轮到优先级最高的任务,直接抢占执行怎样才能讲道理呢?稍微等等嘛,等我做完活你再做 1支持抢占,0不支持抢占 同优先级任务是否交替执行,1交替0不交 空闲任务是否礼让其他任务礼让的话,自己的函数逻辑在时间片内只执行......
  • 前端生成二维码,qrcode使用说明,canvas查看大图
    生成二维码用于vue项目通过字符串转换生成二维码的三方插件安装插件npminstall--saveqrcode引入使用importQRCodefrom"qrcode"页面<!--放置二维码的容器--><canvas:id="'qrCode_id'+stringxxxxx"class="qrCode_style"></canvas><!--可......
  • 二维数组最大连续和
    最大相连男生importjava.util.Scanner;importjava.util.*;//注意类名必须为Main,不要有任何packagexxx信息publicclassMain{staticintrow;staticintcol;staticint[][]arr;staticint[][]offsets={{0,1},{1,0},{1,-1},{1,1}};......
  • 数组详解——一维数组,二维数组(初始化,存储,输入与输出……)
    概念相同元素的集合,存放>=1个数据类型相同1.一维数组typearr_name[常量值(元素个数)]存放在数组的值是数组元素,在创建数组时可以指定数组的大小和元素类型type是数组元素的类型,可以是char,short,int,float,也可以自定义1.1初始化完全初始化:intarr1[5]={1,2,3,4,5};不完全初始化:(......
  • POJ 2823 Sliding Window 单调队列
    这道题就是用单调队列来维护,但是用G++交TLE,用c++5000多ms,真是囧...代码很丑,就凑合着看吧#include<stdio.h>inta[1000009],que[1000009];intmain(){ intn,k,i,head,tail,flag=1,f; scanf("%d%d",&n,&k); for(i=1;i<=n;i++) scanf("%d",&a[i]); head=......
  • 二维数组的存储顺序、表示方法
    二维数组的存储顺序、表示方法先说一维数组:1.数组首地址也是第一个元素的首地址1#include<iostream>2usingnamespacestd;34intmain(){5intarr[5]={};6cout<<"arr="<<arr<<endl;7cout<<"&arr[0]=&q......