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

· · 题解

注意到最优区间的长度一定是 2 或 3，直接用线段树维护连续 2 格和连续 3 格的和的最大值。

区间加细节较多，要分成区间左侧、区间前半段、和区间右半段共三段维护，还要讨论更新区间的长度，具体见代码。

const ll N = 1e6 + 10, inf = 3e15;
ll a[N], sgtr2[N * 4], sgtr3[N * 4], tag2[N * 4], tag3[N * 4];

ll ls(ll p) {
    return p * 2;
}

ll rs(ll p) {
    return p * 2 + 1;
}

void pushup2(ll p) {
    sgtr2[p] = max(sgtr2[ls(p)], sgtr2[rs(p)]);
}

void pushup3(ll p) {
    sgtr3[p] = max(sgtr3[ls(p)], sgtr3[rs(p)]);
}

void pushdown2(ll p) {
    sgtr2[ls(p)] += tag2[p];
    sgtr2[rs(p)] += tag2[p];
    tag2[ls(p)] += tag2[p];
    tag2[rs(p)] += tag2[p];
    tag2[p] = 0;
}

void pushdown3(ll p) {
    sgtr3[ls(p)] += tag3[p];
    sgtr3[rs(p)] += tag3[p];
    tag3[ls(p)] += tag3[p];
    tag3[rs(p)] += tag3[p];
    tag3[p] = 0;
}

void build(ll p, ll l, ll r) {
    if (l == r) {
        sgtr2[p] = a[l] + a[l + 1];
        sgtr3[p] = a[l] + a[l + 1] + a[l + 2];
        return;
    }

    ll mid = (l + r) / 2;
    build(ls(p), l, mid);
    build(rs(p), mid + 1, r);
    pushup2(p);
    pushup3(p);
}

void upd2(ll p, ll l, ll r, ll ql, ll qr, ll val) {
    if (ql > r or qr < l)
        return;

//  cout << "upd2:" << l << " " << r << '\n';
//  pause;

    if (ql <= l and r <= qr) {
        sgtr2[p] += val;
        tag2[p] += val;
        return;
    }

    ll mid = (l + r) / 2;

    if (tag2[p])
        pushdown2(p);

    upd2(ls(p), l, mid, ql, qr, val);
    upd2(rs(p), mid + 1, r, ql, qr, val);
    pushup2(p);
}

void upd3(ll p, ll l, ll r, ll ql, ll qr, ll val) {
    if (ql > r or qr < l)
        return;

//  cout << "upd3:" << l << " " << r << '\n';
//  pause;

    if (ql <= l and r <= qr) {
        sgtr3[p] += val;
        tag3[p] += val;
        return;
    }

    ll mid = (l + r) / 2;

    if (tag3[p])
        pushdown3(p);

    upd3(ls(p), l, mid, ql, qr, val);
    upd3(rs(p), mid + 1, r, ql, qr, val);
    pushup3(p);
}

ll query2(ll p, ll l, ll r, ll ql, ll qr) {
    if (ql > r or qr < l)
        return -inf;

    if (ql <= l and r <= qr)
        return sgtr2[p];

    ll mid = (l + r) / 2;

    if (tag2[p])
        pushdown2(p);

    return max(query2(ls(p), l, mid, ql, qr), query2(rs(p), mid + 1, r, ql, qr));
}

ll query3(ll p, ll l, ll r, ll ql, ll qr) {
    if (ql > r or qr < l)
        return -inf;

    if (ql <= l and r <= qr)
        return sgtr3[p];

    ll mid = (l + r) / 2;

    if (tag3[p])
        pushdown3(p);

    return max(query3(ls(p), l, mid, ql, qr), query3(rs(p), mid + 1, r, ql, qr));
}

ll n, q;

int main() {
    cin >> n >> q;

    rep(i, 1, n) cin >> a[i];

    build(1, 1, n);

    count(q) {
        ll ty, l, r, val;
        cin >> ty;

        if (ty == 1) {
            cin >> l >> r >> val;

            if (r - 1 >= l)
                upd2(1, 1, n, l, r - 1, val * 2);

            upd2(1, 1, n, r, r, val);

            if (l - 1 >= 1)
                upd2(1, 1, n, l - 1, l - 1, val);

            if (r - 2 >= l)
                upd3(1, 1, n, l, r - 2, val * 3);

            if (r - 1 >= l)
                upd3(1, 1, n, r - 1, r - 1, val * 2);

            upd3(1, 1, n, r, r, val);

            if (l >= 2) {
                if (r - l + 1 >= 2)
                    upd3(1, 1, n, l - 1, l - 1, val * 2);
                else
                    upd3(1, 1, n, l - 1, l - 1, val);
            }

            if (l >= 3)
                upd3(1, 1, n, l - 2, l - 2, val);

//          cout << query2(1, 1, n, 4, 5) << '\n';
//          pause;
        } else {
            cin >> l >> r;
            ll fm, fz, ans2 = query2(1, 1, n, l, r - 1), ans3 = -inf;

            if (l <= r - 2)
                ans3 = query3(1, 1, n, l, r - 2);

//          cout << "ans2=" << ans2 << ",ans3=" << ans3 << '\n';
//          pause;

            if (ans2 * 1.0 / 2 >= ans3 * 1.0 / 3) {
                fz = ans2;
                fm = 2;
            } else {
                fz = ans3;
                fm = 3;
            }

            if (fz == 0) {
                cout << "0/1\n";
                ctn;
            }

            if (fz < 0) {
                cout << "-";
                fz *= -1;
            }

            ll temp = __gcd(fz, fm);
            fz /= temp;
            fm /= temp;

            cout << fz << "/" << fm << '\n';
        }
    }
}