昨晚肝这一场是真的赔了，傻不拉几的C低级失误wa了一发，出完发现大家都会F然后跑去看了20min没头绪，折回去搞这个D，到最后也没过。。。感觉复杂度没错却一直tle，一直弄到两点受不了了睡觉去了，今早上课困得一批。
下午睡醒之后一直tle on test 27，给跪了好吧，疯狂卡常数真的有意思？最后把multiset改成priority_queue过了，真的服了，到目前为止52组数据吧，最狠的一组达到了2979ms，差21ms超时呵呵呵呵呵呵。。。
继续阅读“[CF][二分check][贪心][×] codeforces 1132D Stressful Training”
http://codeforces.com/contest/1061/problem/D
嗯。。。又是这种一维的区间最优化策略问题了。。。似乎已经感觉到了套路。。。（赛场上贪心有感觉就直接上了
这种题一般是先排序（以左端点或者右端点）搞出来一个顺序，然后在这个顺序的基础上逐个考虑。考察到某一段时候一般需要做决策，然后这时候可以根据具体题目来看是贪心决策还是dp，如果直觉是贪心（毕竟真正证明有时候确实不好弄），那一般决策都跟满足条件的极端值有关，比如在这里就是如果存在能合并的点（如果连最基本的两段合并后小于各买一台电视机都不满足那一定不能合并），那么一定是和这段左边最靠近他的一个点合并。具体证明可以分情况讨论，一般真的证明的时候就是得考虑，如果不这么合并，计算出来的结果和原来的结果对比，一般要考虑之后的seg的影响，在考虑的时候可以分情况讨论（反正我一般有直觉就上233
然后在实现的时候，有时候没有头绪可以想想STL！（想起了ccpc网络赛被set支配的恐惧），这个东西有时候真的有妙用，它既保持了单调的性质（可以用来贪心）又有着动态维护的特性（贪心的动态调整）。
wa点又是精度，嗯万年精度，这次竟然LL也炸了，而且是因为add的两个参数本身可以达到LL，然后一加给爆了。。。。我去
比赛结束智商上线系列
昨天的时候看C没整明白然后来看D，没想出来构造方法又回去卡C结果最后都没出呵呵呵，今早起来写了几个样例，组合了下就发现了规律：每次找到left最大的那个人和right最大的那个人，如果不是同一个人就合并中间left和right重合部分，ans加上这一部分（ans+=max(maxleft,maxright)）然后把这俩人重合的部分消去合并成一个新人放回集合里；如果是同一个人那就自己一个人一个圈子就好了。
感性理解的话就是要尽可能的让长的段之间有重复，重复就可以节省椅子，而始终都找最长的left和right就能保证这一要求。
wa点：multiset中如果两个元素它们定义<运算符的那个信息相同他就认为是相同的，而erase的时候会把所有相同的都erase掉，所以为了区别不同的人加上了一个id。。。很神奇吧。。
http://codeforces.com/contest/1042/problem/D
嗯，大概是发现了自己以前一直没有正确理解mergesort。。。。
vp时候发现一开始这个题目过的人竟然比C多然后就提前去看了，但是竟然并没想出来正解emmmmmm，想过分治但是不知道怎么在线性合并左右段，看了前排dalao代码恍然大悟，其实就是逆序数的推广，这里把前缀和当成要处理的对象即可，如果是逆序数的话就是输出来一个数字右边有多少个比他大的，这里的话是sum[i]的右边有多少个比sum[i]+t小的，而t是常数所以其实几乎和逆序数一样。。如果仔细考虑逆序数的分治算法的话，会发现他能保证合并的时候线性是因为每次左右两边都是排好序的，这样的话就可以线性合并，而为什么排序这个操作不会影响到结果呢？因为在合并的时候左右两边各自的结果已经被计算过了，需要计算的仅仅是跨越中点的那些lr对！而这些计算和左右两边各自的顺序没有关系，只要保证左边的在左边右边的在右边就行了：因为我们是计算合法的数量，只要存在就+1，跟他什么时候存在早存在晚存在没关系。 继续阅读“[分治][mergesort][经典算法推广][实现] Codeforces Round #510 div2 D Petya and Array”
收获：
1 我以前一直疑惑set能不能边遍历边erase，现在看来是可以的，erase(it++)就可以
2 二维转一维的思想，经常使用。
