专栏文章

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

CClaire0918
P12013题解参与者 2已保存评论 3

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
3 条
当前快照
1 份
快照标识符
@mipql28u
此快照首次捕获于
2025/12/03 16:19
3 个月前
此快照最后确认于
2025/12/03 16:19
3 个月前
查看原文
我们作出猜想：最优的 [L,R][L, R] 长度一定不超过 33。
我们先说明一个引理：如果 AA 可以划分成两个子串 BB 和 CC，那么要么 B‾≥A‾\overline B \geq \overline A，要么 C‾≥A‾\overline C \geq \overline A。
证明：
设 p=∑B,q=∑C,n=∣B∣,m=∣C∣p = \sum B, q = \sum C, n = |B|, m = |C|，那么 ∑A=p+q,∣A∣=n+m\sum A = p + q, |A| = n + m，于是
A‾=p+qn+mB‾=pnC‾=qm\overline A = \frac{p + q}{n + m}\\ \overline B = \frac{p}{n}\\ \overline C = \frac{q}{m}\\
考虑反证法，假设原命题不成立，也就是说
pn<p+qn+mqm<p+qn+m\frac{p}{n} < \frac{p + q}{n + m}\\ \frac{q}{m} < \frac{p + q}{n + m}\\
移项
pn+pm<pn+qnqn+qm<pm+qmpn + pm < pn + qn\\ qn + qm < pm + qm\\
两式相加
pn+pm+qn+qm<pn+pm+qn+qmpn + pm + qn + qm < pn + pm + qn + qm\\
这显然是错误的，从而假设不成立，原命题得证。□\square
对于一个长度大于 33 的 [L,R][L, R]，我们一定可以将其分为两个长度都大于等于 22 的子串。依照引理，这二者中至少有一个比原串更优，所以最优的 [L,R][L, R] 长度小于等于 33。
记 bi=ai−1+ai2,ci=ai−2+ai−1+ai3b_i = \frac{a_{i - 1} + a_i}{2}, c_i = \frac{a_{i - 2} + a_{i - 1} + a_i}{3}。查询实际上变成了求
max⁡{max⁡i=l+1r{bi},max⁡i=l+2r{ci}}\max\{\max_{i = l + 1}^{r} \{b_i\}, \max_{i = l + 2}^{r} \{c_i\}\}
使用线段树维护 {bi},{ci}\{b_i\}, \{c_i\} 即可。时间复杂度 O(qlog⁡n)\mathcal{O}(q\log n)。
Code：
CPP
#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;
}

评论

共 3 条评论，欢迎与作者交流。

正在加载评论...