P14638 [NOIP2025] 序列询问 题解

· · 题解

分享一下赛时做法。

首先把区间 [l,r] 映射到直角坐标系上的点 (l,r)，注意到求出一个矩形的最大值是不难的，而题目相当于要求这样一个梯形的最大值：

这个梯形似乎没有什么很好的性质。但我们注意到对于一次询问的所有 i，两条倾斜直线都是不变的。也就是说，如果基于这两条直线构造平行四边形，就相当于一个 RMQ 问题，可以使用单调队列求解，例如：

如果 2L\ge R，使用两个平行四边形即可覆盖梯形内的所有整点。对于一般情况，左下角的三角形可以使用如下方式覆盖：

然后这道题就做完了。可能需要卡常，RMQ 全部使用单调队列维护。

UPD: :::info[赛时代码]


#include <bits/stdc++.h>
using namespace std;
int n,q,l,r,k,st[50010],ll,rr,u;
long long a[50010],mn[50010],mx[50010],v[50010],x[50010];
const long long lim=1e18;
unsigned long long ans;
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>n;
    for (int i=1;i<=n;++i) cin>>a[i],a[i]+=a[i-1];
    cin>>q;
    for (int _=1;_<=q;++_) {
        cin>>l>>r;
        k=r-l>>1;
        ll=1;
        rr=0;
        for (int i=n;~i;--i) {
            while (ll<=rr&&st[ll]>i+k) ++ll;
            while (ll<=rr&&a[st[rr]]<=a[i]) --rr;
            st[++rr]=i;
            mx[i]=a[st[ll]];
        }
        ll=1;
        rr=0;
        for (int i=0;i<=n;++i) {
            while (ll<=rr&&st[ll]<i-k) ++ll;
            while (ll<=rr&&a[st[rr]]>=a[i]) --rr;
            st[++rr]=i;
            mn[i]=a[st[ll]];
        }
        for (int i=1;i<l;++i) x[i]=-lim;
        for (int i=l;i<=n;++i) x[i]=mx[i]-mn[i-l];
        for (int i=1;i<=n-r+k+1;++i) v[i]=max(mx[i+l-1],mx[i+r-k-1])-a[i-1];
        for (int i=n-r+k+2;i<=n-l+1;++i) v[i]=mx[i+l-1]-a[i-1];
        for (int i=n-l+2;i<=n;++i) v[i]=-lim;
        ll=1;
        rr=0;
        for (int i=1;i<=n;++i) {
            while (ll<=rr&&st[ll]<=i-l) ++ll;
            while (ll<=rr&&v[st[rr]]<=v[i]) --rr;
            st[++rr]=i;
            x[i]=max(x[i],v[st[ll]]);
        }
        if (r-l==2*k) for (int i=l;i<=n-k;++i) v[i]=max(mx[i+k]-a[i-l],a[i+k]-mn[i-l]);
        else for (int i=l;i<=n-k;++i) v[i]=max(max(mx[i+k],a[min(n,i+r-l)])-a[i-l],a[i+k]-min(mn[i-l],a[max(0,i-r+k)]));
        for (int i=n-k+1;i<=n;++i) v[i]=-lim;
        ll=1;
        rr=0;
        for (int i=l;i<=n;++i) {
            while (ll<=rr&&st[ll]<i-k) ++ll;
            while (ll<=rr&&v[st[rr]]<=v[i]) --rr;
            st[++rr]=i;
            x[i]=max(x[i],v[st[ll]]);
        }
        ans=0;
        for (int i=1;i<=n;++i) ans^=(unsigned long long)x[i]*i;
        cout<<ans<<'\n';
    }
}