P17533 [JAG 2026 Summer Camp #1] Longest Symmetry

· · 题解

[JAG 2026 Summer Camp #1] Longest Symmetry

安利一下我的博客！

思路

考虑对于每个 i 求出一个最小的 c_i 满足区间 [c_i,2\times i-c_i] 为“对称房屋区间”，这里可以用马拉车或者二分加哈希。

对于一个询问 [l,r]，答案为 2 \times \max_{i\in[l,r]} ( \min(X_i-X_{c_i},\min(X_i-X_l ,X_r-X_i) )。二分找到一个最大的 mid 满足 X_{mid}-X_l\le X_r-X_{mid}。这样一来，对于 i\in[l,mid]，\min(X_i-X_l ,X_r-X_i) 取 X_i-X_l。对于 i\in[mid+1,r]，\min(X_i-X_l ,X_r-X_i) 取 X_r-X_i。两种情况分别考虑一下即可，这里以 i\in[l,mid] 的情况为例，我们根据 c_i 的大小分类讨论：

  1. 对于所有 l\le i\le mid 且 c_i\le l，我们希望求出 X_i-X_l 的最大值，即 i 的最大值。这是一个三维偏序，不过注意到可以将 i\ge l 的条件删去，因为如果 i<l，那么 X_i-X_l 一定小于 0，不会影响答案。
  2. 对于所有 l\le i\le mid 且 c_i\ge l，我们希望求出 X_i-X_{c_i} 的最大值。这同样是一个三维偏序，但是因为 i\ge c_i，所以我们可以将 i\ge l 的限制删掉，变为二维偏序。

离线后进行二维偏序即可，注意“对称房屋区间”的中心可能是 X_i 与 X_{i+1} 的中点，需要特殊考虑一下。

代码

时间复杂度 O(n\log n)。

#include<bits/stdc++.h>
using namespace std;
const int N=4e5+50;
int n,q,a[N];
long long ans[N];
vector<pair<int,int> > qu[N],quu[N];
int c[N],cc[N],b[N],cnt=0,ct[N],p[N];
void solve(int x){while(b[x-p[x]-1]==b[x+p[x]+1]) p[x]++;}
void manacher()
{
    p[1]=0;
    int mm=1;
    for(int i=2;i<=cnt;i++)
    {
        if(mm+p[mm]-1>=i) p[i]=min(mm+p[mm]-1-i,p[mm*2-i]);
        solve(i);
        if(i+p[i]-1>=mm+p[mm]-1) mm=i;
    }
    for(int i=1;i<=cnt;i++)
        if(ct[i]) cc[ct[i]]=ct[i]-p[i]/2,c[ct[i]]=ct[i]-p[i-1]/2,c[ct[i]+1]=ct[i]+1-p[i+1]/2;
}
struct tree
{
    long long tree[N];
    int lowbit(int x) {return x&(-x);}  
    void clear(){ memset(tree,128,sizeof(tree));}
    void update(int x,long long y) {for(int i=x;i<=n;i+=lowbit(i)) tree[i]=max(tree[i],y);}
    long long query(int x)
    {
        long long res=tree[0];
        for(int i=x;i;i-=lowbit(i)) res=max(res,tree[i]);
        return res;
    }
}tr,trr;
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    b[++cnt]=-2,b[++cnt]=-1;
    for(int i=1;i<n;i++) b[++cnt]=a[i+1]-a[i],ct[cnt]=i,b[++cnt]=-1;
    b[++cnt]=-3,manacher();
    cin>>q;
    for(int i=1;i<=q;i++)
    {
        int l,r;
        cin>>l>>r;
        int ll=l,rr=r,res=0;
        while(ll<=rr)
        {
            int mid=(ll+rr)>>1;
            if(a[mid]-a[l]<=a[r]-a[mid]) res=mid,ll=mid+1;
            else rr=mid-1;
        }
        qu[res].push_back({l,i});
        if(res!=r) ans[i]=a[res+1]-a[res]+2*min(a[res]-a[cc[res]],min(a[res]-a[l],a[r]-a[res+1]));
        if(res+1<=r) quu[res+1].push_back({r,i});
    }
    tr.clear(),trr.clear();
    for(int i=1;i<=n;i++)
    {
        tr.update(c[i],a[i]*2),trr.update(n-c[i]+1,(a[i]-a[c[i]])*2);
        if(i!=1) tr.update(cc[i-1],a[i-1]+a[i]),trr.update(n-cc[i-1]+1,(a[i-1]-a[cc[i-1]])*2+a[i]-a[i-1]);
        for(int j=0;j<qu[i].size();j++) ans[qu[i][j].second]=max(ans[qu[i][j].second],max(trr.query(n-qu[i][j].first+1),tr.query(qu[i][j].first)-a[qu[i][j].first]*2)); 
    }   
    tr.clear(),trr.clear();
    for(int i=1;i<=n;i++) c[i]=i-c[i]+i,cc[i]=i+1+i-cc[i];
    for(int i=n;i>=1;i--)
    {
        tr.update(n-c[i]+1,-a[i]*2),trr.update(c[i],(a[c[i]]-a[i])*2);
        if(i!=n) tr.update(n-cc[i]+1,-(a[i+1]+a[i])),trr.update(cc[i],(a[cc[i]]-a[i+1])*2+a[i+1]-a[i]);
        for(int j=0;j<quu[i].size();j++) ans[quu[i][j].second]=max(ans[quu[i][j].second],max(tr.query(n-quu[i][j].first+1)+a[quu[i][j].first]*2,trr.query(quu[i][j].first)));
    }
    for(int i=1;i<=q;i++) cout<<ans[i]<<"\n";
    return 0;
}