题解：P12013 [Ynoi April Fool's Round 2025] 牢夸

· · 题解

我们作出猜想：最优的 [L, R] 长度一定不超过 3。

我们先说明一个引理：如果 A 可以划分成两个子串 B 和 C，那么要么 \overline B \geq \overline A，要么 \overline C \geq \overline A。

证明：

设 p = \sum B, q = \sum C, n = |B|, m = |C|，那么 \sum A = p + q, |A| = n + m，于是

\overline A = \frac{p + q}{n + m}\\ \overline B = \frac{p}{n}\\ \overline C = \frac{q}{m}\\

考虑反证法，假设原命题不成立，也就是说

\frac{p}{n} < \frac{p + q}{n + m}\\ \frac{q}{m} < \frac{p + q}{n + m}\\

移项

pn + pm < pn + qn\\ qn + qm < pm + qm\\

两式相加

pn + pm + qn + qm < pn + pm + qn + qm\\

这显然是错误的，从而假设不成立，原命题得证。\square

对于一个长度大于 3 的 [L, R]，我们一定可以将其分为两个长度都大于等于 2 的子串。依照引理，这二者中至少有一个比原串更优，所以最优的 [L, R] 长度小于等于 3。

记 b_i = \frac{a_{i - 1} + a_i}{2}, c_i = \frac{a_{i - 2} + a_{i - 1} + a_i}{3}。查询实际上变成了求

\max\{\max_{i = l + 1}^{r} \{b_i\}, \max_{i = l + 2}^{r} \{c_i\}\}

使用线段树维护 \{b_i\}, \{c_i\} 即可。时间复杂度 \mathcal{O}(q\log n)。

Code：

#include<bits/stdc++.h>
#define mem(a, v) memset(a, v, sizeof(a));

using namespace std;

const int maxn = 1e6 + 10;

struct{
     struct{
        int l, r;
        long long value, tag;
    } tree[maxn << 2];
    inline void build(int index, int l, int r){
        tree[index].l = l, tree[index].r = r;
        if (l == r){
            return;
        }
        const int mid = l + r >> 1;
        build(index << 1, l, mid), build(index << 1 | 1, mid + 1, r);
    }
    inline void basic_add(int index, long long k){
        tree[index].value += k, tree[index].tag += k;
    }
    inline void pushup(int index){
        tree[index].value = max(tree[index << 1].value, tree[index << 1 | 1].value);
    }
    inline void pushdown(int index){
        basic_add(index << 1, tree[index].tag), basic_add(index << 1 | 1, tree[index].tag), tree[index].tag = 0;
    }
    inline void modify(int index, int l, int r, long long k){
        if (l <= tree[index].l && r >= tree[index].r){
            basic_add(index, k);
            return;
        }
        pushdown(index);
        const int mid = tree[index].l + tree[index].r >> 1;
        if (l <= mid){
            modify(index << 1, l, r, k);
        }
        if (r > mid){
            modify(index << 1 | 1, l, r, k);
        }
        pushup(index);
    }
    inline long long query(int index, int l, int r){
        if (l <= tree[index].l && r >= tree[index].r){
            return tree[index].value;
        }
        pushdown(index);
        const int mid = tree[index].l + tree[index].r >> 1;
        long long res = -1e18;
        l <= mid && (res = max(res, query(index << 1, l, r)));
        r > mid && (res = max(res, query(index << 1 | 1, l, r)));
        return res;
    }
} seg2, seg3;

int n, q;
long long a[maxn], a2[maxn], a3[maxn];

int main(){
    scanf("%d %d", &n, &q);
    for (int i = 1; i <= n; i++){
        scanf("%lld", &a[i]);
        i >= 2 && (a3[i] = (a2[i] = a[i] + a[i - 1]) + a[i - 2]);
    }
    a2[1] = a3[1] = a3[2] = -1e18;
    seg2.build(1, 1, n), seg3.build(1, 1, n);
    for (int i = 1; i <= n; i++){
        seg2.modify(1, i, i, a2[i]), seg3.modify(1, i, i, a3[i]);
    }
    while (q--){
        int op, l, r;
        scanf("%d %d %d", &op, &l, &r);
        if (op == 1){
            long long x;
            scanf("%lld", &x);
            seg2.modify(1, l, l, x), seg3.modify(1, l, l, x);
            if (l + 1 <= r){
                seg2.modify(1, l + 1, r, x << 1), seg3.modify(1, l + 1, l + 1, x << 1);
            }
            if (r + 1 <= n){
                seg2.modify(1, r + 1, r + 1, x), seg3.modify(1, r + 1, r + 1, l == r ? x : x << 1);
            }
            if (l + 2 <= r){
                seg3.modify(1, l + 2, r, x * 3);
            }
            if (r + 2 <= n){
                seg3.modify(1, r + 2, r + 2, x);
            }
        }else{
            const long long res2 = seg2.query(1, l + 1, r), res3 = (l + 2 <= r ? seg3.query(1, l + 2, r) : -1e18);
            long long res = res2 * 3 > res3 << 1 ? res2 : res3;
            int len = res2 * 3 > res3 << 1 ? 2 : 3;
            res % len || (res /= len, len = 1);
            printf("%lld/%d\n", res, len);
        }
    }

return 0;
}