比赛时候万人题，呵呵，没想到转换成histogram来做。貌似转化之后暴力都可以，n*m^2，气哭aaaaaaaaaaaaaaaaaaa
然后自己写了单调栈n*m做法，需要注意的是要同时保存一段height的左端点和右端点，因为要求数量的话，用单调栈只保存一个的话会忽略掉中间的“高点”，只保存一个端点就无法正确计算了。。。emm，代码写得时候脑子也很乱，还是需要多写写单调数据结构的题目。
继续阅读“[比赛][单调栈][histogram] 2018ICPC 南京网络赛 B The writing on the wall 求柱状图中有多少个矩形”
这题真的好鸡儿简单。。。差不多是除了第一题之外最简单的了。比赛的时候没看这个，iSika说很难就没做，唉
题意：给n个房间，当还有房间的灯没有被换成节能灯的时候每个月开始会买入m个节能灯，然后从左向右在列表中找小于m的房间换掉，如果当月的节能灯没有用完的话可以留给下个月。然后给q个询问问d第几个月结束的时候有多少个房间被换成了节能灯，以及手里剩下了多少节能灯。
解法：用value表示当前总共有多少个节能灯，把q个询问都读进来排序后从小到大操作（就是从第一个月开始模拟）。每次都找列表中<=value的最左边的值，找的方法是用线段树维护区间minv 信息，如果左子树minv<=value的话就向左走否则向右，如果小于minv[1]就不找，直接把当月的算出来。找到的话，令找到的房间的计数器+1，value-=找到的值，然后更新线段树这个点的minv为INF就行了。由于每个节点最多被修改一次，修改一次的代价为logn，所以总共的代价为qlogn，case closed！ 继续阅读“[比赛][线段树][模拟] 2018南京网络赛 G Lpl and Energy-saving Lamps”
