题解：P17533 [JAG 2026 Summer Camp #1] Longest Symmetry

UnionRE · 2026-11-11 09:55:54 · 题解

修改了一些笔误。

神秘模拟赛 T2。

还是有较大部分思路来源于 @Bestart。

为区分，将题目的输入区间设为 [x,y]。

先简化一下题意：

差分得到正整数数组 \{d\} 满足 \bm{d_i=x_{i+1}-x_i}，定义一个区间的权值为 sum(l,r)=\displaystyle\sum _{i=l}^rd_i，每次给定区间 [x,y-1]，查询满足 d[L,R] 是回文串子区间的权值最大值。

下面说明，l=2x-1,r=2(y-1)-1=2y-3。

首先用麻辣车统计一下，以 i 为中心的左右最长回文半径 L_i,R_i。（方便起见，我们还是先插入分隔符 d_i=0）

我们以下内容均考虑 i 为回文中心。下面再设 m 表示 [l,r] 插入分隔符后的中间位置。

然后进行分类讨论：

Case 1：[L_i,R_i]\subseteq [l,r]

条件：\begin{cases}l\le L_i\\R_i\le r\end{cases}。

显然长度就是 sum(L_i,R_i)，被完全覆盖。

直接离线处理一下。

Case 2：l\le i\le m

条件：\begin{cases}l\le i\le m\\L_i\le l\end{cases}。

显然这个东西只会保留 sum(l,2i-l)。那我们找满足条件最大的 i。

Case 3：m<i\le r

条件：\begin{cases}m<i\le r\\r \le R_i\end{cases}。

显然只会保留 sum(2i-r,r)。

计算最小的满足条件的 i。

最后就是三个的最大值。

#include<bits/stdc++.h>
using namespace std;
#define fir(i, l, r) for(int i = l; i <= r; i++)
#define fpr(i, r, l) for(int i = r; i >= l; i--)
#define full(v) v.begin(), v.end()
#define endl '\n'
const int maxn = 4e5 + 10;
int x[maxn], d[maxn], p[maxn], L[maxn], R[maxn], _r, _mid, pre[maxn];
template <int (*merge) (int, int), int NO_VAL>
struct Tree{
    struct node{
        int l, r, inf;
    }t[maxn * 4];
    #define ls id << 1
    #define rs id << 1 | 1
    void up(int id){t[id].inf = merge(t[ls].inf, t[rs].inf);}
    void build(int id, int l, int r){
        t[id] = {l, r, NO_VAL};
        if(l == r) return ;
        int mid = (l + r) >> 1;
        build(ls, l, mid);
        build(rs, mid + 1, r);
        up(id);
    }
    void insert(int id, int x, int val){
        if(t[id].l > x || x > t[id].r) return ;
        if(t[id].l == t[id].r) return t[id].inf = merge(t[id].inf, val), void();
        insert(ls, x, val), insert(rs, x, val);
        up(id);
    }
    int query(int id, int l, int r){
        if(t[id].l > r || l > t[id].r) return NO_VAL;
        if(l <= t[id].l && t[id].r <= r) return t[id].inf;
        return merge(query(ls, l, r), query(rs, l, r)); 
    }
};
int ans[3][maxn], qoq = 0;
array <int, 4> q[3][maxn];
basic_string <array <int, 2>> vecl[maxn], vecr[maxn];
array <int, 2> qq[maxn];
#define sum(x, y) (pre[y] - pre[x - 1])
int Min(int x, int y){return min(x, y);}
int Max(int x, int y){return max(x, y);}
signed main(){
    ios :: sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    freopen("symmetry.in", "r", stdin);
    freopen("symmetry.out", "w", stdout);
    int n, m = 0;
    cin >> n;
    fir(i, 1, n) cin >> x[i];
    fir(i, 1, n - 1) d[++m] = x[i + 1] - x[i], d[++m] = 0; 
    m--;
    fir(i, 1, m) pre[i] = pre[i - 1] + d[i];
    Tree <Max, INT_MIN> T1, T2;
    Tree <Min, INT_MAX> T3;
    d[0] = -1, d[m + 1] = -2;
    fir(i, 1, m){
        if(_r > i){
            if(p[_mid * 2 - i] + i - 1 > _r) p[i] = _r - i + 1;
            else p[i] = p[_mid * 2 - i];
        }
        else p[i] = 1;
        while(d[i - p[i]] == d[i + p[i]]) p[i]++;
        if(p[i] + i - 1 > _r) _r = p[i] + i - 1, _mid = i;
        L[i] = i - p[i] + 1, R[i] = i + p[i] - 1;
        vecl[L[i]] += {R[i], i};
        vecr[R[i]] += {L[i], i};
    }
    T1.build(1, 1, m);
    T2.build(1, 1, m);
    T3.build(1, 1, m);
    int Q;
    cin >> Q;
    fir(i, 1, Q){
        int x, y, l, r, mid;
        cin >> x >> y;
        l = 2 * x - 1, r = 2 * y - 3, mid = l + r >> 1;
        qq[i] = {l, r};
        q[0][i] = {r, l, i};//q[0] 表示 R <= [1] 中 >= [0] 的最大 i
        q[1][i] = {l, mid, i};
        q[2][i] = {r, mid, i};
    }
    sort(q[0] + 1, q[0] + Q + 1);
    sort(q[1] + 1, q[1] + Q + 1);
    sort(q[2] + 1, q[2] + Q + 1);
    reverse(q[2] + 1, q[2] + Q + 1);
    int last = 1;
    fir(i, 1, Q){
        int _r = q[0][i][0];
        fir(j, last, _r) for(auto [l, id] : vecr[j]) T1.insert(1, l, sum(L[id], R[id]));
        last = _r + 1;
        ans[0][q[0][i][2]] = T1.query(1, q[0][i][1], m);
    }
    last = 1;
    fir(i, 1, Q){
        int _l = q[1][i][0];
        fir(j, last, _l) for(auto [r, id] : vecl[j]) T2.insert(1, id, id);
        last = _l + 1;
        ans[1][q[1][i][2]] = T2.query(1, _l, q[1][i][1]);
    }
    last = m;
    fir(i, 1, Q){
        int _r = q[2][i][0];
        fpr(j, last, _r) for(auto [l, id] : vecr[j]) T3.insert(1, id, id);
        last = _r - 1;
        ans[2][q[2][i][2]] = T3.query(1, q[2][i][1] + 1, _r);
    }
    fir(i, 1, Q){
        auto [l, r] = qq[i];
        int I1 = ans[1][i], I2 = ans[2][i];
        int ans_ = ans[0][i];
        if(I1 != INT_MIN) ans_ = max(ans_, sum(l, 2 * I1 - l));
        if(I2 != INT_MAX) ans_ = max(ans_, sum(2 * I2 - r, r));
        cout << ans_ << endl;
    }
    return 0;
}
/*
だから
だから妄想感傷代償連盟
愛を懐いて理想を号んだ
行き場のない愚者のメロディー
再挑戦•転生•テレポーテーション
何回だって　重ねて逝くんだ
終わりなき愛の随に　さあ

*/