根据此题首次学到二阶差分 Trick，好题。
题意
给出一个序列 \(\{a_n\}\)，满足 \(n \le 10^6, 1 \le a_i \le 10^9\)，定义函数 \(f(i, k)\) 为：
\[f(i, k) = \min\limits_{j=i}^{i+k-1} a_j \]你需要回答 \(m\) 个询问，每次询问给出一个整数 \(k\) ( \(1 \le k \le n\) )，求所有 \(f(i, k)\) ( \(1 \le i \le n-k+1\) ) 的平均数。
题解
首先可以直接求 \(\sum\limits_{i=1}^{n-k+1}f(i, k)\) 再用这个值除以 \(n-k+1\) 就得到答案，并且还可以预处理出所有 \(k\) 的答案得到序列 \(\{b_n\}\) 后 \(O(1)\) 回答询问。
注意到 \(f(i, k)\) 一定对应着原序列的一个 \(a\) 值，所以考虑枚举每一个 \(a_i\)，然后算 \(a_i\) 能贡献到哪些 \(f(j, k)\)。
所以肯定要单调栈求出 \(L_i\) 和 \(R_i\)，\(L_i\) 表示 \(i\) 左边的第一个 \(\le a_i\) 的下标，\(R_i\) 表示 \(i\) 右边第一个 \(>a_i\) 的下标，是 \(>\) 而不是 \(\ge\) 的原因是这样才能不算重不算漏。这里要设 \(a_0\) 和 \(a_{n+1}\) 是无穷小。
处理出 \(L_i\) 和 \(R_i\) 后，可以发现 \(i\) 可以贡献 \(f(j, k)\)，当且仅当 \(j \in (L_i, i], (j+k-1) \in [i, R_i)\)。我们发现贡献 \(f(j, k)\) 相当于将 \(b_k\) 加上了 \(a_i\)，我们只用看对于一个 \(k\)，\(a_i\) 贡献了多少次即可。那么将 \(j\) 从 \(i\) 往 \(L_i+1\) 扫，合法的 \(k\) 的范围是 \([i-j+1, R_i-j]\)，可以发现不管 \(j\) 怎么变，这个区间长度是不变的，恒为 \(R_i - i\)，\(j\) 的改变只影响了这个区间的位置而已，于是设 \(x=i-j+1, P = i - L_i, Q = R_i - i\)，则 \(x \in [1, P]\)，\(x\) 会贡献给区间 \([x, x + Q - 1]\)。
将每个 \(b_i\) 被贡献的次数写出来之后，发现被贡献的次数长这个样子：
\[1, 2, \cdots, (m-1), m, \cdots, m, \cdots, m, (m-1), \cdots, 2, 1, 0, 0, \cdots \]还可以得知 \(m = \min(P, Q)\)，于是分成三部分计算贡献，第一部分就是最开始的 \(1, 2, \cdots, (m-1)\)，第二部分就是中间连续的 \(m\)，第三部分就是最后的 \((m - 1), \cdots, 2, 1\)，可以直接用线段树来做，复杂度 \(O(n \log n)\)，代码：
#include <bits/stdc++.h>
#define rep(i, l, r) for (int i = l; i <= r; ++i)
#define per(i, r, l) for (int i = r; i >= l; --i)
#define re(i, n) for (int i = 0; i < n; ++i)
#define pe(i, n) for (int i = n - 1; i >= 0; --i)
#define bg begin()
#define ed end()
#define alls(a) a.bg, a.ed
using i64 = long long;
using namespace std;
const int N = 1E6 + 5;
int n, a[N], L[N], R[N];
i64 Ans[N];
struct segt {
struct node {
int i;
i64 sum;
i64 add0, add1;
} t[N << 2];
void build(int x, int l, int r) {
t[x].add0 = t[x].add1 = 0;
if (l + 1 == r) {t[x].i = r; return ;}
int mid = (l + r) / 2;
build(x * 2, l, mid);
build(x * 2 + 1, mid, r);
}
void apply0(int x, i64 tag) {
t[x].sum += t[x].i * tag;
t[x].add0 += tag;
}
void apply1(int x, i64 tag) {
t[x].sum += tag;
t[x].add1 += tag;
}
void push(int x) {
apply0(x * 2, t[x].add0);
apply0(x * 2 + 1, t[x].add0);
apply1(x * 2, t[x].add1);
apply1(x * 2 + 1, t[x].add1);
t[x].add0 = t[x].add1 = 0;
}
void modify0(int x, int l, int r, int L, int R, i64 v) {
if (L >= R) return ;
if (l >= R || r <= L) return ;
if (l >= L && r <= R) return apply0(x, v);
int mid = (l + r) / 2; push(x);
modify0(x * 2, l, mid, L, R, v);
modify0(x * 2 + 1, mid, r, L, R, v);
}
void modify0(int L, int R, i64 v) {modify0(1, 0, n, L, R, v);}
void modify1(int x, int l, int r, int L, int R, i64 v) {
if (L >= R) return ;
if (l >= R || r <= L) return ;
if (l >= L && r <= R) return apply1(x, v);
int mid = (l + r) / 2; push(x);
modify1(x * 2, l, mid, L, R, v);
modify1(x * 2 + 1, mid, r, L, R, v);
}
void modify1(int L, int R, i64 v) {modify1(1, 0, n, L, R, v);}
void query(int x, int l, int r) {
if (l + 1 == r) {
Ans[r] = t[x].sum;
return ;
}
int mid = (l + r) / 2; push(x);
query(x * 2, l, mid);
query(x * 2 + 1, mid, r);
}
} seg;
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
cin >> n;
re(i, n) cin >> a[i];
seg.build(1, 0, n);
stack<int> st;
re(i, n) {
while (!st.empty() && a[st.top()] > a[i]) R[st.top()] = i, st.pop();
st.push(i);
} while (!st.empty()) R[st.top()] = n, st.pop();
pe(i, n) {
while (!st.empty() && a[st.top()] >= a[i]) L[st.top()] = i, st.pop();
st.push(i);
} while (!st.empty()) L[st.top()] = -1, st.pop();
re(i, n) {
int P = i - L[i], Q = R[i] - i;
int r = P + Q - 2;
int mx = min(P, Q);
int nl = mx - 1, nr = r - mx + 1;
seg.modify0(0, nl, a[i]);
seg.modify0(nr + 1, r + 1, -a[i]);
seg.modify1(nr + 1, r + 1, 1LL * a[i] * (r + 2));
seg.modify1(nl, nr + 1, 1LL * mx * a[i]);
} seg.query(1, 0, n);
int q; cin >> q; while (q--) {
int k, d; cin >> k; d = n - k + 1;
cout << setprecision(10) << fixed << 1.0 * Ans[k] / d << '\n';
}
}
交上去 2500ms 过题，点开题解区一看题解码长是我的三分之一，发现都要用二阶差分。想了一想，发现这种对区间 \([l, r]\) 执行 \(a_i += (i-l+1)*v\) 的操作不就是二阶差分板题吗？
二阶差分就是差分两遍，那么在一个位置 \(d_i\) 加上 \(v\)，差分两遍后就会往后产生 \(1, 2, \cdots\) 次的影响，与此题契合。时间复杂度 \(O(n)\)，代码也相当好写。下面是代码：
#include <bits/stdc++.h>
#define rep(i, l, r) for (int i = l; i <= r; ++i)
#define per(i, r, l) for (int i = r; i >= l; --i)
#define re(i, n) for (int i = 0; i < n; ++i)
#define pe(i, n) for (int i = n - 1; i >= 0; --i)
#define bg begin()
#define ed end()
#define alls(a) a.bg, a.ed
using i64 = long long;
using namespace std;
const int N = 1E6 + 5;
int n, a[N], L[N], R[N];
i64 Ans[N], d[N];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n; rep(i, 1, n) cin >> a[i];
stack<int> st;
rep(i, 1, n) {
while (!st.empty() && a[st.top()] > a[i]) R[st.top()] = i, st.pop();
st.push(i);
} while (!st.empty()) R[st.top()] = n + 1, st.pop();
per(i, n, 1) {
while (!st.empty() && a[st.top()] >= a[i]) L[st.top()] = i, st.pop();
st.push(i);
} while (!st.empty()) L[st.top()] = 0, st.pop();
auto m0 = [&](int l, int r, i64 v) {
if (l > r) return ;
d[l] += v; d[r + 1] -= v;
d[r + 1] -= (r - l + 1) * v;
d[r + 2] += (r - l + 1) * v;
} ;
auto m1 = [&](int l, int r, i64 v) {
if (l > r) return ;
d[l] += v; d[l + 1] -= v;
d[r + 1] -= v; d[r + 2] += v;
} ;
rep(i, 1, n) {
int P = i - L[i], Q = R[i] - i, mx = min(P, Q), r = P + Q - 1;
int nl = mx, nr = r - mx + 1;
m0(1, nl - 1, a[i]);
m0(nr + 1, r, -a[i]);
m1(nl, r, 1LL * mx * a[i]);
}
rep(i, 1, n) d[i] += d[i - 1];
rep(i, 1, n) d[i] += d[i - 1];
int q; cin >> q; while (q--) {
int k; cin >> k; int p = n - k + 1;
cout << setprecision(10) << fixed << 1.0 * d[k] / p << '\n';
}
}