http://poj.org/problem?id=3667
有N个连续编号的房间的酒店，M次操作。包括x个人入住连续的房间，x开始的y个人登出。求每次入住房间的开始房号，不能入住则输出0.
http://www.java3z.com/cwbwebhome/article/article17/acm922.html
线段树，区间合并，区间替换，查询最左断点
Read full article from POJ - 3667 - Hotel - 芒果糕
The cows are journeying north to Thunder Bay in Canada to gain cultural enrichment and enjoy a vacation on the sunny shores of Lake Superior. Bessie, ever the competent travel agent, has named the Bullmoose Hotel on famed Cumberland Street as their vacation residence. This immense hotel has N (1 ≤ N ≤ 50,000) rooms all located on the same side of an extremely long hallway (all the better to see the lake, of course).
The cows and other visitors arrive in groups of size Di (1 ≤ Di ≤ N) and approach the front desk to check in. Each group i requests a set of Di contiguous rooms from Canmuu, the moose staffing the counter. He assigns them some set of consecutive room numbers r..r+Di-1 if they are available or, if no contiguous set of rooms is available, politely suggests alternate lodging. Canmuu always chooses the value of r to be the smallest possible.
Visitors also depart the hotel from groups of contiguous rooms. Checkout i has the parameters Xi and Di which specify the vacating of rooms Xi ..Xi +Di-1 (1 ≤ Xi ≤ N-Di+1). Some (or all) of those rooms might be empty before the checkout.
Your job is to assist Canmuu by processing M (1 ≤ M < 50,000) checkin/checkout requests. The hotel is initially unoccupied.
The cows and other visitors arrive in groups of size Di (1 ≤ Di ≤ N) and approach the front desk to check in. Each group i requests a set of Di contiguous rooms from Canmuu, the moose staffing the counter. He assigns them some set of consecutive room numbers r..r+Di-1 if they are available or, if no contiguous set of rooms is available, politely suggests alternate lodging. Canmuu always chooses the value of r to be the smallest possible.
Visitors also depart the hotel from groups of contiguous rooms. Checkout i has the parameters Xi and Di which specify the vacating of rooms Xi ..Xi +Di-1 (1 ≤ Xi ≤ N-Di+1). Some (or all) of those rooms might be empty before the checkout.
Your job is to assist Canmuu by processing M (1 ≤ M < 50,000) checkin/checkout requests. The hotel is initially unoccupied.
Input
* Line 1: Two space-separated integers: N and M
* Lines 2..M+1: Line i+1 contains request expressed as one of two possible formats: (a) Two space separated integers representing a check-in request: 1 and Di (b) Three space-separated integers representing a check-out: 2, Xi, and Di
* Lines 2..M+1: Line i+1 contains request expressed as one of two possible formats: (a) Two space separated integers representing a check-in request: 1 and Di (b) Three space-separated integers representing a check-out: 2, Xi, and Di
Output
* Lines 1.....: For each check-in request, output a single line with a single integer r, the first room in the contiguous sequence of rooms to be occupied. If the request cannot be satisfied, output 0.
Sample Input
10 6 1 3 1 3 1 3 1 3 2 5 5 1 6
Sample Output
1 4 7 0 5POJ - 3667 - Hotel - 芒果糕
有N个连续编号的房间的酒店，M次操作。包括x个人入住连续的房间，x开始的y个人登出。求每次入住房间的开始房号，不能入住则输出0.
比较复杂的线段树＋懒惰标记。根据题意，其实是求连续的01串中，最左侧的连续k个1的序列的位置。
需要维护3个参数，每个区间最长连续1序列的长度sum，左侧开始往右最长的1序列lsum，右侧开始往左最长的1序列rsum。
这样在PushUp时，首先继承左儿子的lsum和右儿子的rsum，然后判断左儿子的lsum是否覆盖左儿子整个区间，如果是则说明左儿子和右儿子是左相连的，lsum更新为左右儿子的lsum之和。其次判断右儿子的rsum是否覆盖右儿子整个区间，如果是则同理，rsum更新为左右儿子的rsum只和。最后，sum取左右儿子sum以及左儿子rsum和右儿子lsum之和的最大值。左儿子rsum和右儿子lsum之和即为左右区间合并点所在的最长1序列。
PushDown时，首先继承父亲的标记。如果标记为1入住，则儿子的所有序列长度更新为0，否则更新为对应区间长度。最后标记还原为－1.这里为了和登出的0区分开，用－1表示没有标记。
建立线段树时，序列长度默认为区间长度。
更新时，搜索到子集时，更新标记，并且序列长度根据标记更新为0或者区间长度。然后PushDown,PushUp。
查询时，优先查询左子树，其次查询左右区间连接部分，最后查询右子树。
最后，每次入住操作的查询后，如果可以入住，则需要更新对应区间为1状态。
http://www.acmerblog.com/POJ-3667-Hotel-blog-1124.html009 | class point |
010 | { |
011 | int l,r,max,cov; |
012 | } |
013 | public class Main{ |
014 | // static int MAX = 50010; |
015 |
016 |
017 | point p[]; |
018 | public Main(){ |
019 | p=new point[131070]; |
020 | for(int i=0;i< p.length;i++) |
021 | p[i]=new point(); |
022 | } |
023 | |
024 | void push_up(int l,int r,int rt) |
025 | { |
026 | p[rt].l = p[rt<<1].l; |
027 | p[rt].r = p[rt<<1|1].r; |
028 | int mid = r+l>>1; |
029 | if(p[rt].l==mid-l+1) p[rt].l+=p[rt<<1|1].l; |
030 | if(p[rt].r==r-mid) p[rt].r+=p[rt<<1].r; |
031 | p[rt].max =Math.max(Math.max(p[rt<<1].max,p[rt<<1|1].max),p[rt<<1].r+p[rt<<1|1].l); |
032 | } |
033 |
034 | void push_down(int l,int r,int rt) |
035 | { |
036 | if(p[rt].cov!=-1) |
037 | { |
038 | p[rt<<1].cov = p[rt<<1|1].cov = p[rt].cov; |
039 | if(p[rt].cov==1) |
040 | p[rt<<1].l = p[rt<<1|1].l = p[rt<<1].r = p[rt<<1|1].r = p[rt<<1].max = p[rt<<1|1].max = 0; |
041 | else |
042 | { |
043 | int mid = r+l>>1; |
044 | p[rt<<1].l = p[rt<<1].r = p[rt<<1].max = mid-l+1; |
045 | p[rt<<1|1].l = p[rt<<1|1].r = p[rt<<1|1].max = r-mid; |
046 | } |
047 | p[rt].cov = -1; |
048 | } |
049 | } |
050 |
051 | void build(int l,int r,int rt){ |
052 | p[rt].l = p[rt].r = p[rt].max = r-l+1; |
053 | p[rt].cov = -1; |
054 | if(l==r) |
055 | { |
056 | return; |
057 | } |
058 | int mid = r+l>>1; |
059 | build(l,mid,rt<<1); |
060 | build(mid+1,r,rt<<1|1); |
061 | } |
062 |
063 | //a==1,填满[L,R],a=0清空区间[L,R] |
064 | void update(int a,int L,int R,int l,int r,int rt) |
065 | { |
066 | if(L<=l&&R>=r) |
067 | { |
068 | if(a==1) |
069 | p[rt].l = p[rt].r = p[rt].max = 0; |
070 | else |
071 | p[rt].l = p[rt].r = p[rt].max = r-l+1; |
072 | p[rt].cov = a; |
073 | return; |
074 | } |
075 | int mid = r+l>>1; |
076 | push_down(l,r,rt); |
077 | if(L<=mid) update(a,L,R,l,mid,rt<<1); |
078 | if(R>mid) update(a,L,R,mid+1,r,rt<<1|1); |
079 | push_up(l,r,rt); |
080 | } |
081 | |
082 | int query(int a,int l,int r,int rt) |
083 | { |
084 | if(l==r) |
085 | { |
086 | return l; |
087 | } |
088 | int mid = r+l>>1; |
089 | push_down(l,r,rt); |
090 | if(p[rt<<1].max>=a) return query(a,l,mid,rt<<1); |
091 | if(p[rt<<1].r+p[rt<<1|1].l>=a) return mid-p[rt<<1].r+1; |
092 | return query(a,mid+1,r,rt<<1|1); |
093 | } |
094 |
095 | public int getMax(){ |
096 | return p[1].max; |
097 | } |
098 | public static void main(String args[]) throws IOException{ |
099 |
100 | StreamTokenizer st = new StreamTokenizer(new BufferedReader( |
101 | new InputStreamReader(System.in))); |
102 | PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out)); |
103 | |
104 |
105 | int n,m,k,x,y; |
106 | while(st.nextToken() != StreamTokenizer.TT_EOF) |
107 | { |
108 | |
109 | n= (int) st.nval; |
110 | st.nextToken(); |
111 | m= (int) st.nval; |
112 | Main ma=new Main(); |
113 | |
114 | ma.build(1,n,1); |
115 | while(m-->0) |
116 | { |
117 | st.nextToken(); |
118 | k=(int) st.nval; |
119 | if(k==1) |
120 | { |
121 | st.nextToken(); |
122 | x= (int) st.nval; |
123 | if(ma.getMax()< x) System.out.println("0"); |
124 | else |
125 | { |
126 | int tmp =ma.query(x,1,n,1); |
127 | System.out.printf("%d\n",tmp); |
128 | ma.update(1,tmp,tmp+x-1,1,n,1); |
129 | } |
130 | } |
131 | else |
132 | { |
133 | st.nextToken(); |
134 | x=(int) st.nval; |
135 | st.nextToken(); |
136 | y=(int) st.nval; |
137 | ma.update(0,x,x+y-1,1,n,1); |
138 | } |
139 | } |
140 | out.flush(); |
141 | } |
142 | } |
143 | } |
线段树，区间合并，区间替换，查询最左断点
Read full article from POJ - 3667 - Hotel - 芒果糕
