因为最近的生活太颓废总是不做题而被老师D了一番， 所以今天晚上到bzoj上去刷了几道水题。。。。。
维护一个支持两个操作的集合：
1） 插入一个数x
2） 询问集合中所有数中 mod x 最小是多少
似乎log家族没有什么好的办法解决这道题？
考虑 sqrt() 的方法。
当询问 x <= sqrt(m) 的时候， 直接存一下就可以了。
当询问 x > sqrt(m) 的时候，把n分成 n / x 块， 每一块单独考虑。
这时对于每一块， 我们需要求出的就是 >= (i * x) 的所有数中最小的那个。
填一个log会爆掉的。但是如果倒着处理， 每一次询问的就是 x 右面第一个没有被染色的点， 其实就是 疯狂的馒头 这道题， 用并查集搞一搞就可以了。
一个01串的价值定义为它的所有极长子只含1串的长度的立方的和。
尝试计算每一位对答案的贡献f(i)。 设li 为 i 前面的极长"1"串的长度
显然 f(i) = p[i] * (3 * li2 + 3 * li + 1)。
只要算出 li2 和 li 的期望， 就可以算出 f(i) 的期望了。
注意 li2 的期望并不等于 （li的期望）2 ， 要单独存一个数来转移。
虽然恶意缩了缩空格，，但代码真的本来就很短很漂亮。。
构造题。首先旋转一下令 n <= m，显然， 最后答案中覆盖的块一定都是 1 * x 的
其实整个问题的答案就是覆盖了障碍点的 上， 下， 左， 右 四个点的四个块的长度。
这时候情况数就很少了， 分类讨论一下就好了。
1）（障碍物）上面的点向上， 下面的点向下， 这时候剩下的点分两种情况： 1， 全部按照 (n + 1) / 2的方式竖着排列 2, 所有左边的点向左连， 右边的点向右连（其实第2种情况更优当且仅当是一个边长为奇数的正方形且障碍点在中间）
2）（障碍物）上面的点和下面的点都向 左边和右边中更近的那一边连 ， 这时候剩下的点（就是障碍物左边的所有点或者是右边的所有点）分两种情况： 1， 全部按照 (n + 1) / 2的方式竖着排列 2, 所有点都向左边/ 右边连。
好了， 其实一共只有四小类。
代码还是炒鸡短。。。
因为 300000 以内的数的因子个数最多也就140个， 所以这道题怎么搞一搞都可以。
然后就是一些基本数论知识也没什么好说的。
代码有点丑就不贴了（竟然比绝大多数代码都长简直不能忍！！！一定是我的算法太丑了QAQ）
原文：http://www.cnblogs.com/lixintong911/p/4934336.html
