今日
- 早晨运动，跑了3个800米，跟不上老码农节奏（虽然他也不快。。。）；
- 作业：已经完成80%；
- 中午：家庭会议；
- 信息：1小时AC掉P8856；
- 接下来时光：该放松下了。
题目
题目原文请移步下面的链接
- https://www.luogu.com.cn/problem/P8856
- 参考题解：https://www.luogu.com.cn/problem/solution/P8856
- 标签：
OI、数据结构、线段树
题解
思路
- 求区间最大值（既被预订座位最多的一天有几个预订），如果在预定n个座位后，是否会超出预订限额，若超出，则不做处理，输出N，反之，输出T；
- 易错点
- 不能用区间被预订的座位总数去加，因为可能出现某一天预订数量已经超出限额但另一天很少，最终座位总数未超过限额的情况；
- 区间应为[0, d - 1]，因为最后一站乘车人下车，座位就空出来了。
代码
#include <bits/stdc++.h>
using namespace std;
#define endl '\n';
typedef long long LL;struct edge {int l, r;LL m, add;
};struct Segment_Tree {vector<edge> t;vector<LL> a;Segment_Tree(int n) : t(4 * n), a(n + 1){}void push_up(int u) {t[u].m = max(t[u << 1].m, t[u << 1 | 1].m);}void push_down(int u) {auto &root = t[u], &left = t[u << 1], &right = t[u << 1 | 1];if (root.add) {left.add += root.add;left.m += root.add;right.add += root.add;right.m += root.add;root.add = 0;}}void build(int u, int l, int r) {t[u].l = l;t[u].r = r;if (l == r) {t[u].m = a[l];return;}int mid = l + r >> 1;build(u << 1, l, mid);build(u << 1 | 1, mid + 1, r);push_up(u);}LL query(int u, int l, int r) {if (t[u].l >= l && t[u].r <= r) {return t[u].m;}push_down(u);int mid = t[u].l + t[u].r >> 1;LL s = 0;if (l <= mid) {s = max(s, query(u << 1, l, r));}if (r > mid) {s = max(s, query(u << 1 | 1, l, r));}return s;}void cnt(int u, int l, int r, LL v) {if (t[u].l >= l && t[u].r <= r) {t[u].m += v;t[u].add += v;} else {push_down(u);int mid = t[u].l + t[u].r >> 1;if (l <= mid) {cnt(u << 1, l, r, v);}if (r > mid) {cnt(u << 1 | 1, l, r, v);}push_up(u);}}
};void best_coder() {int c, s, q;cin >> c >> s >> q;Segment_Tree st(c);st.build(1, 1, c);for (int i = 0; i < q; ++i) {int o, d, n;cin >> o >> d >> n;if(st.query(1, o, d - 1) + n <= s) {st.cnt(1, o, d - 1, n);cout << "T" << endl;} else {cout << "N" << endl;}}
}void happy_coder() {
}int main() {// 提升cin、cout效率ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);// 小码匠best_coder();// 最优解// happy_coder();// 返回return 0;
}
