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

jiangxinyang2012 · 2025-04-02 09:45:07 · 题解

因为题目要求最终所选的区间长度不为 1，所以，显然存在结论：每次询问的答案区间长度不是 2 就是 3。

考虑证明。

假设存在长度 k \geq 4 的区间 S = [a_1, a_2, \dots, a_k]，其平均值为 M，则：

• 将 S 分割为前 2 项 [a_1,a_2] 和剩余项 [a_3,\dots,a_k]
• • 若 \frac{a_1 + a_2}{2} \geq M，则存在长度为 2 的子区间满足条件
  • 否则有： a_1 + a_2 < 2M \implies \sum_{i=3}^k a_i = kM - (a_1+a_2) > kM - 2M = M(k-2)

对剩余区间 [a_3,\dots,a_k] 递归应用上述逻辑：

• 当剩余长度降为 3 时： 假设剩下的数是 b_1,b_2,b_3，显然 \sum_{i=1}^3 b_i > 3M \implies \exists \text{子区间} \left( \frac{b_1+b_2}{2} \geq M \ \text{或} \ \frac{b_1+b_2+b_3}{3} \geq M \right)
• 最终必然得到长度 2 或 3 的子区间

然后就是数学归纳法:

• 假设对所有长度 <k 的区间结论成立
• 对长度 k \geq 4 的区间，通过递归分解必然存在符合条件的子区间

知道了这个结论，我们只要维护所有长度为 2 和 3 的子区间的和就好了。

区间加的时候细节有点多。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll mod = 1e9 + 7;
const int N = 1000005;
const ll INF = 0x3f3f3f3f3f3f3f3f;
#define int long long
int a[N];
int val2[N << 2], val3[N << 2];
void pushup(int u) {
    val2[u] = max(val2[u << 1], val2[u << 1 | 1]);
    val3[u] = max(val3[u << 1], val3[u << 1 | 1]);
}
int tag2[N << 2], tag3[N << 2];
void pushdown(int u) {
    if (tag2[u]) {
        val2[u << 1] += tag2[u];
        val2[u << 1 | 1] += tag2[u];
        tag2[u << 1] += tag2[u];
        tag2[u << 1 | 1] += tag2[u];
        tag2[u] = 0;
    }
    if (tag3[u]) {
        val3[u << 1] += tag3[u];
        val3[u << 1 | 1] += tag3[u];
        tag3[u << 1] += tag3[u];
        tag3[u << 1 | 1] += tag3[u];
        tag3[u] = 0;
    }
}
void build(int u, int l, int r) {
    if (l == r) {
        val2[u] = a[l] + a[l + 1];
        val3[u] = a[l] + a[l + 1] + a[l + 2];
        return;
    }
    int mid = l + r >> 1;
    build(u << 1, l, mid);
    build(u << 1 | 1, mid + 1, r);
    pushup(u);
}
void update2(int u, int l, int r, int x, int y, int v) {
    if (x <= l && r <= y) {
        val2[u] += v;
        tag2[u] += v;
        return;
    }
    int mid = l + r >> 1;
    pushdown(u);
    if (x <= mid) update2(u << 1, l, mid, x, y, v);
    if (y > mid) update2(u << 1 | 1, mid + 1, r, x, y, v);
    pushup(u);
}
void update3(int u, int l, int r, int x, int y, int v) {
    if (x <= l && r <= y) {
        val3[u] += v;
        tag3[u] += v;
        return;
    }
    int mid = l + r >> 1;
    pushdown(u);
    if (x <= mid) update3(u << 1, l, mid, x, y, v);
    if (y > mid) update3(u << 1 | 1, mid + 1, r, x, y, v);
    pushup(u);
}
int query2(int u, int l, int r, int x, int y) {
    if (x <= l && r <= y) return val2[u];
    int mid = l + r >> 1;
    pushdown(u);
    int res = -INF;
    if (x <= mid) res = max(res, query2(u << 1, l, mid, x, y));
    if (y > mid) res = max(res, query2(u << 1 | 1, mid + 1, r, x, y));
    return res;
}
int query3(int u, int l, int r, int x, int y) {
    if (x <= l && r <= y) return val3[u];
    int mid = l + r >> 1;
    pushdown(u);
    int res = -INF;
    if (x <= mid) res = max(res, query3(u << 1, l, mid, x, y));
    if (y > mid) res = max(res, query3(u << 1 | 1, mid + 1, r, x, y));
    return res;
}
signed main() {
    int n, m;
    scanf("%lld%lld", &n, &m);
    for (int i = 1; i <= n; i++) scanf("%lld", &a[i]);
    build(1, 1, n);
    while (m--) {
        int op, l, r;
        int x;
        scanf("%lld%lld%lld", &op, &l, &r);
        if (op == 1) {
            scanf("%lld", &x);
            if (r - 1 >= l) update2(1, 1, n, l, r - 1, 2 * x);
            update2(1, 1, n, r, r, x);
            if (l - 1 >= 1) update2(1, 1, n, l - 1, l - 1, x);
            if (r - 2 >= l) update3(1, 1, n, l, r - 2, 3 * x);
            if (r - 1 >= l) update3(1, 1, n, r - 1, r - 1, 2 * x);
            update3(1, 1, n, r, r, x);
            if (l == r) {
                if (l > 1) update3(1, 1, n, l - 1, l - 1, x);
                if (l > 1) update3(1, 1, n, l - 2, l - 2, x);
            } else {
                if (l > 1) update3(1, 1, n, l - 1, l - 1, 2 * x);
                if (l > 2) update3(1, 1, n, l - 2, l - 2, x);
            }
        } else {
            int ans2x = query2(1, 1, n, l, r - 1), ans2y = 2;
            int ansx = ans2x, ansy = ans2y;
            if (r - 2 >= l) {
                int ans3x = query3(1, 1, n, l, r - 2), ans3y = 3;
                if (ans2x * 1.0 / ans2y > ans3x * 1.0 / ans3y) {
                    ansx = ans2x;
                    ansy = ans2y;
                } else {
                    ansx = ans3x;
                    ansy = ans3y;
                }
            }
            if (ansx == 0) {
                printf("0/1\n");
            } else if (ansx < 0) {
                ansx *= -1;
                int g = __gcd(ansx, ansy);
                ansx /= g;
                ansy /= g;
                printf("-%lld/%lld\n", ansx, ansy);
            } else {
                int g = __gcd(ansx, ansy);
                ansx /= g;
                ansy /= g;
                printf("%lld/%lld\n", ansx, ansy);
            }
        }
    }
    return 0;
}