Gym - 100623B Billboard——线段树

Gym - 100623B Billboard——线段树

要实现先上后左，只需要修改一下查询函数，如果当前值x小于等于左区间最大值就查左区间，否则查右区间，边界是只有一个元素时判一下这个元素是否大于等于x，是的话就用一个变量pos记录一下位置，返回true，否则返回false

#include #include #include #include using namespace std;const int maxn = 2e5 + 10;int h, w, n, pos;int a[maxn<<2];void pushup(int root) { a[root] = max(a[root<<1], a[root<<1|1]); }void build(int l, int r, int root) { if (l == r) { a[root] = w; return; } int mid = (l+r)>>1; build(l, mid, root<<1); build(mid+1, r, root<<1|1); pushup(root);}void update(int l, int r, int root, int p, int x) { if (l == r) { a[root] -= x; return; } int mid = (l+r)>>1; if (p <= mid) update(l, mid, root<<1, p, x); else update(mid + 1, r, root<<1|1, p, x); pushup(root);}bool query(int l, int r, int root, int x) { if (l == r) { if (x <= a[root]) { pos = l; return true; } else return false; } int mid = (l+r)>>1; if (x <= a[root<<1]) return query(l, mid, root<<1, x); else return query(mid+1, r, root<<1|1, x);}int main() { freopen("billboard.in", "r", stdin); freopen("billboard.out", "w", stdout); scanf("%d %d %d", &h, &w, &n); int x, len = min(h, n); build(1, len, 1); for (int i = 1; i <= n; i++) { scanf("%d", &x); if (query(1, len, 1, x)) { printf("%d\n", pos); update(1, len, 1, pos, x); } else printf("-1\n"); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。