赛后过题，心塞。
这题搞明白以后就是一个暴力打SG表的过程，-1表示bad，0表示normal，1表示good，从最后一轮开始，分奇偶轮，如果是奇数轮也就是先手轮，那就尽可能往1，也就是往大了转移，如果是偶数轮，也就是后手轮，那就往小了转移。真的是服了，这么简单当时就是没想到，唉。
因为n只有1000，每次的状态也最多只有200，（妈的限制上下界不就是为了可以暴力打表或者暴搜吗。。这么明显的特征没看出来我也是呵呵）想到这儿的时候直接明白了，为什么比赛时候那么多人过还那么高的通过率，呵呵呵呵呵，当时脑子真是短路。心情复杂。思考。 继续阅读“[比赛][博弈论][SG表] 2018 ICPC徐州网络赛 B BE, GE or NE”
这次写了这个题目之后我发现之前对面积并的那个cal计数的意义还是理解还是有一点偏差：这个东西表示的是当前节点对应的线段整体覆盖的情况。为0时没有被全覆盖（注意不等于没有被覆盖），为1时被全覆盖了1次（意为min(l,r)==1，不代表不大于1)，为k时表示min(l,r)==k。而且对应的只是一个节点对应的整个线段，跟只表示当前整段线段的状况，儿子是什么样不知道。。。
这个题也貌似有很多种方法，我参考了一位前辈的博客之后用了Len1表示全覆盖次数≥1的长度，Len2表示全覆盖次数≥2的长度，当然全部都是针对当前节点。Len1的维护方法和面积并的方法完全一样。然后Len2维护的时候就是，如果cnt[o]大于等于2，那么说明当前节点被全覆盖了两次，直接Len2=Len1，如果为1，说明当前节点被全覆盖了一次，那么只需要加上子节点中被全覆盖了一次的Len1就可以了（这样相当于在双亲节点里覆盖了两次），如果是叶子节点，没有孩子，那就直接是0，如果cnt为0，那就只有孩子里面的被全覆盖了两次之和才能更新当前点了。
这里还有一个需要注意的是，如果cnt为0，那么要么说明，当前节点从来没有被计算过，要么说明只计算过子节点，所以不会出现错误。
继续阅读“[线段树][扫描线][面积交] HDU 1255”
从后往前，如果遇到下雨的天气就存进优先队列里，如果遇到不下雨的天气，优先解决离当前位置最近的湖，用vis记录一个湖是否有危险，如果遇到一个下雨天这个湖已经有危险了那么就输出NO，否则标记为有危险，如果是不下雨的天有则把有危险的（队列中的）前一个最大的湖去掉。到最后如果队列非空则也输出NO，说明有的湖的危险没有解决。
有趣的一道dp，让我想起了msc面试的时候问的扔杯子的问题。
首先，如果确定了对于长度为n的代码要写x个printf，那么这x个一定是尽量均匀分布（数学显然）才能使得最坏情况最好！因此，可以写出递推式：f(n)=min(f(ceil(1.0*n/i))+r+i*p);记忆化搜索暴力转移即可。
这个复杂度分析很数学：[n/i]的只有O(sqrt(n))种可能，每种可能的情况递归下去的话[n/ab]=[[n/a]/b],仍然是在那sqrt(n)种可能里面。所以总共有sqrt(n)个点会往下递归，每个递归点又最多有sqrt(n)次，相乘的话相当于O(n)； 继续阅读“[DP][复杂度分析] Gym – 101485D Debugging”
这个题当时tle到哭，心态爆炸，也几乎直接导致了没去看很简单的G，心情复杂。
这个判重刚好卡unordered_set，怎么都过不了，只能自己手写Hash判重。另外一个优化的点就是一定要边Manachar边计算，我一开始写的跑一遍Manacher之后枚举中点然后计算左右端点（那不就退化成n^2了嗯我当时就这么傻）。一边Manacher一边做，好处就是关于某个点对称的重复的回文串只会被算一次！这也是Manacher自身的算法决定的。。这个题其实出题人就是想让这么做的，不然要想计算所有出现的回文串的（不判重）MOD，应该是只能n^2吧。。（或许SAM可以？我没想过）。
需要巩固的地方：字符串Hash，字符串子串预处理（取模等），Manacher的原理的深刻理解。
继续阅读“[字符串][Manacher][Hash] 2018ICPC 南京网络赛 I Skr”
比赛时候万人题，呵呵，没想到转换成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]相等的元素，这样就可以不用特殊判断了。
