[CF618F] Double Knapsack
遇到这种神秘问题我们肯定是想加强一下限制，不然直接做这咋做。
适当地猜一下结论。yhx-12243 指出，这类存在性问题肯定是根据抽屉原理搞一搞。
先猜一个结论：取出 \(a,b\) 的前缀和数组 \(A,B\)，答案一定是 \(a[l_1\sim r_1]\) 和 \(b[l_2\sim r_2]\)。即存在 \(l_1,r_1,l_2,r_2\) 满足 \(\sum\limits_{i=l_1}^{r_1}a_i=\sum\limits_{i=l_2}^{r_2} b_i\)。
怎么证明？考虑利用前缀和构造。条件即 \(A_r-A_l=B_v-B_u\)，盯不出来所以先换一下，\(A_r-B_v=A_l-B_u\)。考虑找到最大的 \(B_j\le A_i\) 的 \(j\)，一定有 \(0\le A_i-B_j<n\)，但是我们的 \(i\) 有 \(n+1\) 个啊，这样就构建了抽屉原理的模型。同时给出了一个构造方法，two-pointers 即可 \(\mathcal O(n)\) 算。
然后还有一点是，\(A_n>B_n\) 的话这个关系不对，交换一下 \(a,b\) 就行。