一个Y打成了X导致调了4h，视力为0，望周知

题目给的A>=0，我还以为拆了再建的美观值可以为0呢……
cdq分治大法好，伏地膜万古神犇cdq！

UUPD：又改写了一个二分的，也写错好久。。最后发现自己二分姿势一直是有bug的。。

UPD:又写了个复杂度正确的（nlog^2)，不过三分写挂了好久。。

好吧我承认我的第二问做法貌似是可以构造数据卡掉的，但是我没有成功，大体卡的方法是“构造出一种数据使得g[i]的值只有两个且g[i]==1的和g[i]==2的各有n/2个”，其中g[i]表示前i个房子保留第i最多保留多少个房子，但是在构造数据时发现似乎难以构造出这样的数据？我尝试构造前n/2单调减，后n/2单调减，但是后n/2都比前n/2大的，但是没能卡住，是我的姿势不对吗？求大神指点

第一问线段树，第二问玄学暴力水过= =

拆完再建的房子美观值也必须是正的（好像是废话）
不拆房子就得给房主赔偿金并且还要求尽量不拆房子是什么设定啊喂→_→
驼峰命名法就是看着舒服……（虽然一旦用上就表明这是一道丧心病狂的码农题233333333）
做法是斜率优化+线段树套凸包：在线段树每个节点处记录该段元素形成的凸包……然后会用到单点修改（将其压入路径上所有节点的凸包）和段询问（在它覆盖的每一个“完整段”处做一次凸包二分查询）
解题报告：http://blog.sina.com.cn/s/blog_c5566b0f0102v7mu.html