P1204 [USACO1.2] 挤牛奶Milking Cows
题目描述
三个农民每天清晨 \(5\) 点起床，然后去牛棚给三头牛挤奶。
第一个农民在 \(300\) 秒 (从 \(5\) 点开始计时) 给他的牛挤奶，一直到 \(1000\) 秒。第二个农民在 \(700\) 秒开始，在 \(1200\) 秒结束。第三个农民在 \(1500\) 秒开始，\(2100\) 秒结束。
期间最长的至少有一个农民在挤奶的连续时间为 \(900\) 秒 (从 \(300\) 秒到 \(1200\) 秒)，而最长的无人挤奶的连续时间(从挤奶开始一直到挤奶结束)为 \(300\) 秒 (从 \(1200\) 秒到 \(1500\) 秒)。
你的任务是编一个程序，读入一个有 \(n\) 个农民挤 \(n\) 头牛的工作时间列表，计算以下两点(均以秒为单位):
最长至少有一人在挤奶的时间段。
最长的无人挤奶的时间段。（从有人挤奶开始算起）
输入格式
第一行一个正整数 \(n\)
接下来 \(n\) 行，每行两个非负整数 \(l,r\)，表示一个农民的开始时刻与结束时刻。
输出格式
一行，两个整数，即题目所要求的两个答案。
样例 #1
样例输入 #1
3
300 1000
700 1200
1500 2100
样例输出 #1
900 300
提示
【数据范围】
对于 \(100\%\) 的数据，\(1\le n \le 5000\)，\(0 \le l \le r \le 10^6\)。
题目翻译来自NOCOW。
USACO Training Section 1.2
解题思路
没什么好说的自己看看吧
每个农夫就\(assign\)一下，但要注意一下细节
应该写\(assign(l,r-1,1)\)，查询时应写\(query(mi，mx，1/0)\)
同时，因为下面的代码中有\(r-1\)，所以初始化时应该包含下标\(0\)
#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
// 柯朵莉树模板
struct Node {
int l, r; // l和r表示这一段的起点和终点
mutable int v; // v表示这一段上所有元素相同的值是多少,注意关键字 mutable,使得set中结构体属性可修改
bool operator<(const Node &b) const {
return l < b.l; // 规定按照每段的左端点排序
}
};
set<Node> s; // 柯朵莉树的区间集合
// 分裂:[l,x-1],[x,r]
set<Node>::iterator split(int x) {
auto it = s.lower_bound({x});
if (it != s.end() && it->l == x) return it; // 一击命中
it--; // 没有找到就减1个继续找
if (it->r < x) return s.end(); // 真的没找到,返回s.end()
int l = it->l, r = it->r, v = it->v; // 没有被返回，说明找到了,记录下来，防止后面删除时被破坏
s.erase(it); // 删除整个区间
s.insert({l, x - 1, v}); //[l,x-1]拆分
return s.insert({x, r, v}).first; //[x,r]拆分
}
// 区间加
void add(int l, int r, int v) {
auto R = split(r + 1), L = split(l);
for (; L != R; L++) L->v += v;
}
// 区间赋值
void assign(int l, int r, int v) {
auto R = split(r + 1), L = split(l);
s.erase(L, R); // 删除旧区间
s.insert({l, r, v}); // 增加新区间
}
// 区间查询
int query(int l, int r, bool v) {
int sum = 0, res = 0;
auto R = split(r + 1), L = split(l);
for (; L != R; L++)
if (L->v == v)
sum += L->r - L->l + 1;
else {
res = max(res, sum);
sum = 0;
}
return res;
}
int main() {
// 加快读入
ios::sync_with_stdio(false), cin.tie(0);
int n;
cin >> n;
int mi = INF, mx = -INF;
// 柯朵莉树需要进行初始化,而且，最好带0，防止RE
s.insert({0, 1000000, 0});
while (n--) {
int l, r;
cin >> l >> r;
assign(l, r - 1, 1); // 这里如果l=r=1，按这样[1,0],就会出现边界问题，所以上面最初时加入了{0,1000000}
mi = min(mi, l);
mx = max(mx, r);
}
cout << query(mi, mx, 1) << ' ' << query(mi, mx, 0);
return 0;
}