第三次模拟延续了前两次模拟的一贯风格（水的一批 ），虽然都不难，还是有几道还行的题目，下面讲解最后一题，以此来复习一下前面学过的知识

问题描述:

小蓝有一个序列a[1],a[2],…,a[n]。给定一个正整数k，请问对于每一个1到n之间的序号i.a[i-k]，a[i-k+1]…a[i+K]
这2k+1个数中的最小值是多少？当某个下标超过1到n的范围时，数不存在，求最小值时只取存在的那些值。

输入格式：

输入的第一行包含一整数n。 第二行包含n个整数，分别表示 a[1],a[2],…,a[n]。 第三行包含一个整数k

输出格式：

输出一行，包含n个整数，分别表示对于每个字号求得的最小值

样例输入：

5
5 2 7 4 3
1

样例输出：

2 2 2 3 3

评测用例规模与约定

对于 30% 的评测用例，1 <= n <= 1000，1 <= a[i] <= 1000。
对于 50% 的评测用例，1 <= n <= 10000，1 <= a[i] <= 10000。
对于所有评测用例，1 <= n <= 1000000，1 <= a[i] <= 1000000

思路1：树状数组

首先说树状数组
先挖掘一下题意，遍历序列，对于遍历的元素的一段区间，求最值。随着遍历的进行，区间内的元素在变化，也就是说要修改元素，对于区间最值，我们可以使用二分的方法来查找。
具体的做法是，维护一个关于当前遍历的元素一定大小区间(2k + 1)记录数值的树状数组。每一次遍历通过二分查找，查找这段区间数值的最小值。

代码

N = 100010tr = [0] * N
a = [0] * Ndef lowbit(x) : return x & -xdef add(x, c) :i = xwhile i <= n :tr[i] += ci += lowbit(i)def ask(x) :res = 0i = xwhile i :res += tr[i]i -= lowbit(i)return resdef init() : # 初始化，将第一个元素右边的m个元素初始化树状数组for i in range(1, m + 1) :add(a[i], 1)n = int(input())
a[1 : n + 1] = list(map(int, input().split()))
maxn = max(a[1 : n + 1])
m = int(input())
init()
for i in range(1, n + 1) : if i + m <= n : # 随着区间的挪动添加元素add(a[i + m], 1)if i - m - 1 >= 1 : # # 随着区间的挪动删除元素add(a[i - m - 1], -1)l, r = 0, maxn # 二分查找，右半段查找最小值while l < r :mid = (l + r) >> 1if ask(mid) >= 1 :r = midelse :l = mid + 1print(l, end = " ")

思路2：滑动窗口

通过上面的描述，显然说的就是滑动窗口啊。
维护一个窗口大小为2 * k + 1的单调递减队列即可。

代码

N = 1000010a = [0] * N
q = [0] * Nn = int(input())a[1 : n + 1] = list(map(int, input().split()))m = int(input())hh, tt = 0, -1def init() : # 初始化，将前m个进队列，这时只需要保持单调性即可global ttfor i in range(1, m + 1) :while hh <= tt and a[q[tt]] >= a[i] :tt -= 1tt += 1q[tt] = i
init()for i in range(m + 1, n + m + 1) :while hh <= tt and i - q[hh] + 1 > 2 * m + 1 :hh -= 1if i <= n : # 防止序列越界while hh <= tt and a[q[tt]] >= a[i] :tt -= 1tt += 1q[tt] = iprint(a[q[hh]], end = " ")

思路3：线段树

思路同树状数组，区间查询。

N = 1000010class Tree :def __init__(self) :self.l = 0self.r = 0self.v = 0tr = [Tree() for _ in range(N * 4)]
a = [0] * Ndef pushup(u) :tr[u].v = min(tr[u << 1].v, tr[u << 1 | 1].v)def build(u, l, r) :tr[u].l, tr[u].r = l, rif l == r :tr[u].v = a[l]returnmid = l + r >> 1build(u << 1, l, mid)build(u << 1 | 1, mid + 1, r)pushup(u)def query(u, l, r) :if l <= tr[u].l and tr[u].r <= r :return tr[u].vres = 10000010mid = tr[u].l + tr[u].r >> 1if l <= mid :res = query(u << 1, l, r)if r > mid :res = min(res, query(u << 1 | 1, l, r))return resn = int(input())a[1 : n + 1] = list(map(int, input().split()))m = int(input())
build(1, 1, n)for i in range(1, n + 1) :l, r = max(1, i - m), min(i + m, n)print(query(1, l, r), end = " ")

思路4：RMQ

from math import logN = 1000010a = [0] * N
f = [[1000010] * 25 for _ in range(N)]n = int(input())a[1 : n + 1] = list(map(int, input().split()))
m = int(input())def init() : # 预处理st表for i in range(1, n + 1) :f[i][0] = a[i]k = int(log(n, 2)) + 1for length in range(1, k) :for l in range(1, n + 1) :r = l + (1 << length) - 1if r > n : breakf[l][length] = min(f[l][length - 1], f[l + (1 << (length - 1))][length - 1])def query(l, r) :k = int(log(r - l + 1, 2))return min(f[l][k], f[r - (1 << k) + 1][k])init()for i in range(1, n + 1) :l, r = max(1, i - m), min(i + m, n)print(query(l, r), end = " ")