分类： CF

题目：http://codeforces.com/problemset/problem/1030/F

这个题最主要的是自己没有想出来怎么求出那个“不动的点”，因为其实整体的cost用k去表示出来是很困难的，求出来也无法发现其极值点。但是如果考虑差分就会比较好做，很容易发现当当前设的k点变成k+1时，cost变化了(S(l,k)-S(k+1,r))*(p[k+1]-p[k])，其中S(l,r)=Σw[i](l<=i<=r)。这样的话很明显当且仅当S(l,k)≤S(k+1,r)S(l,k)≤S(k+1,r)时k+1比k更优。所以我们只要找到最小的k使得S(l,k)>=S(l,r)/2就行了！

然后是对于一个[l,r]对求出k之后，如何快速的求出其cost。

对于i∈(l,k)i∈(l,k) 代价是∑(pk−pi−(k−i))∗wi（l<=i<=k)
对于i∈(k,r)i∈(k,r) 代价是∑(pi−pl−(i−k))∗wi（k<=i<=r)

把pi-i看成一个整体，记为ai，就可以得到cost=∑(ak−ai)∗wi(l<=i<=k)+∑(ai−al)∗wi(k<=i<=r)

展开整理就可以得到cost=ak*(S(l,k)-S(k,r))-(Σwi*ai(l<=i<=k)-Σwi*ai(k<=i<=r))。这样的话用一个BIT快速求S(l,r)，另一个BIT快速求Σwi*ai就可以了。

wa点的话，发现了一个以前没有注意到的bug，那就是我每次判断都是if(x>mod)x%=mod;但是忽然意识到在有减法的运算中，还有一种下越界的可能性，所以应该是if(x>mod||x<-mod)x%=mod; 继续阅读“[BIT][思维][反证][差分求极值] codeforces1030F Putting Boxes Together”

比赛时候wa到哭，后来发现优化错了，把优化去掉玄学AC（这可是三个for啊这复杂度）

后来想一下，之所以能玄学过，就是因为题目保证了一定有解，如果无解的话那三个for还真有可能跑一遍，不说三个了两个跑一遍都够呛。。

我这里的玄学算法就是，对横纵坐标分别标记，当一个点在纵方向上被至少n-1个举行覆盖的时候才考虑这个横坐标，然后在这个横坐标上的所有纵坐标，也只有当被至少n-1个覆盖到的时候才考虑它，当然这只是必要条件而不是充分条件，然后对于一个要考虑的点遍历所有矩形（没错就是这么暴力）如果有超过1个没覆盖到这个点就退出直接不考虑。。。就这么超级暴力+剪枝，玄学过了cf的所有数据，emmm 继续阅读“[CF][区间标记方法][暴力] codeforces 1028C Rectangles”