P5892 [IOI2014] holiday 假期
题意
健佳正在制定下个假期去台湾的游玩计划。在这个假期，健佳将会在城市之间奔波，并且参观这些城市的景点。
在台湾共有 \(n\) 个城市，它们全部位于一条高速公路上。这些城市连续地编号为 \(0\) 到 \(n-1\)。
对于城市 \(i\)（\(0 < i < n-1\) ）而言，与其相邻的城市是 \(i-1\) 和 \(i+1\)。但是对于城市 \(0\)，唯一与其相邻的是城市 \(1\)。而对于城市 \(n-1\)，唯一与其相邻的是城市 \(n-2\)。
每个城市都有若干景点。健佳有 \(d\) 天假期并且打算要参观尽量多的景点。健佳已经选择了假期开始要到访的第一个城市。在假期的每一天，健佳可以选择去一个相邻的城市，或者参观所在城市的所有景点，但是不能同时进行。即使健佳在同一个城市停留多次，他也不会去重复参观该城市的景点。请帮助健佳策划这个假期，以便能让他参观尽可能多的景点。
题解
有趣的一道题，虽然考试的时候乱搞过了但是还是来补一下正解。
考虑起点为 \(0\) 的时候怎么做。
显然我们可以枚举一个 \(t\) 表示最右走到哪一个位置，则我们可以选择 \(s-t\) 个景点旅游，所以我们应该贪心地选前 \(s-t\) 大的景点趣旅游，可以直接用主席树去维护。
考虑起点为 \(s\) 时应该怎么做。
我们扩展上一种做法，向左走到 \(t_1\) ，向右走到 \(t_2\) ，容易发现我们只会往返一次，定方向之后翻转序列之后再做一遍就行了，我们假设是从右往左拐，则我们可以选择的景点个数为 \(d-2*(t_2-s)-(s-t_1)\) ，这时我们枚举 \(t_1,t_2\) ，再用主席树快速判断可以做到 \(O(n^2 logn)\) 。
考虑怎么优化这样一个东西，我们发现对于一个递减的 \(t_1\) 其对应的最优的 \(t_2\) 也是递减的，这个东西满足决策单调性。
可以用分治的的方法解决这个东西。
我们设 Solve(l,r,L,R)表示左端点在 \([l,r]\) ，最优右端点在 \([L,R]\)。
我们有这样一个东西，对于 \(mid=\frac{l+r}{2}\) 来说，有对应的最优右端点 \(pos\) ，则 \([l,mid-1]\) 对应的右端点都小于等于 \(pos\) ，\([mid+1,r]\) 对应的端点都大于等于 \(pos\)。
所以我们有Solve(l,r,L,R)->Solve(l,mid,L,pos)+Solve(mid+1,r,pos,R)
每层时间复杂度 \(O(n)\) ，总共有 \(logn\) 层，算上主席树的时间复杂度，总时间复杂度 \(O(nlognlogn)\)。code