题目连接
You are given two integers \(n\) and \(m\). For a sequence of \(n\) integers \(A=(a_1, a_2, \ldots, a_n)\), the parallel sums of \(A\) are the \(n-m+1\) integers \(s_1, s_2, \ldots, s_{n-m+1}\) defined by \(s_i = a_i + a_{i+1} + \ldots + a_{i+m-1}\) for each \(i\) (\(1 \leq i \leq n-m+1\)).
You are given the values of \(s_1, s_2, \ldots, s_{n-m+1}\). Your task is to answer \(q\) queries, described as follows. In the \(j\)-th query, you are given two integers \(l_j\) and \(r_j\), and you are asked to find the smallest possible value of \(\max(a_{l_j}, a_{l_j+1}, \ldots, a_{r_j})\) among all sequences \(A=(a_1, a_2, \ldots, a_n)\) of \(n\) integers (possibly negative) such that \(s_1, s_2, \ldots, s_{n-m+1}\) are the parallel sums of \(A\). Or determine if this value can be arbitrarily small.
观察到，\(a_{m + i} - a_i = s_{i + 1} - s_i\)，这告诉我们可以按照模 \(m\) 对所有的数字进行分类，重写方程组可以得到：
对模 \(m\) 余 \(d\) 的所有 \(\{a\}\)，我们重写为 \(b_{1}, \, \cdots, \, b_{k}\)，容易得知他们的差分是确定的，这启示我们如果想要找到一段区间的最小 \(\max\)，可以通过平衡分配 \(a_1, \, \cdots, \, a_m\) 来是的区间中最大的 \(b_i\) 最小，因此，任何长度小于 \(m\) 的区间都可以使得最大值无限小，反之，必定取遍 \(s_1\) 所覆盖的所有数字，我们不妨设 \(c_d\) 表示余数为 \(d\) 的元素在 \([l, \, r]\) 区间中的最大值与组成 \(s_1\) 的 \(a_d\) 的差，显然最大的元素可以取 \(\left\lceil\dfrac{s_1 + \sum_{i = 1}^{m}c_i}{m}\right\rceil\)，所以，我们的目标是求出最大的 \(c_i\)。
-
当 \(m \le \sqrt{n}\) 时，我们可以对每个余数类建立一个 ST 表，将 \([l, \, r]\) 的区间映射到每个余数类内取最大值。
-
当 \(m > \sqrt{n}\) 时，每个余数类里的元素个数较少，因此我们可以求出覆盖第 \(i\) 到第 \(j\) 个元素，前 \(m\) 个余数类的前缀和，询问一个区间 \([l, \, r]\) 时，将这个区间分为 \(3\) 个块，如下：
于是我们可以在 \(O(1)\) 的复杂度处理每个询问。
总时间复杂度 \(O((n + q)\sqrt{n})\)。
参考代码
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define i128 __int128
#define ld long double
#define pb push_back
#define PII pair<ll, ll>
#define PPI pair<ll, PII>
#define clr(f, n) memset(f, 0, sizeof(int) * (n))
#define cpy(f, g, n) memcpy(f, g, sizeof(int) * (n))
#define rev(f, n) reverse(f, f + (n))
const int N = 2e5 + 10, mod = 998244353, INF = 1e9;
const int B = 450;int n, m, q;
int lg2[N], len[N];
ll s[N], a[N], b[N];
vector<int> pos[N];
vector<vector<ll>> st[B], maxx[N];void build1() {lg2[0] = -1;for (int i = 1; i <= n; i ++ ) lg2[i] = lg2[i >> 1] + 1;for (int d = 1; d <= m; d ++ ) {for (int i = d; i <= n; i += m) pos[d].push_back(i);len[d] = pos[d].size();st[d].resize(lg2[len[d]] + 1, vector<ll>(len[d] + 1));for (int i = 0; i <= lg2[len[d]]; i ++ ) {for (int j = 1; j + (1 << i) - 1 <= len[d]; j ++ ) {if (!i) st[d][i][j] = b[pos[d][j - 1]];else st[d][i][j] = max(st[d][i - 1][j], st[d][i - 1][j + (1 << i - 1)]);}}}
}// x-th element is in d-group's y-th element
// x = d + y * m -> y = (x - d) / m
// L = ceil((x - d) / m), R = floor((x - d) / m)
ll query1(int d, int l, int r) {int L = (l - d + m - 1) / m + 1;int R = (r - d) / m + 1;int t = lg2[R - L + 1];return max(st[d][t][L], st[d][t][R - (1 << t) + 1]);
}void build2() {for (int d = 1; d <= m; d ++ ) {for (int i = d; i <= n; i += m) pos[d].push_back(i);len[d] = pos[d].size();maxx[d].resize(len[1] + 2, vector<ll>(len[1] + 2));for (int i = 1; i <= len[d]; i ++ ) {for (int j = i; j <= len[d]; j ++ ) {if (i == j) maxx[d][i][i] = b[pos[d][i - 1]];else maxx[d][i][j] = max(maxx[d][i][j - 1], b[pos[d][j - 1]]);}}}maxx[0].resize(len[1] + 2, vector<ll>(len[1] + 2));for (int d = 1; d <= m; d ++ ) {for (int i = 1; i <= len[d]; i ++ ) {for (int j = i; j <= len[d]; j ++ ) {maxx[d][i][j] += maxx[d - 1][i][j];}}}
}ll query2(int l, int r) {int fir = (l - 1) % m + 1, sec = (r - 1) % m + 1;int p = (l - 1) / m + 1, q = (r - 1) / m + 1;ll res = 0;res += maxx[min(fir - 1, sec)][p + 1][q];if (fir <= sec) res += maxx[sec][p][q] - maxx[fir - 1][p][q];else res += maxx[fir - 1][p + 1][q - 1] - maxx[sec][p + 1][q - 1];res += maxx[m][p][q - 1] - maxx[max(fir - 1, sec)][p][q - 1];return res;
}void solve() {cin >> n >> m;for (int i = 1; i <= n - m + 1; i ++ ) cin >> s[i];for (int i = 1; i <= n - m + 1; i ++ ) a[i] = s[i] - s[i - 1];for (int i = m; i <= n; i ++ ) b[i] = b[i - m] + a[i - m + 1];cin >> q;if (m < B) {build1();while (q -- ) {int l, r;cin >> l >> r;if (r - l + 1 < m) cout << "unbounded\n";else {ll sum = 0;for (int i = 1; i <= m; i ++ ) sum += query1(i, l, r);if (sum < 0) sum = sum / m;else sum = (sum + m - 1) / m;cout << sum << "\n";}}} else {build2();while (q -- ) {int l, r;cin >> l >> r;if (r - l + 1 < m) cout << "unbounded\n";else {ll sum = query2(l, r);if (sum < 0) sum = sum / m;else sum = (sum + m - 1) / m;cout << sum << "\n";}}}
}int main() {ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int T = 1;// cin >> T;while (T -- ) solve();return 0;
}