题解：P15574 [USACO26FEB] Milk Buckets S

MLE_Automaton · 2026-03-06 17:17:38 · 题解

思路

考虑使用线段树维护一个区间最上面的桶要往下倒几次才能让最下面的桶倒一次，设左儿子答案为 lans，最右边 a_i 的值为 lr；右儿子答案为 rans，最左边 a_i 的值为 rl，则 pushup 时根节点的答案即为 lans\times rans\times \lceil\frac{rl}{lr}\rceil。

设整个线段树的根节点的答案为 ans，则对于询问的答案为 \lfloor\frac{(t-n+1)}{ans\times (a_1+1)}\rfloor\times a_n。

用 (t-n+1) 和 a_1+1 是因为往下倒还需要一秒的时间。

实现时注意溢出问题。

感觉这题蓝只是因为线段树的门槛。

赛时代码

我写的有点丑，但是关键只有那两个式子。

// Created at 2026-02-21 09:43:04
// Source: USACO - USACO 2026 Third Contest, Silver
// Problem: Problem 2. Milk Buckets
// URL: https://usaco.org/index.php?page=viewproblem&cpid=1579
// Limits: 4000ms 256MB
// By MLE_Automaton

#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=(a),END##i=(b);i<=END##i;++i)
#define pre(i,a,b) for(int i=(a),END##i=(b);i>=END##i;--i)
#define INF 0x3f3f3f3f
#define llINF 0x3f3f3f3f3f3f3f3f
#define mem(a, x) memset((a), (x), sizeof(a))
#define pb push_back
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;

const int N = 3e5 + 5;
namespace segt
{
    struct node
    {
        int l, r; ll x, ml, mr; // most left most right
    } a[N << 1];
    #define ls (u << 1)
    #define rs (u << 1 | 1)
    void pushup(int u)
    {
        // todo
        // this is the most important part wow
        __int128 t = a[ls].x; t *= a[rs].x;
        if (t > llINF) t = llINF;
        if (a[ls].mr < a[rs].ml)
        {
            t *= (a[rs].ml + a[ls].mr - 1) / a[ls].mr;
            if (t > llINF) t = llINF;
        }
        a[u].x = t;
        a[u].ml = a[ls].ml; a[u].mr = a[rs].mr;
    }
    void build(ll *b, int l, int r, int u = 1)
    {
        a[u] = {l, r, 0, 0, 0};
        if (l == r) return a[u].ml = a[u].mr = b[l], a[u].x = 1, void();
        int mid = (l + r) >> 1;
        build(b, l, mid, ls);
        build(b, mid + 1, r, rs);
        pushup(u);
    }
    void mod(int i, ll x, int u = 1)
    {
        if (a[u].l == a[u].r) return a[u].ml = a[u].mr = x, a[u].x = 1, void();
        int mid = a[ls].r;
        if (i <= mid) mod(i, x, ls);
        else mod(i, x, rs);
        pushup(u);
    }
    ll qry() { return a[1].x; }
}
int n, q; ll a[N];
void wte(__int128 x)
{
    if (x / 10) wte(x / 10);
    putchar((x % 10) ^ 48);
}
int main()
{
    scanf("%d", &n);
    rep(i, 1, n) scanf("%lld", &a[i]);
    segt::build(a, 1, n);
    scanf("%d", &q);
    // one loop: a[1] + 1
    // time to get to pool: n - 1
    while (q --)
    {
        ll i, x, t; scanf("%lld%lld%lld", &i, &x, &t);
        a[i] = x; segt::mod(i, x);
        __int128 tt = segt::qry();
        tt *= a[1] + 1; if (tt > llINF) tt = llINF;
        if (t < n - 1) { puts("0"); continue; }
        tt = (t - n + 1) / tt * a[n]; // it can be stuck into 1e27!!!
        wte(tt); puts("");
    }
    return 0;
}