【BZOJ 3711】[PA2014] Druzyny

相关链接

题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=3711
神犇题解Ⅰ：http://www.cnblogs.com/clrs97/p/4654215.html
神犇题解Ⅱ：http://blog.csdn.net/u010600261/article/details/54917569

解题报告

去膜了题解，好神啊！
本题一个区间要同时受$c_i,d_i$的限制

于是我们先只考虑$d_i$的限制
那么对于某一个区间的右端点$i$来讲，设合法的左端点$\in [g_i,i)$
至于$g_i$怎么求？搞一个队列就可以了？或者二分也是可以的
另外还需要注意一点：$g_i$是单调递增的

现在我们再来考虑$c_i$的限制，我们使用分治来解决
在$solve(l,r)$的时候，我们找出$c_i$最大的那个点$k$，然后递归下去
在合并上来的时候，我们就只需要考虑$[l,k-1]$对于$[k,r]$的贡献了
更进一步：因为$c_k$是$[l,r]$中最大的那个，所以对于此时所有的转移，$c_i$的限制均只需要考虑$c_k$
那么此时对于$i \in [k,r]$来讲，其合法的左端点$j \in [max(l,g_i),min(k-1,i-c_k)]$
因为$g_i$单调递增，所以我们对于$[k,r]$从左到右分四段考虑：

1. $g_i \le l$且$i-c_k \le k-1$
   我们的首先我们肯定可以使用线段树来更新
   但更进一步，对于这一类点，我们只需要在查询第一个点时使用线段树就可以了
   因为这是一个前缀，之后$i$每向右移一位，合法的$j$也最多增加$1$
   不难发现，总的暴力操作次数不大于左右区间中较小的一段
   时间复杂度：$O(\log + \min(r-k+1,k-l))$
2. $g_i \le l$且$k-1 < i-c_k$
   对于这些点，我们查询的是整个左区间
   我们整体查一次，然后一起更新就可以了
   时间复杂度：$O(\log n)$
3. $l < g_i < k$
   对于这些点，我们查询的是左区间的一个后缀，我们直接在线段树上查就好
   考虑所有会影响到$i$的$solve$，它们的左区间一定没有交集
   也就是说只会有一个$solve$的左区间包含$g_i$
   于是对于每一个$i$，在整个算法中只会被查询一次
   所以这部分复杂度是$O(n \log n)$的，且不需要考虑到分治的复杂度中去
4. $g_i \le k$
   直接不管就好

现在我们来分析分治的复杂度：$T(a+b)=T(a)+T(b)+min(a,b)+\log n$
我们发现这和启发式合并一样，于是复杂度是$O(n \log n)$的
在算上第三类更新的复杂度，总时间复杂度仍然为$O(n \log n)$

值得一提的是，这种与最值相关的问题使用分治来解决已经多次出现
比如HDU 5575，一定要引起重视啊