【Atcoder Grand Contest 011 F】Train Service Planning
题意：给\(n+1\)个站\(0,\dots,n\)，连续的两站\(i-1\)和\(i\)之间有一个距离\(A_i\)，其是单行（\(B_i=1\)）或双行（\(B_i=2\)），单行线不能同时有两辆方向不相同的车在上面，现在每\(k\)分钟发一次车（从\(0\)到\(n\)和从\(n\)到\(0\)），需要安排\(k\)分钟内的时间表，使得从\(0\)开到\(n\)的时间和从\(n\)开到\(0\)的时间和最小。
思路：主席树优化\(dp\)。
SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。这道题告诉我们要学好语文
首先避免在单行线上交叉的方式是在站台上停留一段时间。
假设我们从\(0\)到\(n\)的过程中停在第\(i\)个站台的时间是\(p_i\)，从\(n\)到\(0\)的过程中停在第\(i\)个站台的时间是\(q_i\)。
那么我们看在第\(s\)个段中它们的时间区间是怎样的。
\(0\dots n\)：\([\sum_{i=1}^{s-1} p_i+\sum_{i=1}^{s-1}A_i,\sum_{i=0}^{s-1}p_i+\sum_{i=1}^{s}A_i]\)
\(n\dots0\)：\([\sum_{i=s}^{n}q_i+\sum_{i=s+1}^nA_i,\sum_{i=s}^nq_i+\sum_{i=s}^nA_i]\)
题目要求的就是这两个区间在\(mod\ k\)意义下不相交。
但是这样的式子比较丑，没办法化简，
所以我们换一种方式表示\(n\dots0\)的时间区间。
既然是模意义下的，我们就假设它在\(0\)出发，“倒退”回\(n\)。
那么它的时间区间就是\([-\sum_{i=0}^{s-1}q_i-\sum_{i=1}^sA_i,-\sum_{i=0}^{s-1}q_i-\sum_{i=1}^{s-1}A_i]\)。
我们要求这两个区间不相交，就是第一个区间的两个端点都不在第二个区间内。
移项得\(\sum_{i=0}^{s-1}p_i+q_i\leq-2\sum_{i=1}^sA_i\)
或者\(\sum_{i=0}^{s-1}p_i+q_i\geq-2\sum_{i=1}^{s-1}A_i\)。
即\(\sum_{i=0}^{s-1}p_i+q_i\)不在\((-2\sum_{i=1}^sA_i,-2\sum_{i=1}^{s-1}A_i)\)内
即\(\sum_{i=0}^{s-1}p_i+q_i\)在\([-2\sum_{i=1}^{s-1}A_i,-2\sum_{i=1}^sA_i]\)内。
那么题目转化成了这样的东西：
一个人在数轴上走路，起初在任一点，只能向右，
要求某些整数时间点时他的位置在模\(k\)意义下属于区间\([L_i,R_i]\)，
问他最少走多少距离。
首先确定我们肯定只会走到端点上。
那么把所有端点离散化。
然后考虑一个很\(naive\)的\(dp\)。
设\(dp(i,j)\)表示现在在第\(i\)个段，
目前的位置\(mod\ k\)在第\(j\)个离散化后的端点处，走到第\(n\)段的最小代价。
那么转移的时候就从\(dp(i+1,*)\)转移来就好辣。
可惜这个方法只能过500分的点。
那我们换一种思路。
考虑\(dpL(i)\)和\(dpR(i)\)表示到了第\(i\)个段，
现在在\(L_i\)还是\(R_i\)，走到第\(n\)段的最小代价。
转移以\(dpL\)为例。我们看现在如果一直不走最多到哪里会不可行，假设这个点为\(j\)，
那么我们就从\(dpL(j)+L_j-L_i\)转移就好了。
但是求\(j\)的过程是\(O(n)\)的，肯定\(TLE\)。
那么就要看这个\(j\)的性质。然后发现并没有什么性质
所以我们用主席树维护每个新区间放下的时候每个点被覆盖了多少次。
但是主席树只能单点修改。所以果断差分。这样空间就得开的很大很大（我开了1e7。。。
如果在\(i\dots j\)的这段区间内所有新区间都覆盖\(L_i\)，那么自然是极好的。
直接二分\(j\)即可。复杂度\(O(n log(n)^2)\)。
再看怎么求答案。
首先我们还是从一个\(L_i\)（或\(R_i\)）开始，一直走走走到\(i\)，再加上\(dpL(i)\)即可。只是需要判断是否中间不能走了。
主席树真\(^{tm}\)难写。中间还出现了一些幺蛾子。。。
人生第一棵主席树祭
