专栏文章

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

__jxy
P12013题解参与者 2已保存评论 1

文章操作

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

当前评论
1 条
当前快照
1 份
快照标识符
@mipqncav
此快照首次捕获于
2025/12/03 16:21
3 个月前
此快照最后确认于
2025/12/03 16:21
3 个月前
查看原文
因为题目要求最终所选的区间长度不为 11，所以，显然存在结论：每次询问的答案区间长度不是 22 就是 33。
考虑证明。
假设存在长度 k≥4k \geq 4 的区间 S=[a1,a2,…,ak]S = [a_1, a_2, \dots, a_k]，其平均值为 MM，则：
  • 将 SS 分割为前 22 项 [a1,a2][a_1,a_2] 和剩余项 [a3,…,ak][a_3,\dots,a_k]
    • 若 a1+a22≥M\frac{a_1 + a_2}{2} \geq M，则存在长度为 22 的子区间满足条件
    • 否则有： a1+a2<2M  ⟹  ∑i=3kai=kM−(a1+a2)>kM−2M=M(k−2)a_1 + a_2 < 2M \implies \sum_{i=3}^k a_i = kM - (a_1+a_2) > kM - 2M = M(k-2)
对剩余区间 [a3,…,ak][a_3,\dots,a_k] 递归应用上述逻辑：
  • 当剩余长度降为 33 时： 假设剩下的数是 b1,b2,b3b_1,b_2,b_3，显然 ∑i=13bi>3M  ⟹  ∃子区间(b1+b22≥M 或 b1+b2+b33≥M)\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)
  • 最终必然得到长度 22 或 33 的子区间
然后就是数学归纳法:
  • k=2k=2 或 k=3k=3 时结论显然成立
  • 假设对所有长度 <k<k 的区间结论成立
  • 对长度 k≥4k \geq 4 的区间，通过递归分解必然存在符合条件的子区间
知道了这个结论，我们只要维护所有长度为 22 和 33 的子区间的和就好了。
区间加的时候细节有点多。
CPP
#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;
}

评论

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

正在加载评论...