RMQ

稀疏表（Sparse Table表） 解决静态RMQ，区间最值查询问题的数据结构，树状数组（BIT）解决动态前缀和问题的数据结构； 例：https://www.luogu.org/problemnew/show/P3865 　　　　原理:把给定区间分成长度是2的...

题目描述 给定N个数的序列和M次询问，每次询问给定左右端点区间中的最大值 输入样例: 6 (N) 34 1 8 123 3 2 4 (M) 1 2 1 5 3 4 2 3 输出样例: 34 123 123 8 题目分析 虽然是另一类问题，但分析方法实际采用的是...

线段树＋RMQ问题第二弹 上篇文章讲到了基于Sparse Table 解决 RMQ 问题，不知道大家还有没有印象，今天我们会从线段树的方法对 RMQ 问题再一次讨论。 正式介绍今天解决 RMQ 问题的方法之前，我先对 RMQ 问题的...

给一个长度为n的数列a，q个询问，每次询问一段区间的mex。（没有出现过的最小非负整数） 1<=n,q<=200000，0<=ai<=200000。 题解1 莫队 我们将权值分成根号块，记录每个权值的出现次数和每块内有多少...

F. Strings and Queries time limit per test 2.5 s memory limit per test 256 MB input standard input output standard output You are given a set of n strings such that all characters in the strings ar...

BUAA 724 晴天小猪的神题 题意:中文题,略 题目链接:http://acm.buaa.edu.cn/problem/724/ 思路:对于询问x,y是否在同一区间,可以转换成有没有存在一个区间它的左端点小于等于x,右端点大于等于y 即小于等于x的所有...

rmq是一类询问区间最小/最大值的问题。 这类问题一般分成两类：静态区间（无修改），动态区间（带修改）。 对于动态区间查询最大/最小，我们显然可以用线段树来解决…… 那么对于静态区间查询最大/最...

题目描述 有一个a*b的整数组成的矩阵，现请你从中找出一个n*n的正方形区域，使得该区域所有数中的最大值和最小值的差最小。 输入输出格式 输入格式： 第一行为3个整数，分别表示a,b,n的值 第二行至第a+1行每行为b...

目录 1. 普通做法 2. Four Russian 算法 3. 随机数据的一种做法 4. 有关转 LCA 的做法 1.1. RMQ 转 LCA 再转 ±1RMQ（RMQ 标准算法） 1.2. 一个优化 2. RMQ 转 LCA 然后 tarjan 求 LCA 3. RMQ 转 LCA 然后 Schiebe...