P14638 [NOIP2025] 序列询问 / query

· · 题解

场上死磕 T2，没细想。

思路：

考虑单次询问怎么做。

信息很多浪费，于是考虑分治，calc(l, r) 表示已经算了左右端点都在 [l, r] 范围的区间后对 ans 的贡献。

然后考虑 i \in [l, mid]，需要计算右端点在 [mid + 1, r] 内的区间的答案 f_i，然后你发现 f_{i - 1} 计算的区间一定包含了 i，于是只需要增量算左端点是 i 是区间，即：

f_i = \max(f_{i - 1}, \max\limits_{j = \max(i + L - 1, mid + 1)}^{\min(i + R - 1, r)}(s_j - s_{i - 1}))

对于 i \in [mid + 1, r]，计算左端点在 [l, mid] 的区间的答案，处理是类似的。

这里查询是区间 \max/\min 形式的，提前用 ST 表预处理。

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

考虑拓展，发现当我们的贡献区间一定跨过一个中点 mid 时是线性的；于是可以倍增值域分块 len \in [2^k, 2^{k + 1})，即刚开始对于每个块通过上述的分治预处理出 len 在这个区间内的答案。

然后查询就是中间若干个整块加上两边两个小块，需要查询一个区间的块的一个位置的最大值，对 i 在每个块内的值建 ST 表即可线性。

考虑小块怎么做，必然是 2^{t - 1} \le l \le r < 2^t 这样形式，即 r < 2l，此时对于包含 i 的区间，i 到左右某个端点的距离一定 \le l。

于是对于每个位置 i 处理 f_i, g_i 表示以 i 为左/右端点的合法区间最大权值；然后 ans_i \gets \max \left(\max\limits_{j = i - l +1}^i f_i, \max\limits_{j = i}^{i + l - 1} g_i \right)；线性的话直接单调队列即可。

于是总时间复杂度应该是 O(n \log^2 n + n \log n \log \log n + q \log n + nq) 的。

完整代码：

#include<bits/stdc++.h>
#define lowbit(x) x & (-x)
#define pi pair<ll, ll>
#define ls(k) k << 1
#define rs(k) k << 1 | 1
#define fi first
#define se second
using namespace std;
typedef __int128 __;
typedef long double lb;
typedef double db;
typedef unsigned long long ull;
typedef long long ll;
const int N = 5e4 + 10, M = 17, LM = 5;
const ll inf = 1e10;
inline ll read(){
    ll x = 0, f = 1;
    char c = getchar();
    while(c < '0' || c > '9'){
        if(c == '-')
            f = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9'){
        x = (x << 1) + (x << 3) + (c ^ 48);
        c = getchar();
    }
    return x * f;
}
inline void write(ull x){
    if(x < 0){
        putchar('-');
        x = -x;
    }
    if(x > 9)
        write(x / 10);
    putchar(x % 10 + '0');
}
#define prel(k) (1 << ((k) - 1))
#define prer(k) ((1 << (k)) - 1)
int n, q, block, L, R;
int lg[N], a[N], Q[N], Lb[N], Rb[N];
ll f[N], g[N];
ll pre[N][M], pmx[N][M][LM];
ll s[N], ans[N];
ll smx[M][N], smn[M][N];
inline ll askmx(int l, int r){
    int k = lg[r - l + 1];
    return max(smx[k][l], smx[k][r - (1 << k) + 1]);
}
inline ll askmn(int l, int r){
    int k = lg[r - l + 1];
    return min(smn[k][l], smn[k][r - (1 << k) + 1]);
}
inline ll askpremx(int i, int l, int r){
    int k = lg[r - l + 1];
    return max(pmx[i][l][k], pmx[i][r - (1 << k) + 1][k]);
}
inline void solve(int l, int r){
    if(r - l + 1 < L)
        return ;
    if(l == r){
        ans[l] = a[l];
        return ;
    }
    int mid = (l + r) >> 1;
    solve(l, mid), solve(mid + 1, r);
    ll now = -inf;
    for(int i = l; i <= mid; ++i){
        int x = max(mid + 1, i + L - 1), y = min(r, i + R - 1);
        if(x <= y)
            now = max(now, askmx(x, y) - s[i - 1]);
        ans[i] = max(ans[i], now);
    }
    now = -inf;
    for(int i = r; i >= mid + 1; --i){
        int y = min(mid, i - L + 1), x = max(l, i - R + 1);
        if(x <= y)
            now = max(now, s[i] - askmn(x - 1, y - 1));
        ans[i] = max(ans[i], now);
    }
}
inline void upd(int L, int R){
//  cerr << "other: " << L << ' ' << R << '\n';
    for(int i = 1; i <= n; ++i)
      f[i] = g[i] = -inf;
    for(int i = 1; i <= n; ++i){
        int x = i + L - 1, y = i + R - 1;
        if(x > n)
          break;
        y = min(y, n);
        f[i] = askmx(x, y) - s[i - 1];
//      cerr << i << ' ' << f[i] <<  '\n';
    }
    for(int i = n; i >= 1; --i){
        int y = i - L + 1, x = i - R + 1;
        if(y < 1)
          break;
        x = max(x, 1);
        g[i] = s[i] - askmn(x - 1, y - 1);
//      cerr << i << ' ' << g[i] << '\n';
    }
    int head = 1, top = 0;
    for(int i = 1; i <= n; ++i){
        while(top >= head && f[i] > f[Q[top]])
          --top;
        while(Q[head] < i - L + 1 && head <= top)
          ++head;
        Q[++top] = i;
//      cerr << i << ' ' << Q[head] << ' ' << head << '\n';
        ans[i] = max(ans[i], f[Q[head]]);
    }
    head = 1, top = 0;
    for(int i = n; i >= 1; --i){
        while(top >= head && g[i] > g[Q[top]])
          --top;
        while(Q[head] > i + L - 1 && head <= top)
          ++head;
        Q[++top] = i;
        ans[i] = max(ans[i], g[Q[head]]);
    }
}
int main(){
//  freopen("A.in", "r", stdin);
    lg[0] = 0 - 1;
    n = read();
    for(int i = 1; i <= n; ++i){
        lg[i] = lg[i >> 1] + 1;
        a[i] = read();
        s[i] = s[i - 1] + a[i];
    }
    for(int i = 0; i <= n; ++i)
      smx[0][i] = smn[0][i] = s[i];
    for(int j = 1; j < M; ++j)
      for(int i = 0; i + (1 << j) - 1 <= n; ++i)
        smx[j][i] = max(smx[j - 1][i], smx[j - 1][i + (1 << (j - 1))]), smn[j][i] = min(smn[j - 1][i], smn[j - 1][i + (1 << (j - 1))]);
    for(int k = 1; k <= M; ++k){
        L = prel(k), R = prer(k);
        if(L > n)
          break;
        R = min(R, n);
        block = k;
        for(int i = 1; i <= n; ++i)
          ans[i] = -inf;        
        solve(1, n);
        for(int i = 1; i <= n; ++i){
            pre[i][k] = ans[i];
        }
        Lb[k] = L, Rb[k] = R;
//      cerr << "block: " << L << ' ' << R << '\n';
    }
    Lb[block + 1] = Rb[block + 1] = 1e9;
    for(int i = 1; i <= n; ++i){
        for(int j = 1; j <= block; ++j)
          pmx[i][j][0] = pre[i][j];
        for(int j = 1; j < LM; ++j)
          for(int k = 1; k + (1 << j) - 1 <= block; ++k)
            pmx[i][k][j] = max(pmx[i][k][j - 1], pmx[i][k + (1 << (j - 1))][j - 1]);
    }
    q = read();
    while(q--){
        for(int i = 1; i <= n; ++i)
          ans[i] = -inf;
        L = read(), R = read();
        int bl = 0, br = 0;
        for(int i = 1; i <= block + 1; ++i){
            if(Lb[i] >= L){
                bl = i;
                break;
            }
        }
//      cerr << bl << ' ' << prel(bl) << '\n';
        if(Lb[bl] > R)
          upd(L, R);
        else{
            if(R <= Rb[bl]){
                if(Lb[bl] != L)
                  upd(L, Rb[bl - 1]);
                upd(Lb[bl], R);
            }
            else{
                for(int i = bl; i <= block; ++i)
                  if(Rb[i] <= R)
                    br = i;
//              cerr << bl << ' ' << br << '\n';
                for(int i = 1; i <= n; ++i)
                    ans[i] = max(ans[i], askpremx(i, bl, br));
                if(Lb[bl] != L)
                    upd(L, Rb[bl - 1]);
                if(Rb[br] != R)
                    upd(Lb[br + 1], R);             
            }
        }
        ull s = 0;
        for(int i = 1; i <= n; ++i)
            s ^= (ull) i * (ull)ans[i];
        write(s);
        putchar('\n');
//      for(int i = 1; i <= n; ++i)
//        cerr << ans[i] << ' ';
//      cerr << '\n';
    }
    return 0;
}