LOJ-6279-数列分块入门3(分块, 二分)

题目描述

给定一个长度为n的序列a，有m次询问。每次询问给定l, r, k，要求区间[l, r]中第k小的数。

输入格式

第一行两个整数n,m。 接下来一行n个整数，表示序列a。 接下来m行，每行三个整数l,r,k。

输出格式

对于每个询问，输出一行一个数，表示区间[l, r]中第k小的数。

输入样例

5 3
1 3 2 4 5
1 5 2
2 4 1
3 5 3

输出样例

2
3
5

算法1

(分块) $O(n\sqrt n)$

我们可以预处理出每一个块的信息，每个块又分为若干小块，每个小块中的数都小于等于块中的最大值，可以用二分查找确定小块中满足条件的数的个数，然后用根号分治处理。

时间复杂度

每次查询的时间复杂度是 $O(\sqrt n\log n)$ 的，总时间复杂度是 $O(n\sqrt n\log n)$ 的。

参考文献

算法竞赛进阶指南

C++ 代码

算法2

(二分答案) $O(n\log^2n)$

我们二分答案，然后统计序列中小于等于这个答案的数的个数，统计方法可以用归并排序，在时间复杂度 $O(n\log n)$ 的时间内完成。

时间复杂度

每次查询的时间复杂度是 $O(n\log^2n)$ 的，总时间复杂度是 $O(mn\log^2n)$ 的。

参考文献

算法竞赛进阶指南

C++ 代码

相关问题

/lib/x86_64-linux-gnu/libc.so.6: version `GLIBC_2.34' not found (required by ./loj_judger_server)

这个错误是因为你的系统中缺少 GLIBC 2.34 版本的库，而 ./loj_judger_server 需要这个版本的库来运行。GLIBC 是 GNU C 库，它是 Linux 系统中的一个重要的 C 库，提供了许多系统调用和其他功能。

要解决这个问题，有几种方法可以尝试：

1. 更新你的操作系统：尝试更新你的 Linux 操作系统，以获取最新版本的 GLIBC 库。这可能需要管理员权限。

2. 安装所需的 GLIBC 版本：如果你无法更新整个操作系统，你可以尝试手动安装所需版本的 GLIBC。你可以从 GNU 的官方网站下载 GLIBC 的源代码，并按照它们的说明进行编译和安装。

3. 使用容器或虚拟机：如果更新操作系统或手动安装 GLIBC 版本过于复杂，你可以考虑使用容器技术（如Docker）或虚拟机来创建一个独立的运行环境，其中包含所需的 GLIBC 版本。

请注意，对于特定的应用程序和环境，可能还有其他解决方案适用。如果上述方法无法解决问题，我建议你查看相关文档或向应用程序的开发者寻求支持。

有源汇有上下界的最小流（LOJ117）

这是一个IT类问题。该问题可以使用网络流算法解决。首先用 Dinic 或 ISAP 算法求出最大流，然后根据最大流的值和边的上下界，构造一个新图，使得原图中的每条边都对应着新图中的一些流量限制。具体地，对于一条容量为$c$，下界为$l$，上界为$u$的边$(u,v)$，我们在新图中从$u$向$v$连一条容量为$u-l$的边和一条容量为$u-l$，费用为$c$的边，再从源点向$u$连一条容量为$l$的边，费用为$0$，最后从$v$向汇点连一条容量为$l$的边，费用为$0$。在新图上跑一遍费用流，如果总流量等于原图的最大流，则新图中的最小费用即为所求最小流，否则原图不存在满足上下界的流。