- 综合排序
- 最热优先
- 最新优先
- 来自专栏wym
RMQ——模板
RMQ（rang minimun/maximun query，区间最佳查询）的主要思想是动态规划。 假设有序列a,其长度为n。
48410发布于 2018-08-30 - 来自专栏数据结构与算法
RMQ算法
一.概述 RMQ（Range Minimum/Maximum Query），即区间最值查询，是指这样一个问题：对于长度为n的数列A，回答若干询问RMQ（A,i,j）(i,j<=n)，返回数列A中下标在
77270发布于 2018-04-13 - 来自专栏XINDOO的专栏
POJ 3264 RMQ
代码： //poj 3263 RMQ //2013-07-30-21.39 #include <stdio.h> #include <string.h> #include <algorithm> using [j-1]); dmin[i][j] = min(dmin[i][j-1], dmin[i+(1<<(j-1))][j-1]); } } } int RMQ init(n); while (q--) { scanf("%d %d", &l, &r); printf("%d\n", RMQ
45710发布于 2021-01-21 - 来自专栏数据结构与算法
3339: Rmq Problem
Description image.png Input image.png Output image.png Sample Input 7 5 0 2 1 0 1 3 2 1 3 2 3 1 4 3 6 2 7 Sample Output 3 0 3 2 4 HINT image.png Source By X 裸地莫队题目， 每次加入一个数，如果当前答案等于加入的数，就暴力向上加 每次删除一个数，如果删除的那个数比当前的答案小，那么当前的答案就赋值程这个数 因
775110发布于 2018-04-12 - 来自专栏宫水三叶的刷题日记
【RMQ 专题】关于 RMQ 的若干解法（内含彩蛋）
Tag : 「优先队列（堆）」、「线段树」、「分块」、「单调队列」、「RMQ」 给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。 提示： 1 <= nums.length <= 10^5 -10^4 <= nums[i] <= 10^4 1 <= k <= nums.length 优先队列（堆） 根据题意，问题本质是 RMQ 构造答案复杂度为 O(n\times\sqrt{k}) （即 query 操作复杂度为 O(\sqrt{k}) ，最多有 n 次查询） 空间复杂度： \frac{n}{\sqrt{k}} 单调队列 关于 RMQ
85820编辑于 2022-11-01 - 来自专栏数据结构与算法
RMQ求LCA
题目链接 rmq求LCA，interesting。 一直没有学这玩意儿是因为CTSC的Day1T2，当时我打的树剖LCA 65分，gxb打的rmq LCA 45分。。。 不过rmq理论复杂度还是小一点的，就学一下把。 RMQ求LCA 我们要用到三个数组 $dfn[i]$:第$i$个节点位置的时间戳 $id[i][j]$：在欧拉序中$i$到$i + 2^j - 1$这段区间内深度最小的节点编号 $dep[i]$：第$i if((to = v[x][i]) == fa) continue; dfs(to, x); id[++tot][0] = x; } } void RMQ int x = read(), y = read(); v[x].push_back(y); v[y].push_back(x); } dfs(S, 0); RMQ
72260发布于 2018-09-30 - 来自专栏challenge filter
树状数组、线段树与RMQ
RMQ Range Maximum query，区间查找算法。同样出现在刘汝佳的书里面。该算法的核心是二分法，就是将对一个区间的查找转变为对不断二分的子区间的查找，其中子区间长度均为2的倍数。 代码 void rmq_init() { for(int i=1;i<=N;i++) dp[i][0]=arr[i];//初始化 for(int j=1;(1<<j)<= 查询 假设需要查询区间[l,r]的最小值，令k=log2(r-l+1)，区间最小值RMQ[l,r] = min(dp[l][k], dp[r - (1 « k) + 1][k]);，即从左边和右边同时开始搜索的最小值 毕竟RMQ每次修改后都要更新一遍dp数组，速度其实也不快。 核心思想也是二分法，把大区间分成两个小区间管理，直到区间长度为1为止。
87220编辑于 2022-06-17 - 来自专栏blog(为什么会重名，真的醉了)
动态规划-RMQ问题（ST算法）
文章目录 RMQ问题 ST算法 模板 例题 P2251 质量检测 P1816 忠诚 P2216 [HAOI2007]理想的正方形 RMQ问题 RMQ（Range Minimum/Maximum Query 矩阵中的所有数都不超过1,000,000,000 （2）20%的数据2<=a,b<=100,n<=a,n<=b,n<=10 （3）100%的数据2<=a,b<=1000,n<=a,n<=b,n<=100 二维RMQ
1K30编辑于 2021-12-31 - 来自专栏OI
CF803G Periodic RMQ Problem
CF803G Periodic RMQ Problem Description 题目链接：CF803G 一个序列 {a_i} 由 k 个长度为 n 的序列 {b_i} 拼接而成，支持 q 个操作 然后把所有操作离线下来，离散化，拆成每个点以及两个点间的区间，先用 RMQ 预处理出离散化后每个点的初值，然后再套个线段树动态维护一下最小值即可。 int N=1e5+10; int n,k,b[N],q,o[N<<1],cnt,tot,w[N<<2],id[N<<2]; struct Que{int op,l,r,x;}c[N]; class RMQ
31010编辑于 2022-09-19 - 来自专栏CSDN旧文
图论--LCA--在线RMQ ST
include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int MAXN = 10010; int rmq [2 * MAXN]; // rmq数组,就是欧拉序列对应的深度序列 struct ST { int mm[2 * MAXN]; int dp[2 * MAXN][ [dp[i][j - 1]] < rmq[dp[i + (1 << (j - 1))][j - 1]] ? if (a > b) { swap(a, b); } int k = mm[b - a + 1]; return rmq [dp[a][k]] <= rmq[dp[b - (1 << k) + 1][k]] ?
55920发布于 2020-10-28 - 来自专栏Zaqdt_ACM
NYOJ 119 士兵杀敌(三) (RMQ)
RMQ (Range Minimum/Maximum Query)问题是指：对于长度为n的数列A，回答若干询问RMQ(A,i,j)(i,j<=n)，返回数列A中下标在i,j里的最小( 大）值，也就是说，RMQ问题是指求区间最值的问题。 RMQ标准算法：先规约成LCA(Lowest Common Ancestor)，再规约成约束RMQ，O(n)-O(q) online。 LCA问题可以在线性时间内规约为约束RMQ，也就是数列中任意两个相邻的数的差都是+1或-1的RMQ问题。约束RMQ有O(n)-O(1)的在线解法，故整个算法的时间复杂度为O(n)-O(1)。 pid=119 这道题就是一道RMQ的问题，这里我用了ST算法来解，求出区间的最大值和最小值，然后输出差值。没什么好说的，RMQ的ST解法的模板题吧算是。
58020发布于 2019-01-11 - 来自专栏wym
POJ 3264 Balanced Lineup (RMQ模板题)
传送门 #include <algorithm> #include <stdio.h> using namespace std; const int maxn=50005; int a[maxn]; int dp[maxn][20]; int dp2[maxn][20]; int n; void init() { for(int i=1;i<=n;i++) dp[i][0]=a[i],dp2[i][0]=a[i]; for(int j=1; (1<<j) <= n ;j++) for(
46120发布于 2018-08-30 - 来自专栏glm的全栈学习之路
天才的记忆(区间RMQ）
思路：区间RMQ，本质是动态规划 #include<bits/stdc++.h> using namespace std; const int N=2e5+10,M=20; int n,m,a[N],
32330发布于 2021-03-08 - 来自专栏CSDN旧文
关于RMQ问题的四种解法
什么是RMQ问题： RMQ (Range Minimum/Maximum Query)：对于长度为n的数组A，回答若干询问RMQ(A,i,j)(i,j<=n-1)，返回数组A中下标在i,j范围内的最小 （大）值，也就是说，RMQ问题是指求区间最值的问题。
88810发布于 2020-10-28 - 来自专栏小樱的经验随笔
RMQ问题(线段树算法，ST算法优化)
RMQ (Range Minimum/Maximum Query)问题是指： 对于长度为n的数列A，回答若干询问RMQ(A,i,j)(i,j<=n)，返回数列A中下标在[i,j]里的最小(大）值，也就是说 ，RMQ问题是指求区间最值的问题 主要方法及复杂度(处理复杂度和查询复杂度)如下: 1.朴素（即搜索） O(n)-O(n) 2.线段树(segment tree) O(n)-O(qlogn) 使用线段树解决RMQ问题，关键维护一个数组M[num]，num=2^(线段树高度+1). M[i]:维护着被分配给该节点(编号:i 线段树根节点编号:1)的区间的最小值元素的下标。 个数) 14 *dp[i][j]=min{dp[i][j-1],dp[i+2^(j-1)][j-1]} 15 *查询RMQ rmq(int s,int v) 16 *将s-v 分成两个2^k的区间 17 (0,9)<<endl; 61 cout<<rmq(4,9)<<endl; 62 return 0; 63 }
1.3K60发布于 2018-04-08 - 来自专栏CSDN旧文
ST函数（ST表）RMQ O(1)查询 离线
ST算法是基于倍增的动态规划算法。 #include<iostream> #include<cstdio> #include<cstdlib> #include<cmath> using namespace std; int map[1000005][20]; int N,K; void work() { int i,j; for(j=1;1<<j<=N;j++) for(i=1;i+(1<<j)-1<=N;i++)//i+(1<<j)-1<=n是为了保证区间左端点不超出总数n
64330发布于 2020-10-28 - 来自专栏数据结构与算法
BZOJ4516: 生成魔咒(后缀数组 set RMQ)
首先，本质不同的子串的个数 $ = \frac{n(n + 1)}{2} - \sum height[i]$
50020发布于 2018-12-19 - 来自专栏ACM算法日常
RMQ算法 NYOJ-119 士兵杀敌（三）
样例输入 5 2 1 2 6 9 3 1 2 2 4 样例输出 1 7 概述 RMQ（Range Minimum/Maximum Query），即区间最值查询，是指这样一个问题：对于长度为n的数列A，回答若干询问 RMQ（A,i,j）(i,j<=n)，返回数列A中下标在i，j之间的最小/大值。 查询 假设我们需要查询区间[l, r]中的最小值，令k = log2(r - l + 1); 则区间[l, r]的最小值RMQ[l,r] = min(mn[l][k], mn[r - (1 << k) 我们来举个例子 l = 4, r = 6; 此时k = log2(r - l + 1) = log2(3) = 1; 所以RMQ[4, 6] = min(mn[4][1], mn[5][1]); mn[4][1] = 4, mn[5][1] = 2; 所以RMQ[4, 6] = min(mn[4][1], mn[5][1]) = 2; 我们很容易看出来了答案是正确的。
54930发布于 2018-12-12 【POJ】3264 - Balanced Lineup（RMQ - ST算法 || 线段树）
0x3f3f3f3f #define MAX 50000 int n,q; int num[MAX+11]; int maxx[MAX+11][25]; int minn[MAX+11][25]; void RMQ (int i = 1 ; i <= n ; i++) { scanf ("%d",&num[i]); maxx[i][0] = minn[i][0] = num[i]; } RMQ
25310编辑于 2025-08-26- 来自专栏数据结构与算法
BZOJ 3489: A simple rmq problem(K-D Tree)
因为是OJ上的题，就简单点好了。给出一个长度为n的序列，给出M个询问：在[l,r]之间找到一个在这个区间里只出现过一次的数，并且要求找的这个数尽可能大。如果找不到这样的数，则直接输出0。我会采取一些措施强制在线。
69350发布于 2019-02-13
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号