POJ 3667 Hotel 线段树 区间合并 入门题

发布时间:2016-12-6 8:53:50 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"POJ 3667 Hotel 线段树 区间合并 入门题",主要涉及到POJ 3667 Hotel 线段树 区间合并 入门题方面的内容,对于POJ 3667 Hotel 线段树 区间合并 入门题感兴趣的同学可以参考一下。

#include<stdio.h> #include<string.h> #include<algorithm> using namespace std; #define maxn 50003 #define lson l, m, rt<<1 #define rson m+1, r, rt<<1|1 #define mid int m = (l + r)>>1 int col[maxn<<2]; int lsum[maxn<<2], msum[maxn<<2], rsum[maxn<<2]; int n, m; int max(int a , int b) { return a > b ? a : b; } void pushup(int rt, int len) { lsum[rt] = lsum[rt<<1]; rsum[rt] = rsum[rt<<1|1]; if(lsum[rt] == len - (len>>1)) lsum[rt] += lsum[rt<<1|1]; if(rsum[rt] == (len>>1)) rsum[rt] += rsum[rt<<1]; msum[rt] = max(rsum[rt<<1] + lsum[rt<<1|1], max(msum[rt<<1], msum[rt<<1|1]) ); } void pushdown(int rt, int len) { if(col[rt] != -1) { col[rt<<1] = col[rt<<1|1] = col[rt]; lsum[rt<<1] = rsum[rt<<1] = msum[rt<<1] = col[rt] ? 0 :(len - (len >>1)); lsum[rt<<1|1] = rsum[rt<<1|1] = msum[rt<<1|1] = col[rt] ? 0 : (len>>1) ; col[rt] = -1; } } void build(int l, int r, int rt) { lsum[rt] = msum[rt] = rsum[rt] = r-l+1; col[rt] = -1; if(l == r) return; mid; build(lson); build(rson); } void update(int L, int R, int v, int l, int r, int rt) { if(L <= l && r <= R ) { col[rt] = v; lsum[rt] = msum[rt] = rsum[rt] = v ? 0 : (r-l+1); return; } pushdown(rt, r-l+1); mid; if(L <= m) update(L, R, v, lson); if(R > m) update(L, R, v, rson); pushup(rt, r-l+1); } int query(int v, int l, int r, int rt) { if(l == r) return l; pushdown(rt, r-l+1); mid; if(msum[rt<<1] >= v) return query(v, lson); else if( rsum[rt<<1] + lsum[rt<<1|1] >= v) return m - rsum[rt<<1] + 1; else return query(v, rson); } int main() { int i, j; while( ~scanf("%d%d", &n, &m)) { int op, x, y; build(1, n, 1); while(m--) { scanf("%d%d", &op, &x); if(op == 1) { if(msum[1] < x) puts("0"); else { int k = query(x, 1, n, 1); printf("%d\n", k); update(k , k+x-1, 1, 1, n, 1); } } else { scanf("%d", &y); update(x, x+y-1, 0, 1, n, 1); } } } return 0; }

上一篇:xmlbeans使用
下一篇:codeforces div2 #152 小结

相关文章

相关评论