Rmq
P4137 Rmq Problem / mex
题意 给定一个长度为 \(n\) 的数组。 \(q\) 次询问，每次询问区间 \(mex\)。 Sol 考虑主席树维护区间 \(mex\)。 不难发现可以考虑维护当前所有点的最后出现的下标。 直接套板子即可。 Code #include <iostream> #include <algorithm> ......
【学习笔记】浅谈 RMQ 与 LCA
- $\text{update 2023.11.14}$：增加 $\text{LCA}$ 求解树上最短路的代码。 $\text{RMQ}$ 定义：区间最值查询，功能类 $\text{st}$ 表，预处理 $O(n\log_2n)$，查询 $O(q)$，总复杂度 $O(n \log _2n+q)$。 ......
ST表 RMQ（区间最大/最小值查询）问题
主要应用倍增思想预处理：O(nlogn) 查询：O(1)f[i][j]是以i为起点，长度为2j的区间中的最大值(一个点一个单位长度，不是一条线段)区间终点：i+2j-1<=n区间长度的指数k=log2(r-l+1)，只有当r-l+1为2n-1时是恰好分割，其他时候有重叠，但问题不大 代码 #incl ......
AI问答：基于ST表的RMQ问题
以下是一个基于ST表（Sparse Table）的RMQ（Range Maximum Query）问题的C++算法模板： #include<bits/stdc++.h> using namespace std; const int MAXN = 100005; const int LOGN = 20 ......
#P1042. 静态RMQ[ST表模板]
题意是：给定一个长度为 N 的数列，和 M 次询问，求出每一次询问的区间内数字的最大值。 ST表的基本功能是对区间进行查询，其核心使用的是倍增的思想 f[i][k]:意思是从第i个数开始往后2^k个数 f[i][k]=max(f[i][k-1],f[i+2^k-1][k-1]) 求【l,r】区间 m ......
CF803G Periodic RMQ Problem
题目描述 给你一个序列\(a\) 让你支持 \(1\) \(l\) \(r\) \(x\) 区间赋值 \(2\) \(l\) \(r\) 询问区间最小值 我们觉得这个问题太水了,所以我们不会给你序列\(a\) 而是给你序列一个长度为\(n\) 的序列\(b\) ,把\(b\) 复制粘贴\(k\) 次 ......
RMQ模板
#include <cstdio> #include <cstring> #include <algorithm> #include <cmath> using namespace std; const int N = 200010, M = 18; int n, m; int w[N]; int ......
P2251 质量检测(分块线段树RMQ单调队列)
P2251 质量检测 正解应该是ST表和单调队列，不过对于这道题来说只有查询没有修改，这里我还是想用线段树和分块来写，不得不说分块是真好，优雅的暴力 线段树版本： #include <bits/stdc++.h> #define LL long long using namespace std; c ......
RMQ
P3865 【模板】ST 表 利用倍增 f[i][j]表示，范围[i,i+2^(j)-1]内的最大值是多少 点击查看代码 #include<bits/stdc++.h> using namespace std; const int N = 1e5 + 10; int f[N][22]; int ma ......
分块+ST的RMQ
期望\(O(n)-O(1)的RMQ\) #include<bits/stdc++.h> #define int long long #define F(i0,i1,i2) for(int i0=(i1);i0<=(i2);++i0) using namespace std; inline int r ......
【树论】RMQ问题和ST表
[toc] # RMQ问题 RMQ（Range Maximum/Minimum Query）问题，即区间最值问题。 一般是多次询问，对时间复杂度要求高，一般需要 $O(logn)$ 或 $O(1)$ 复杂度 ## ST表 `p[i][j]` 是以i为起点，连续 $2^j$ 个数字的最大值(是一个递推 ......
RMQ问题中的ST算法
# RMQ问题中的ST算法 长为 n 的数组 a ，m次询问，求l~r中最大值是多少 ```cpp // RMQ问题中的ST算法 // m次询问，求l~r中最大值是多少 #include #define reg register using namespace std; // 读取输入的函数 inl ......
RMQ模板
template<calss T> struct RMQ { int n; vector<vector<T>> f; vector<int> log_2; vector<T> a; function <T(T, T)> cmp; RMQ() {} RMQ(int n, function<T(T, T ......
2023ACM暑假训练day 7-RMQ问题
[toc] # DAY 7 RMQ问题 训练地址：[传送门](https://vjudge.net/contest/566701) ## 训练情况简介 2023-07-03 星期一 早上： 下午： 晚上： ## 题 **题意：** **思路：** ......
（炒冷饭）线性 RMQ
之前一直在用别人写的线性 $\text{RMQ}$ 板子，但是我自己一直不会写。 所以去年退役以后，有一天学文化课的过程中走神想了这个。 不过现在这个东西是不是人人都会呢…… 下面是我的想法，不过很久以前就已经被发明过了。 本来这玩意儿不值得发一篇博客的，但毕竟已经从文化课中解放了，想要发点什么庆祝 ......
静态RMQ处理方式合辑
这里汇集了所有我知道的静态区间最大值做法。 ### $O(n)$ 预处理，$O(n)$ 回答。 每一次询问暴力处理即可。 ### $O(n^2)$ 预处理，$O(1)$ 回答。 预处理出所有的答案。 ### $O(n)$ 预处理，$O(\log n)$ 回答。 维护一棵线段树。 ### $O(n\l ......
6573: 天才的记忆 RMQ
描述 从前有个人名叫 W and N and B，他有着天才般的记忆力，他珍藏了许多许多的宝藏。在他离世之后留给后人一个难题（专门考验记忆力的啊！），如果谁能轻松回答出这个问题，便可以继承他的宝藏。 题目是这样的：给你一大串数字（编号为 1 到 N，大小可不一定哦！），在你看过一遍之后，它便消失在你 ......
6571: 最敏捷的机器人 RMQ
描述 Wind 设计了很多机器人。但是它们都认为自己是最强的，于是，一场比赛开始了…… 机器人们都想知道谁是最敏捷的，于是它们进行了如下一个比赛。首先，他们面前会有一排共 n 个数，它们比赛看谁能最先把每连续 k 个数中最大和最小值写下来，当然，这些机器人运算速度都很快，它们比赛的是谁写得快。 但是 ......
RMQ——询问区间最大最小值问题
RMQ 如题：作用是询问区间最大最小值问题 步骤： 1.定义 a[i]表示数列的数 lg数组是一个辅助数组，用于快速计算查询区间的长度对应的k值。具体来说，lg[i]表示以2为底，i的对数。在C++中，可以使用lg2函数来计算以2为底的对数 f[i][j]表示从a[i]到a[i+2^i-1]这个范围 ......
最近公共祖先 RMQ
就是把LCA问题转化为RMQ问题 转化之前先要了解欧拉序列：对一棵树进行 DFS，无论是第一次访问还是回溯，每次到达一个结点时都将编号记录下来，可以得到一个长度为 2n-1 的序列，这个序列被称作这棵树的欧拉序列。 比如下面这个树：(2连3和4) 1->2->3 ->4->5 其序列就是1 2 3 ......
【rmq】洛谷P7333
题目：P7333 [JRKSJ R1] JFCA - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 分析：用rmq处理出各个区间长度的最大值，然后在二分区间长度找到答案 （最开始想的是开长度为n的数组，对位置i的数，分别找1-（i-1）和（i+1）-n中的离i最近满足条件的位置，然后 ......