比赛时候万人题，呵呵，没想到转换成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”
自己看看了半天都找不到规律，倒是感觉和逆序数应该有关系，但是直接按照偶序列有解奇序列无解来算wa，因为按照我原来的理解是，偶序列4个反转一定还是偶序列，奇序列4个反转也一定是奇序列。搜了题解之后发现漏掉了一个条件，那就是这个是个环，所以他从任意一个地方开始都可以，这就相当于在原来的4个翻转的变换的基础上多了一种变换：把后面的一段整个的移动到前面的一段。这个操作是如果按照一次简单变换来衡量的话，相当于做了i*j次变换，其中i是分界点前一段的个数，j是后一段的。当n为偶数的时候可以找到一个分界点分为两个奇数段，则相乘之后仍然是奇数，等于说这时候是可以从奇序列变成偶序列的；而当n为奇数的时候，i和j必定一奇一偶，这时候相乘必定为偶数，无法变换序列的奇偶性。所以，只有当序列为奇序列且n为奇数的时候才无解，其他情况均有解，因为均可以变换为偶序列。
扫描线第一题，求矩形面积的并。思路很好理解，但是实现上有很多的问题。
1 维护的变量ala[o]代表含义是“当前节点对应区间全覆盖的点数”，举个例子来说，现在的区间各个节点的值如果是2 3 3 3 5 5 2，那么ala就应该是2。这个变量这么做的好处就是，当ala不为0的时候一定可以直接把整个区间的Len算出来：就是x[r]-x[l]，当他为0的时候说明中间有的点为0，那么我们再考虑左右儿子Len之和。这个东西注意是不要pushdown的，如果pushdown了反而会使得问题变得复杂，因为如果你只是往里面+1也要pushdown的话，那等于原来的可以直接得到的Len现在反而要往下走才可以得到。那么不pushdown会不会出现重复加的情况？也不会，因为这个问题里所有的形状都是矩形，有一个上下边使得ala[o]+1，则一定有另外一个边使得他-1，而这中间的呢？因为肯定这一条线段都是还是属于计算范围的，所以也没有多加，一定是对的，这个特点很重要，今早赖床的时候想了下才明白其中的奥妙所在。。。。
引用一位dalao的话描述一下
这里的区间覆盖不需要打懒惰标记。为什么呢？因为很显然，每个下边都有与之对应的上边，它显然不会被比它的长度小的上边给清除。而如果有比它长的上边，也一定有和那个上边对应的下边还存在。所以用那个上边清除下边的时候，一定会先递归到那个更长的下边，还没有递归到它就停止递归了。所以每个上下边是一一对应的，无需下传标记等。
2 这个线段树不是[l,r]，而是[l,r)，因为我们这里离散化之后，如果按照闭区间来算，那[mid,mid+1]这一段就不能被计算到了，所以要用左闭右开，这样的话对应的一开始的区间右边要+1，而这样又会有问题就是原来的整个线段，也就是o==1时候的线段，以及所有的右侧端点为整个线段树右端点的线段，他们的右侧怎么处理，这可是个必须要左闭右闭的啊？我这里用的是在xs离散化数组的后面加上一个和xs[cnt1]相等的元素，这样就可以不用特殊判断了。
这个题也是看了一晚上，各种题解各种论文各种ppt emmmmmmm
话说发现真的线段树这东西不能看别人的代码，怎么看怎么看不懂，非得自己写一遍才是。感觉市面上常见的线段树也就两种写法，一种是pushdown以及在update预判返回的时候把维护子节点的事情做了，维护只维护当前节点所以又叫pushup，另一种是pushdown和预判都只改变标记，而所有的维护都交给maintain来做，(⊙﹏⊙)我一直写的是后一种，但是这里写前一种貌似比较方便（🌫）因为update在这里兼具了更新和搜索的功能，所以最好是在pushdown的时候就把维护子节点的事情做了。（感觉自己对pushdown标记的理解之前还是不到位啊emmmm还是得写）
继续阅读“[线段树][区间最值操作][论文题][难] HDU5306 Gorgeous Sequence”
比赛时候wa到哭，后来发现优化错了，把优化去掉玄学AC（这可是三个for啊这复杂度）
后来想一下，之所以能玄学过，就是因为题目保证了一定有解，如果无解的话那三个for还真有可能跑一遍，不说三个了两个跑一遍都够呛。。
我这里的玄学算法就是，对横纵坐标分别标记，当一个点在纵方向上被至少n-1个举行覆盖的时候才考虑这个横坐标，然后在这个横坐标上的所有纵坐标，也只有当被至少n-1个覆盖到的时候才考虑它，当然这只是必要条件而不是充分条件，然后对于一个要考虑的点遍历所有矩形（没错就是这么暴力）如果有超过1个没覆盖到这个点就退出直接不考虑。。。就这么超级暴力+剪枝，玄学过了cf的所有数据，emmm 继续阅读“[CF][区间标记方法][暴力] codeforces 1028C Rectangles”
连续做的又一道预处理+贪心的题目，一开始因为复杂度的原因一直没有下手，看了官方题解才意识到复杂度是nlogn，因为调和级数求和是logn。。。
贪心策略就是每次都选择能覆盖到的范围内的最右边的非block的点，如果这个点等于原来的出发点就直接return -1，因为说明不可行。这时候我们需要预处理出来每个点对应的它左边离他最近的那个非block的点（也有可能是他自己），当然这个预处理就很简单了。主要的思考难度在于没想到可以这么预处理，其次是复杂度的分析没有到位。
错误的点的话是对题意的理解：这里要求覆盖整条线段，而不仅仅是覆盖整点，但是放灯却只能在0到n-1的整点上放。。。第二个错误是如果0处禁止放的话那直接就是输出-1了，原来的算法在这里会失效，因为那个总是多考虑一步，而没有考虑出发点是不是合法的。
首先确定，什么时候是NO，因为把ai全部异或起来一定是整个矩阵全异或，bi同理所以这俩数字应该相等，xor为0，如果不为0一定是不存在的。所以，如果存在，那么a全部xor和b全部xor一定是相等的，记为tmp
否则的话，把b1到bm-1全放到第一行的左边m-1个空位，剩下的右边那个补上一个t使得这一行xor为a1，此时最右边一列的xor为tmp^a1^t=tmp^(b1^bi..^bm-1)==bm，所以这样构造的矩阵一定满足要求！！！
继续阅读“[XOR][思维][构造] codeforces 1016D Vasya And The Matrix”
还是找星星，但是数据量升高了，不能用n^3复杂度的算法了
这里可以用六个预处理的矩阵来表示信息，前四个分别为上下左右到当前位置的连续的星个数，这样就不用每次到一个坐标都从新求了。后两个分别为两个标记矩阵，这里的思想很像之前有个AC自动机替换禁忌词的题目，因为那个题目禁忌词可能互相冲突，互相交错，互相包含，而这个里面的不同的星星也会出现这种情况，所以采用了类似的方法：在左端点标记+1，右端点标记-1，然后再把矩阵从左往右过一遍，h[i][j]=h[i][j]+h[i][j-1]，这样的话，就可以确定出来一个点有没有被星星覆盖到：如果他的h或v大于0就被覆盖了，否则就没有。所有的矩阵预处理都是n^2的复杂度，总共6*n^2大概。
继续阅读“[思维][预处理][区间信息技巧] codeforces 1015E2 Stars Drawing (Hard Edition)”
都是泪啊啊啊啊啊啊啊啊啊啊啊啊啊
汪聚代哥一队打了79，v5的一批Ooooooorz 我们就很惨了，4题，300多名。。据说校前三可以去现场赛，然后我们第六凉凉。。
这个题真的是。。。真的是就差了那么一点，一层窗户纸，捅破就恍然大悟，过不去就死活想不出来了。我甚至也想到了官方题解中的类似于二分图的配置，可是没想到怎么去合并，不对，是我根本就没想合并。。。。。根本就没有意识到传递性啊啊啊啊啊啊啊啊惨的一批
最扯淡的是后面发现是原题。。。虽然有一点不一样，但是能理解原题的话就完全可以做这个了，啊啊啊啊啊啊啊啊啊啊啊啊啊啊
然后lyq差点把1005做出来，沙雕数论题，她会推公式不会实现，我会实现不懂公式，如果我们不是云操作的话可能就做出来了，在线交流真的难受。。。
还有就是1007，赛后看了一眼完全可做的样子，然而最后思维全死在这个A题。。。。决定去cf上刷一波进阶贪心了aaaaaaaa
继续阅读“[比赛][思维][贪心] CCPC网络赛 HDU6438 Buy and Resell”
