题解：P14638 [NOIP2025] 序列询问 / query

· · 题解

[NOIP2025] 序列询问 / query

题意简述

每次询问 L,R，对于每个 i 求：

\max_{0\le l<i\le r\le n,L\le r-l\le R} s_r-s_l

其中 s 为前缀和数组，这里为了后面计算方便用 (l,r] 来描述题意。

正文

设点 (x,y) 的权值为 s_y-s_x。

先看 L\le r-l\le R，把 (l,r) 搬到坐标系上就是这样：

加上 l<i,r\ge i 后就是这样：

即要对于每个 i 求一个“梯形”内的最大权值，将其拆成两个部分：

右侧（平行四边形）

因为初始两条线（图一）不会变，因此可以对于每个 k 求出 x=k 时的最大权值 w_k，这用 ST 表预处理可以 O(1) 做。i 往后挪一格，原本平行四边形最左边的 w 会被删除，最右边加入 w_i。这直接单调队列维护滑动窗口即可。

左侧（三角形）

如图，将三角形沿中点切割成一个正方形（绿）和两个三角形。

因为只是求 \max，所以可以直接计算两个平行四边形（黄或蓝 + 深绿，因为沿中点切割可以证明是平行四边形）和正方形的最大权值的最大值。平行四边形可以用上面说的单调队列求。正方形其实就是横坐标与纵坐标可以随便组合，求 \max s_y-\min s_x 即可。

预处理 ST 表时间复杂度 O(n\log n)，每次询问 O(n)，总时间复杂度 O(n\log n+nq)。

细节

AC Code

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e5 + 5 , M = 15;
const ll inf = 2e18 + 7;
struct Deque
{
    int a[N] , head , tail;
    inline void init ()
    {head = 1 , tail = 0;}
    inline void push (int x)
    {a[++ tail] = x;}
    inline void pop_front () {head ++;}
    inline void pop_back () {tail --;}
    inline int front () {return a[head];}
    inline int back () {return a[tail];}
    inline bool empty () {return head == tail + 1;}
} qu;
int n , q;
ll a[N] , w[N] , wl[N] , wr[N] , ans[N] , f[M + 1][N] , g[M + 1][N];
int lg[N];
inline void init ()
{
    lg[0] = -1;
    for (int i = 1;i <= n;i ++) lg[i] = lg[i >> 1] + 1;
    for (int i = 0;i <= n;i ++) f[0][i] = -a[i] , g[0][i] = a[i];
    for (int j = 1;j <= M;j ++)
        for (int i = 0;i + (1 << j) - 1 <= n;i ++)
            f[j][i] = max (f[j - 1][i] , f[j - 1][i + (1 << j - 1)]),
            g[j][i] = max (g[j - 1][i] , g[j - 1][i + (1 << j - 1)]);
}
inline ll Maxf (int l , int r)
{
    if (r < l) return -inf;
    l = max (l , 0);
    int Log = lg[r - l + 1];
    return max (f[Log][l] , f[Log][r - (1 << Log) + 1]);
}
inline ll Maxg (int l , int r)
{
    if (r < l) return -inf;
    r = min (r , n);
    int Log = lg[r - l + 1];
    return max (g[Log][l] , g[Log][r - (1 << Log) + 1]);
}
inline void solve (int L , int R)
{
    for (register int i = 0;i <= n;++ i)
        w[i] = wl[i] = wr[i] = -inf;
    int m = n - L;
    for (register int i = 0;i <= m;++ i)
        w[i] = Maxg (i + L , i + R) - a[i];
    qu.init ();
    for (register int i = 1;i <= n;++ i)
    {
        while (!qu.empty () && qu.front () < i - L) qu.pop_front ();
        while (!qu.empty () && w[qu.back ()] <= w[i - 1]) qu.pop_back ();
        qu.push (i - 1);
        ans[i] = w[qu.front ()];
    }
    int sz = R - L + 1;
    if (sz & 1) sz ++;
    sz >>= 1;
    m = n - L - sz;
    for (register int i = 0;i <= m;++ i)
        wl[i] = Maxg (i + L + sz , i + R) - a[i];
    qu.init ();
    for (register int i = L;i <= n;++ i)
    {
        int p = i - L - sz , q = i - L;
        while (!qu.empty () && qu.front () <= p) qu.pop_front ();
        while (!qu.empty () && wl[qu.back ()] <= wl[q]) qu.pop_back ();
        qu.push (q);
        if (!qu.empty ()) ans[i] = max (ans[i] , wl[qu.front ()]);
    }
    for (register int i = L + sz;i <= n;++ i)
        wr[i] = a[i] + Maxf (i - R , i - L - sz);
    qu.init ();
    for (register int i = L + 1;i <= n;++ i)
    {
        int q = i + sz - 1;
        while (!qu.empty () && qu.front () < i) qu.pop_front ();
        if (n >= q)
        {
            while (!qu.empty () && wr[qu.back ()] <= wr[q]) qu.pop_back ();
            qu.push (q);
        }
        if (!qu.empty ()) ans[i] = max (ans[i] , wr[qu.front ()]);
    }
    for (register int i = L;i <= n;++ i)
        ans[i] = max (Maxg (i , i + sz - 1) + Maxf (i - L - sz + 1 , i - L) , ans[i]);
    unsigned ll ANS = 0;
    for (register int i = 1;i <= n;++ i)
        ANS ^= ans[i] * i;
    cout << ANS << '\n';
}

signed main ()
{
    ios::sync_with_stdio (0);
    cin.tie (0) , cout.tie (0);
    cin >> n;
    for (register int i = 1;i <= n;i ++) cin >> a[i] , a[i] += a[i - 1];
    init ();
    cin >> q;
    while (q --)
    {
        int L , R;
        cin >> L >> R;
        solve (L , R);
    }
    return 0;
}