upd：2020.12.3
题外话
本来这篇博客只有一道题的，今天拿给神仙zxp做
他说证明很难，我说不难
他让我两个手来证这道题目，我证不动
他啪的一下就给出了问题
一个情况，另一个情况，再一个情况
我都证了，全证出来了啊
这时候我收手不证了，按照规矩我已经证完了，他也承认我讲的不清楚
这笔就放在本子上，再证下去，我脑子就废了
他啪一下站起来："你还是没讲清楚"
我大意了啊，没有闪，两分钟后就自闭了
于是我们花了一个小时的时间，把证明搞了出来
前置问题
题意：
给定两个序列({a_1,a_2,cdots,a_n},{b_1,b_2,cdots ,b_m})，每个序列有个指针(it1,it2)，初始为(0)
目标为(it1=n,it2=m)
在每个时刻，需要满足(sumlimits_{i=1}^{it1}a_i+sumlimits_{i=1}^{it2}b_ige 0)
令(A_i=sumlimits_{k=1}^i a_k,B_i=sumlimits_{k=1}^i b_k)
那么需要保证(A_{it1}+B_{it2}ge 0)
弱化题目：假设(A_n)为序列({A_i})的最大值，(B_m)为序列({B_i})的最大值
我们每次：将(it1)往后移动到离其最近(i(it1<i))且满足(A_{i}>A_{it1})，或，将(it2)往后移动到离其最近(i(it2<i))且满足(B_i>B_{it2})
若不能移动显然无解
回到原题：你会发现这种方法只能移动到序列的最大位置
我们将两个序列倒过来，按同样的方法，若能走到最大值，则有解，否则无解
正确性显然
问题
给定一个长度为(n)的环序列({a_i})，从(1)出发，每次可以前往一个未到过的位置（但需保证其与到过的位置相邻）。
令(b_i)为前(i)次经过的位置(a_j)之和。
问(minlimits_{i=1}^n{b_i})最大可以是多少（(a_i)可以为负数）
(nle 10^5,|a_i|le 10^9)
做法
由于位置(1)是首先选的，我们令(a_1=0)，然后问题变成了每次从最左边或最右边选一个数，最大答案再加上(a_1)
定义：令(pre_i=sumlimits_{j=1}^i a_i)，(suf_{i}=sumlimits_{j=i}^n a_j)
二分答案(Ans)
令(mi_i)为从最左边选了(i)个数时，(minleft{j|存在方法从最右边选[j,n]
ight})
考虑从(mi_{i-1})转移到(mi_i)
- (a_ige 0)
初始化(mi_i=mi_{i-1})
不断左移(mi_i)，判断是否满足(pre_i+suf_xge Ans)（(x=mi_i)），若不满足则退出 - (a_i<0)
初始化(mi_i=mi_{i-1})
不断右移(mi_i)，判断是否满足(pre_i+suf_xge Ans)（(x=mi_i)），若满足则退出
证明：
对于(a_ige 0)正确性显然
对于(a_i<0)
按上面方法到达的位置是上界
考虑证明一定能通过某种方式到达此位置
在前置问题的基础上，将序列分割讨论，容易得出正确性
可以用线段树优化移动过程