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

wsy_I · 2026-11-10 13:39:14 · 题解

代码比鸭棋长，大战一个晚上 + 半个中午之后终于补出来了。所以为啥有人把这个大数据结构 + 大分类讨论放 NOIP 模拟赛 T2，这真比 sale 难 INF 倍吧。

首先一步很显然的转化是，假如一个区间是“回文区间”，那么这个区间对应的差分数组 d_i=x_{i+1}-x_i 回文。由于一个回文区间左右边各去掉一个数也是回文的，所以我们考虑只保留极大的回文区间，这样做一遍马拉车或者二分哈希就可以求出来。

接着是分类讨论查询和回文区间的相交情况。设查询区间 [l,r]，回文区间 [L,R]，那么可以做如下分类讨论。

第一种情况，区间不交，即 L>r\lor l>R。这种显然没有贡献，可以去掉。

第二种情况，[L,R]\subseteq[l,r]。此时贡献就是区间长度 x_R-x_L，需要满足的条件就是 l\leq L\land R\leq r，是一个离线二维数点。

第三种情况，区间左交。也就是 L<l\land l\leq R<r。此时由于区间回文，贡献可以写作 2(x_{\frac{L+R}{2}}-x_l)。这里 x 单调递增，所以我们对于 l 做二维偏序，维护一个 \max \frac{L+R}{2} 即可。第四种情况也就是区间右交，和区间左交相似，维护 \min \frac{L+R}{2} 即可。

第五种情况，[l,r]\subseteq[L,R]。记 m=\frac{L+R}{2}，那么贡献是 2\min(x_m-x_l,x_r-x_m)，由于这里带一个 \min 看起来十分不好维护。于是分类讨论 \min 的情况，分界点显然是 \frac{l+r}{2}。于是可以维护 l\leq L\land l\leq m\leq\frac{l+r}{2} 的二维偏序，查询 \max m；对于另一种情况类似。这么做可能会让第三种和第四种情况的情况被再贡献一遍，但是 \max 有幂等律，所以重复贡献没有问题，直接做二维偏序是对的。

由于三、四、五这三种情况需要记 l\leq R<r 这种状物，\min 操作又难以差分掉，所以维护二维偏序的时候要用线段树，树状数组和 CDQ 分治貌似都不太行。

具体实现的时候，对于 l 递增和 l 递减的时候分别做一遍扫描线，使用五个线段树维护每一种情况的单点修改和区间 \min 就可以了。时间复杂度 O(n\log n)，空间复杂度 O(n)。我写的双哈希求回文串，可能代码会略微长一点。

::::success[code]

#include <bits/stdc++.h> 
#define rep(i, l, r) for(int i = (l); i <= (r); i ++ )
#define per(i, l, r) for(int i = (l); i >= (r); i -- )
#define frein(s) freopen(s, "r", stdin)
#define freout(s) freopen(s, "w", stdout)
#define endl '\n'
using namespace std;

const int N = 4e5 + 5;
const int M = 998244353, B = 19491001;
const int INF = 0x3f3f3f3f;
using ull = unsigned long long;
int n, x[N], d[N], tot, ph1[N], sh1[N], pB1[N], ltot, qtot, q, ans[N];
ull ph2[N], sh2[N], pB2[N];
struct Line { int l, r, w, type; } li[N * 5];
struct Query { int l, r, id, type; } qry[N * 5];
inline int& chkmax(int &x, int v) { return x = x > v ? x : v; }

struct SEG {
  #define lc(x) ((x) << 1)
  #define rc(x) ((x) << 1 | 1)
    int t[N << 3];
  void init() { rep(i, 1, n << 3) t[i] = -INF; }
  void pushup(int x) { t[x] = max(t[lc(x)], t[rc(x)]); }

  void update(int l, int r, int x, int pos, int v) {
    if(l == r) {
      chkmax(t[x], v);
      return;
    }
    int mid = l + r >> 1;
    if(pos <= mid) update(l, l + r >> 1, lc(x), pos, v);
    else update((l + r >> 1) + 1, r, rc(x), pos, v);
    pushup(x);
  }

  int query(int l, int r, int x, int ql, int qr) {
    if(ql <= l && r <= qr) return t[x];
    if(l > qr || ql > r) return -INF;
    return max(query(l, l + r >> 1, lc(x), ql, qr),
      query((l + r >> 1) + 1, r, rc(x), ql, qr));
  }
} T[6];

pair<int, ull> getHash(int h1[], ull h2[], int B[], ull B2[], int l, int r) {
    return make_pair(
        (h1[r] - 1ll * h1[l - 1] * B[r - l + 1] % M + M) % M,
        h2[r] - h2[l - 1] * B2[r - l + 1]
    );
}

bool check(int l, int r) {
    return getHash(ph1, ph2, pB1, pB2, l, r) ==
        getHash(sh1, sh2, pB1, pB2, tot - r, tot - l);
}

void Manacher() {
    pB1[0] = pB2[0] = 1;
    rep(i, 1, tot - 1) {
        ph1[i] = (1ll * ph1[i - 1] * B + d[i]) % M;
        ph2[i] = ph2[i - 1] * B + d[i];
        pB1[i] = 1ll * pB1[i - 1] * B % M;
        pB2[i] = pB2[i - 1] * B;
    }
    reverse(d + 1, d + tot);
    rep(i, 1, tot - 1) {
        sh1[i] = (1ll * sh1[i - 1] * B + d[i]) % M;
        sh2[i] = sh2[i - 1] * B + d[i];
    }
    rep(i, 1, tot - 1) {
    int l = 0, r = min(tot - 1 - i, i - 1), mid, ans = 0;
    while(l <= r) {
      mid = l + r >> 1;
      if(check(i - mid, i + mid)) {
        l = mid + 1;
        ans = mid;
      } else {
        r = mid - 1;
      }
    }
    l = i - ans, r = i + ans;
    li[ ++ ltot] = {l, r, x[r] - x[l], 1};
    li[ ++ ltot] = {l, r, i, 2};
    li[ ++ ltot] = {l, r, i, 3};
    li[ ++ ltot] = {l, i, i, 4};
    li[ ++ ltot] = {i, r, i, 5};
  }
}

void solve() {
  rep(i, 1, 5) T[i].init();
  sort(li + 1, li + ltot + 1, [&](auto a, auto b) { return a.l < b.l; });
  sort(qry + 1, qry + qtot + 1, [&](auto a, auto b) { return a.l < b.l; });
  int ptr2 = 0;
  rep(i, 1, qtot) {
    while (ptr2 + 1 <= ltot && qry[i].l >= li[ptr2 + 1].l) {
      ptr2++;
      if (li[ptr2].type == 2 || li[ptr2].type == 4)
        T[li[ptr2].type].update(1, n << 1, 1, li[ptr2].r, li[ptr2].w);
    }
    if (qry[i].type == 2) {
      int c = T[2].query(1, n << 1, 1, qry[i].l, qry[i].r);
      if (c != -INF)
        chkmax(ans[qry[i].id], x[2 * c - qry[i].l] - x[qry[i].l]);
    } else if (qry[i].type == 4) {
      int c = T[4].query(1, n << 1, 1, qry[i].l, qry[i].r);
      if (c != -INF)
        chkmax(ans[qry[i].id], x[2 * c - qry[i].l] - x[qry[i].l]);
    }
  }
  rep(i, 1, 5) T[i].init();
  sort(qry + 1, qry + qtot + 1, [&](auto a, auto b) { return a.l > b.l; });
  int ptr1 = ltot + 1;
  rep(i, 1, qtot) {
    while (ptr1 - 1 >= 1 && li[ptr1 - 1].l >= qry[i].l) {
      ptr1--;
      if (li[ptr1].type == 1)
        T[1].update(1, n << 1, 1, li[ptr1].r, li[ptr1].w);
      else if (li[ptr1].type == 3 || li[ptr1].type == 5)
        T[li[ptr1].type].update(1, n << 1, 1, li[ptr1].r, -li[ptr1].w);
    }
    if (qry[i].type == 1) {
      chkmax(ans[qry[i].id], T[1].query(1, n << 1, 1, qry[i].l, qry[i].r));
    } else if (qry[i].type == 3) {
      int v = T[3].query(1, n << 1, 1, qry[i].r, n << 1);
      if (v != -INF) {
        int c = -v;
        chkmax(ans[qry[i].id], x[qry[i].r] - x[2 * c - qry[i].r]);
      }
    } else if (qry[i].type == 5) {
      int v = T[5].query(1, n << 1, 1, qry[i].r, n << 1);
      if (v != -INF) {
        int c = -v;
        chkmax(ans[qry[i].id], x[qry[i].r] - x[2 * c - qry[i].r]);
      }
    }
  }
}

int main() {
    ios :: sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> n;
    rep(i, 1, n) {
        int p;
        cin >> p;
        x[ ++ tot] = p;
        x[ ++ tot] = p;
    }
    rep(i, 1, tot - 1) d[i] = x[i + 1] - x[i];
    Manacher();
  cin >> q;
  rep(i, 1, q) {
    int l, r;
    cin >> l >> r;
    l = (l << 1) - 1, r = (r << 1) - 1;
    int mid = l + r >> 1;
    qry[ ++ qtot] = {l, r, i, 1};
    qry[ ++ qtot] = {l, r, i, 2};
    qry[ ++ qtot] = {l, r, i, 3};
    qry[ ++ qtot] = {l, mid, i, 4};
    qry[ ++ qtot] = {mid, r, i, 5};
  }
  solve();
  rep(i, 1, q) cout << ans[i] << endl;
    return 0;
}

::::