「USACO 2023.2 Platinum」Hungry Cow 题解

题目大意

Bessie 每天吃一捆干草。FJ 会在某些天送干草，每次更新操作会修改某天送的干草数量。要求在每次更新后，输出 Bessie 所有能吃到干草的日期之和对 $10^9+7$ 取模的值。

解题思路

核心算法：线段树 + 区间合并

该解法使用线段树维护送干草的日子，通过巧妙的区间合并来高效计算所有吃到干草的日期之和。

关键数据结构

struct Node {
    long long overflow;      // 剩余干草传递到下一段
    long long consumed;      // 本段消耗的干草总数
    long long day_sum;       // 本段吃草日期的和
    long long merge_sum;     // 与左段合并时的额外贡献
} tree[400020];

算法流程

1. 数据预处理

// 离散化送干草的日子
sort(days + 1, days + n + 1);
int compressed_size = unique(days + 1, days + n + 1) - days - 1;
days[compressed_size + 1] = 1e18;  // 设置边界

2. 线段树更新

void upd(int node, int l, int r, int pos, long long bales) {
    if (l == r) {
        // 叶子节点：计算单天的消耗
        long long max_consumable = days[l + 1] - days[l];
        tree[node].consumed = min(bales, max_consumable);
        tree[node].day_sum = range_sum(days[l], days[l] + tree[node].consumed - 1);
        tree[node].overflow = bales - tree[node].consumed;
        return;
    }
    // 递归更新并合并
}

3. 区间合并

void merge(int node, int l, int r) {
    int mid = (l + r) >> 1;
    long long available_days = days[r + 1] - days[mid + 1] - tree[right].consumed;
    
    if (available_days < tree[left].overflow) {
        // 左段剩余干草超过右段容量
        tree[node].overflow = tree[right].overflow + tree[left].overflow - available_days;
        tree[node].consumed = tree[left].consumed + days[r + 1] - days[mid + 1];
        tree[node].day_sum = tree[left].day_sum + range_sum(days[mid + 1], days[r + 1] - 1);
    } else {
        // 左段剩余干草在右段内消耗完
        tree[node].overflow = tree[right].overflow;
        tree[node].consumed = tree[left].consumed + tree[right].consumed + tree[left].overflow;
        // 计算合并产生的额外日期和
    }
}

4. 端点查找

pair<long long, long long> find_endpoint(int node, int l, int r, long long hay_count) {
    // 二分查找干草消耗完的位置
    // 返回最后吃草的日期和对应的日期和
}

算法原理

关键观察

1. 干草消耗连续性：Bessie 连续吃草，直到干草用完
2. 区间独立性：送干草的日子将时间线分成若干段
3. 剩余传递：某天剩余的干草会传递到后续日子

状态设计意义

• overflow：当前区间结束后剩余的干草数量
• consumed：当前区间内消耗的干草总数
• day_sum：当前区间内吃草日期的和
• merge_sum：左右子区间合并时产生的额外日期和

数学工具

等差数列求和

long long range_sum(long long start, long long end) {
    long long count = (end - start + 1) % MOD;
    long long total = ((start + end) % MOD);
    return count * total % MOD * INV2 % MOD;
}

• 计算连续日期 $[start, end]$ 的和
• 使用模逆元处理除法

复杂度分析

• 预处理：$O(n \log n)$
• 每次更新：$O(\log n)$
• 总复杂度：$O(n \log n)$

样例验证

样例1：

更新1: (4,3)
线段树状态：
  区间[4]: consumed=3, day_sum=4+5+6=15, overflow=0
输出: 15

更新2: (1,5)  
线段树状态：
  区间[1,4]: 计算合并后的连续吃草区间
输出: 1+2+...+8=36

更新3: (1,2)
重新计算合并，输出: 1+2+4+5+6=18

代码亮点

1. 离散化处理：将大范围日期压缩到可处理的范围
2. 边界设置：days[compressed_size + 1] = 1e18 简化边界判断
3. 模块化设计：分离区间合并和端点查找逻辑
4. 数学优化：使用等差数列公式快速计算日期和

实现细节

关键函数说明

find_endpoint

在区间内二分查找干草消耗完的位置，用于计算合并时的额外贡献。

merge

处理两种合并情况：

• 左段剩余干草超过右段容量：右段被完全填满
• 左段剩余干草在右段内消耗完：精确计算消耗位置

模运算处理

const long long MOD = 1e9 + 7;
const long long INV2 = (MOD + 1) / 2;  // 2的模逆元

确保所有运算在模意义下进行。

总结

这个解法通过巧妙的线段树区间合并设计，高效解决了动态干草消耗问题：

1. 状态设计：用四个变量完整描述区间状态
2. 合并策略：分类讨论剩余干草的传递情况
3. 数学工具：等差数列求和优化计算
4. 离散化：处理大范围日期

该算法能够处理 $U \leq 10^5$ 的大规模更新，是一个高效且优雅的解决方案。