P7514
yzc2005
·
·
题解
提供一个线性做法（p.s. 不保证不 fst，即不保证正确性（
容易发现翻转的一定是一个前缀加一个后缀，而且在前缀中如果存在 a_i>b_i 或在后缀中存在 a_i<b_i 则一定不优。
于是假设前缀翻转到了 i，后缀翻转到了 j。特判 m=n 的情况，则答案就是
\max\{a_{j-1},\max(b_1,b_2,\cdots,b_i),\max(b_j,b_{j+1},\cdots,b_n)\}-\min\{a_{i+1},\min(b_1,b_2,\cdots,b_i),\min(b_{j},b_{j+1},\cdots,b_n)\}
不妨令
l_i=\min\{a_{i+1},\min(b_1,b_2,\cdots,b_i)\}
r_i=\max(b_1,b_2,\cdots,b_i)
l'_i=\min(b_j,b_{j+1},\cdots,b_n)\ (j=n-i+1)
r'_i=\max\{a_{j-1},,\max(b_j,b_{j+1},\cdots,b_n)\}\ (j=n-i+1)
则问题可以转化成求出
\min\{\max(r_i,r'_j)-\min(l_i,l_j')\ |\ i+j\le m\}
注意到 r 单调不减，因此对于某个 i，如果存在 j<i 使得 l_j>l_i，则选 j 一定比选 i 优。因此我们可以只取 l 的前缀最大值，使得 l 也单调不减。
同理可以得到 l',r' 单调不增。
不妨从小到大枚举 [l_i,r_i]。注意到很强的单调性，除去两区间形成包含关系的情况，一定是取最大的 r'_j\le r_i 或者最小的 l'_j\ge l_i，注意到这些端点也都是单调的，因此可以用指针扫。区间包含的情况可以再处理一遍 l',r' 解决。