题解：P14638 [NOIP2025] 序列询问 / query（民间数据）

Kelin · 2025-12-02 00:06:21 · 题解

解法一：几何法

令 s_i=\sum_{j=1}^ia_i ；将区间 [l,r] 映射到二维平面中点 (l,r)，点权为区间和 s_r-s_{l-1} ，无效区间对应的坐标的点权为 -\infty。

那么原题可以转化为：对于所有的点 P(i,i) ，求下图所示梯形区域中的最大点权（GeoGebra 演示）。

这个梯形可以划分成一个平行四边形和一个等腰直角三角形。

取等腰直角三角形的三边中点，可以用 2 个平行四边形和一个正方形将其覆盖。

平行四边形

以 ▱ABCE 区域为例，可以将其划分成 L 条平行于横坐标的线段。

考虑其中一条线段 CE ，对应区间 [i-R+L,i+L-1],[i-R+L+1,i+L-1],\cdots,[i,i+L-1] ，其点权最大值为

所以 ▱ABCE 区域的最大点权为

这是一个非常典型的滑动窗口，可以通过单调队列求解；其中 val_{j+L-1} 可以通过 RMQ 在 O(n\log n)+O(1) 的时间内求出。

竖着的 ▱FDGH 同理。

正方形

设在 r=l 直线上方的正方形左下角为 (l_1,r_1) ，右上角为 (l_2,r_2) 。区间左右端点 l,r 没有相互约束，区域内的最大点权可以直接通过 \rm RMQ 求出：

特殊情况

特别需要注意的是，当 L,R 奇偶性不同时，(R-L)/2, (R+L)/2 向下取整后，点 F,G,H 变成 F',G',H' ，这对计算线段 F'H 和正方形 CF'G'H' 的最值不影响，但是对于 ▱EHFG 应当计算线段 F'G_1 而非线段 F'G' 的最值，也就是需要对 G 坐标中的 (R-L)/2 向上取整。

实现

写代码的时候最好把图放边上，不然会被这一堆的坐标绕晕，同时还要注意边界条件。

显然总时间复杂度为 O(n\log n+nq) 。但是！！！由于这个做法需要同时维护最大值和最小值的 RMQ ，还需要 3 个单调队列维护 3 个平行四边形的最值，常数巨大，需要手写单调队列才能通关全部测试点，用 std::deque 会 TLE！！！

::::success[Code]

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

constexpr int MAXN = 5e4 + 5;

struct MonoQueue {
  int idx[MAXN];
  ll val[MAXN];
  int h, t;

  inline void reset() {
    h = 1;
    t = 0;
  }

  inline void push(ll v, int pos) {
    while (h <= t && val[t] <= v)
      t--;
    t++;
    idx[t] = pos;
    val[t] = v;
  }

  inline void pop(int limit) {
    while (h <= t && idx[h] < limit)
      h++;
  }

  inline ll top() { return val[h]; }

  inline bool empty() { return h > t; }

} q1, q2, q3;

int main() {
#ifndef ONLINE_JUDGE
  cin.tie(0)->sync_with_stdio(0);
#endif
  int n;
  cin >> n;
  int m = __lg(n) + 1;
  vector s(n + 1, 0ll);
  vector f(m, vector(n + 1, INT64_MIN)), g(m, vector(n + 1, INT64_MAX));
  f[0][0] = g[0][0] = 0;
  for (int i = 1; i <= n; i++) {
    cin >> s[i];
    s[i] += s[i - 1];
    f[0][i] = g[0][i] = s[i];
  }
  for (int j = 1; j <= __lg(n); ++j) {
    int l = 1 << (j - 1);
    for (int i = 0; i + (1 << j) - 1 <= n; ++i) {
      f[j][i] = max(f[j - 1][i], f[j - 1][i + l]);
      g[j][i] = min(g[j - 1][i], g[j - 1][i + l]);
    }
  }
  auto qmax = [&](int l, int r) {
    int j = __lg(r - l + 1);
    return max(f[j][l], f[j][r - (1 << j) + 1]);
  };
  auto qmin = [&](int l, int r) {
    int j = __lg(r - l + 1);
    return min(g[j][l], g[j][r - (1 << j) + 1]);
  };
  int q;
  cin >> q;
  for (int l, r; q--;) {
    cin >> l >> r;
    uint64_t ans = 0;
    q1.reset(), q2.reset(), q3.reset();
    for (int i = 1; i <= n; ++i) {
      ll res = INT64_MIN;
      if (i + l - 1 <= n) {
        ll v1 = s[i + l - 1] - qmin(max(1, i - r + l) - 1, i - 1);
        q1.push(v1, i + l - 1);
      }
      if (i + (r + l) / 2 - 1 <= n) {
        ll v2 = s[i + (r + l) / 2 - 1] - qmin(max(1, i - (r - l + 1) / 2) - 1, i - 1);
        q2.push(v2, i + (r + l) / 2 - 1);
        ll v3 = qmax(i + (r + l) / 2 - 1, min(n, i + r - 1)) - s[i - 1];
        q3.push(v3, i);
      }
      q1.pop(i);
      q2.pop(i + l - 1);
      q3.pop(i - (r - l) / 2);
      if (!q1.empty()) res = max(res, q1.top());
      if (!q2.empty()) res = max(res, q2.top());
      if (!q3.empty()) res = max(res, q3.top());
      if (i + l - 1 <= n) {
        ll v4 = qmax(i + l - 1, min(n, i + (l + r) / 2 - 1)) -
                qmin(max(1, i - (r - l) / 2) - 1, i - 1);
        res = max(res, v4);
      }
      ans ^= uint64_t(res) * i;
    }
    cout << ans << '\n';
  }
  return 0;
}

::::

解法二

假设当前已经有了所有左端点小于等于 i-1 的最优的极好区间集合 S 。

如果 S 中的极好区间 A 的右端点比极好区间 B 小且 A 的区间和小于等于 B 的区间和，显然 A 是不优的，因为 B 的和更大且能覆盖更多位置。

对于 i ，会执行以下步骤：

1. 从 S 中移除右端点小于 i 的区间；
2. 加入以 i 为左端点的最优极好区间；
3. 移除不再最优的区间；
4. 从 S 中取出最大区间和作为 i 的答案。

这些步骤完美契合了滑动窗口的求解过程，可以使用单调队列维护 S，其中第 1,3,4 步的实现都非常简单。

考虑如何计算以 i 为左端点的最优极好区间，区间左端点 r 需要满足以下条件：

1. r\le n
2. i+L-1\le r\le i+R-1
3. 不存在 r-R+1\le k<i 满足 s_r-s_{k-1}\ge s_r-s_{i-1} ，即 r 不能有更优的左端点与之匹配
4. 上述条件会将 r 的取值限制在一个区间 [r_1,r_2] 中， r 还需要满足 r\ge r_{\rm best}=\argmax_{r_1\le j\le r_2}(s_j-s_{i-1})=\argmax_{r_1\le j\le r_2}s_j ；特别的，如果区间 [r_1,r_2] 非法，则 r_{\rm best}=\infty
5. 不存在 r'>r 满足 s_{r'}-s_{i-1}\ge s_r-s_{i-1} （这一步可以不管，单调队列会自动删除这些 r）

第 3 点中的 k 满足 s_{k-1}\le s_{i-1} ，可以利用单调栈求出最靠右的小于等于 s_i 的位置 {\rm leftLess}_i ，则 r>k-1+R={\rm leftLess}_{i-1} + R 。

故第 4 点中的 r_1=\max(i+L-1,\ {\rm leftLess}_{i-1} + 1 + R),\ r_2=\min(n,\ i+R-1) ，记 {\rm Right}_i=\min(n,\ i+R-1),\ {\rm Left}_i=\argmax_{r_1\le j\le r_2}s_j ，则 r 的取值范围为 [{\rm Left}_i,\ {\rm Right}_i] ，其中 {\rm Left}_i 可以利用 RMQ 在 O(n\log n)+O(1) 的时间内求出。

但是 \sum_i\max(0,\ {\rm Right}_i-{\rm Left}_i+1) 可能是 O(n^2) 级别的，需要优化。

进一步观察可以发现，当 r>\min({\rm Left}_{i+1},\ {\rm Left}_{i+2},\ ...,\ {\rm Left}_n)\overset{\rm def}{=}{\rm minSuffixLeft}_{i+1} 时，这样的 r 不会作为任何 j>i 的答案，因为根据 {\rm Left}_{j} 的定义， 有 s_{{\rm Left}_{j}}>s_r 。同时，这样的 r 也不能作为 i 的答案。

考虑对于 j>i 的位置：

如果 {\rm leftLess}_{i-1}\le{\rm leftLess}_{j-1}，那么 {\rm Left}_j 的 RMQ 区间是比 {\rm Left}_j 更靠右的，于是有 {\rm Left}_i\le {\rm Left}_j ，那么 r>{\rm Left}_j\ge{\rm Left}_i 显然不会是 i 的答案；

如果 {\rm leftLess}_{i-1}>{\rm leftLess}_{j-1} 且 {\rm Left}_i\le {\rm Left}_j ，同上；

如果 {\rm leftLess}_{i-1}>{\rm leftLess}_{j-1} 且 {\rm Left}_i>{\rm Left}_j ，此时 {\rm Left}_j 的 RMQ 区间是包含 {\rm Left}_i 的 RMQ 区间的，那么有 s_{{\rm Left}_j}>s_{{\rm Left}_i} ，又因为 i+L-1<j+L-1\le {\rm Left}_j<{\rm Left}_i\le i+R-1，所以 [i, {\rm Left}_i] 比 [i, {\rm Left}_j] 更劣，所以当 r\ge {\rm Left}_i>{\rm Left}_j 时，同样不会作为 i 的答案。 \square

所以可以进一步限制 {\rm Right}_i=\min(n,\ i+R-1,\ {\rm minSuffixLeft}_{i+1}) ，故此时

暴力将区间 [i,r],r\in[{\rm Left}_i,\ {\rm Right}_i] 添加到 S 即可。

实现

时间复杂度 O(n\log n+nq) ，常数极小。

::::success[Code]

#include <bits/stdc++.h>

using namespace std;
using ll = int64_t;

int main() {
#ifndef ONLINE_JUDGE
  cin.tie(0)->sync_with_stdio(0);
#endif
  int n;
  cin >> n;
  int m = __lg(n) + 1;
  vector s(n + 1, 0ll);
  vector f(m, vector(n + 1, 0));
  for (int i = 1; i <= n; i++) {
    cin >> s[i];
    s[i] += s[i - 1];
    f[0][i] = i;
  }
  auto argmax = [&](int x, int y) {
    return (s[x] == s[y] ? x > y : s[x] > s[y]) ? x : y;
  };
  for (int j = 1; j <= __lg(n); ++j) {
    int l = 1 << (j - 1);
    for (int i = 0; i + (1 << j) - 1 <= n; ++i) {
      f[j][i] = argmax(f[j - 1][i], f[j - 1][i + l]);
    }
  }
  auto qmax = [&](int l, int r) {
    if (l > r)
      return n + 1;
    int j = __lg(r - l + 1);
    return argmax(f[j][l], f[j][r - (1 << j) + 1]);
  };
  stack<int> stk;
  vector<int> leftLess(n + 1), L(n + 1), R(n + 1);
  for (int i = 0; i <= n; ++i) {
    while (!stk.empty() && s[stk.top()] > s[i])
      stk.pop();
    leftLess[i] = stk.empty() ? INT_MIN : stk.top();
    stk.push(i);
  }
  int q;
  cin >> q;
  for (int l, r; q--;) {
    cin >> l >> r;
    uint64_t ans = 0;
    for (int i = n, minL = n; i; --i) {
      R[i] = min(minL, i + r - 1);
      L[i] = qmax(max(leftLess[i - 1] + 1 + r, i + l - 1), min(n, i + r - 1));
      minL = min(minL, L[i]);
    }
    deque<pair<int64_t, int>> Q;
    for (int i = 1; i <= n; ++i) {
      while (!Q.empty() && Q.front().second < i)
        Q.pop_front();
      for (int j = L[i]; j <= R[i]; ++j) {
        auto val = s[j] - s[i - 1];
        while (!Q.empty() && val > Q.back().first)
          Q.pop_back();
        Q.emplace_back(val, j);
      }
      ans ^= uint64_t(Q.front().first) * i;
    }
    cout << ans << '\n';
  }
  return 0;
}

::::

冷静分析可以发现，这题本质上其实并不难，可能是大家在考场上被吓到了吧，估计过段时间就会回归到紫题，先 \rm mark 一下。