一、题目
1、题目描述
一个音乐会总共有
n排座位，编号从0到n - 1，每一排有m个座椅，编号为0到m - 1。你需要设计一个买票系统，针对以下情况进行座位安排：
- 同一组的
k位观众坐在 同一排座位，且座位连续 。k位观众中 每一位 都有座位坐，但他们 不一定 坐在一起。由于观众非常挑剔，所以：
- 只有当一个组里所有成员座位的排数都 小于等于
maxRow，这个组才能订座位。每一组的maxRow可能 不同 。- 如果有多排座位可以选择，优先选择 最小 的排数。如果同一排中有多个座位可以坐，优先选择号码 最小 的。
请你实现
BookMyShow类：
BookMyShow(int n, int m)，初始化对象，n是排数，m是每一排的座位数。int[] gather(int k, int maxRow)返回长度为2的数组，表示k个成员中 第一个座位 的排数和座位编号，这k位成员必须坐在 同一排座位，且座位连续 。换言之，返回最小可能的r和c满足第r排中[c, c + k - 1]的座位都是空的，且r <= maxRow。如果 无法 安排座位，返回[]。boolean scatter(int k, int maxRow)如果组里所有k个成员 不一定 要坐在一起的前提下，都能在第0排到第maxRow排之间找到座位，那么请返回true。这种情况下，每个成员都优先找排数 最小 ，然后是座位编号最小的座位。如果不能安排所有k个成员的座位，请返回false。
2、接口描述
cpp
class BookMyShow {
public:BookMyShow(int n, int m) {}vector<int> gather(int k, int maxRow) {}bool scatter(int k, int maxRow) {}
};/*** Your BookMyShow object will be instantiated and called as such:* BookMyShow* obj = new BookMyShow(n, m);* vector<int> param_1 = obj->gather(k,maxRow);* bool param_2 = obj->scatter(k,maxRow);*/
3、原题链接
2286. 以组为单位订音乐会的门票
二、解题报告
1、思路分析
对于gather 相当于找从上往下第一个剩余空间够k的排
对于scatter 相当于找从上往下依次填k个空格
我们用线段树来维护 区间剩余容量以及区间容量最值
对于gather我们线段树二分找到第一个符合的即可
对于scatter 我们线段树二分找到第一个不空的，依次往后填
由于填满的格子不会再次在 scatter中访问，所以是 O((n + q)logn) 的
2、复杂度
时间复杂度： O((N + Q)logN)空间复杂度：O(NlogN)
3、代码详解
cpp
using u32 = unsigned;
using i64 = long long;
using u64 = unsigned long long;constexpr int inf32 = 1E9 + 7;
constexpr i64 inf64 = 1E18 + 7;template<class Info, class Tag>
struct LazySegmentTree {int n;std::vector<Info> info;std::vector<Tag> tag;LazySegmentTree() : n(0) {}LazySegmentTree(int _n, Info _v = Info()) {init(_n, _v);}template<class T>LazySegmentTree(std::vector<T> _init) {init(_init);}void init(int _n, const Info &_v = Info()) {init(std::vector<Info>(_n, _v));}template<class T>void init(const std::vector<T> &_init) {n = _init.size();info.assign(4 << std::__lg(n), Info());tag.assign(4 << std::__lg(n), Tag());auto build = [&](auto &&self, int p, int l, int r) -> void {if (l == r) {info[p] = _init[l];return;}int m = (l + r) / 2;self(self, p * 2, l, m);self(self, p * 2 + 1, m + 1, r);pull(p);};build(build, 1, 0, n - 1);}void pull(int p) {info[p] = info[p * 2] + info[p * 2 + 1];}void apply(int p, const Tag &v) {info[p].apply(v);tag[p].apply(v);}void push(int p) {apply(2 * p, tag[p]);apply(2 * p + 1, tag[p]);tag[p] = Tag{};}void modify(int p, int l, int r, int x, const Info &v) {if (l == r) {info[p] = v;return;}int m = (l + r) / 2;push(p);if (x < m)modify(p * 2, l, m, x, v);elsemodify(p * 2 + 1, m + 1, r, x, v);pull(p);}void modify(int x, const Info &v) {modify(1, 0, n - 1, x, v);}Info rangeQuery(int p, int l, int r, int x, int y) {if (l > y || r < x)return Info{};if (x <= l && r <= y) return info[p];int m = (l + r) / 2;push(p);auto t = rangeQuery(p * 2, l, m, x, y) + rangeQuery(p * 2 + 1, m + 1, r, x, y);return t;}Info rangeQuery(int l, int r) {return rangeQuery(1, 0, n - 1, l, r);}void rangeApply(int p, int l, int r, int x, int y, const Tag &v) {if (l > y || r < x) return;if (x <= l && r <= y) {apply(p, v);return;}int m = (l + r) / 2;push(p);rangeApply(p * 2, l, m, x, y, v);rangeApply(p * 2 + 1, m + 1, r, x, y, v);pull(p);}void rangeApply(int l, int r, const Tag &v) {rangeApply(1, 0, n - 1, l, r, v);}template<class F>int findFirst(int p, int l, int r, int x, int y, F pred) {if (l > y || r < x || !pred(info[p])) {return -1;}if (l == r)return l;int m = (l + r) / 2;push(p);int res = findFirst(p * 2, l, m, x, y, pred);if (res == -1)res = findFirst(p * 2 + 1, m + 1, r, x, y, pred);return res;}template<class F>int findFirst(int l, int r, F pred) {return findFirst(1, 0, n - 1, l, r, pred);}template<class F>int findLast(int p, int l, int r, int x, int y, F pred) {if (l > y || r < x || !pred(info[p])) {return -1;}if (l == r)return l;int m = (l + r) / 2;push(p);int res = findLast(p * 2 + 1, m + 1, r, x, y, pred);if (res == -1)res = findLast(p * 2, l, m, x, y, pred);return res;}template<class F>int findLast(int l, int r, F pred) {return findLast(1, 0, n - 1, l, r, pred);}
};struct Tag{int x = 0;void apply(const Tag &t) {x += t.x;}
};struct Info{i64 s = 0;int ma = 0;void apply(const Tag &t) {s += t.x;ma += t.x;}friend Info operator+ (const Info &a, const Info &b) {return {a.s + b.s, std::max(a.ma, b.ma)};}
};struct F{int t = 0;bool operator()(const Info& v) {return v.ma >= t;}
};class BookMyShow {
public:int n, m;LazySegmentTree<Info, Tag> sgt;BookMyShow(int n_, int m_): n(n_), m(m_), sgt(std::vector<Info>(n, {m, m})) {}vector<int> gather(int k, int maxRow) {int res = sgt.findFirst(0, maxRow, F{k});if (res == -1)return {};int c = m - sgt.rangeQuery(res, res).s;sgt.rangeApply(res, res, Tag{-k});return {res, c};}bool scatter(int k, int maxRow) {if (sgt.rangeQuery(0, maxRow).s < k) return false;int res = sgt.findFirst(0, maxRow, F{1});while (k) {int c = std::min<i64>(k, sgt.rangeQuery(res, res).s);sgt.rangeApply(res, res, Tag{-c});k -= c;++ res;}return true;}
};/*** Your BookMyShow object will be instantiated and called as such:* BookMyShow* obj = new BookMyShow(n, m);* vector<int> param_1 = obj->gather(k,maxRow);* bool param_2 = obj->scatter(k,maxRow);*/