※ 以下都是我自己著墨出來的，不保證正確
※ 以下 r+ 指的是比 r 大的數
爬行法是一種利用 （解在數列上的）單調性 來進行枚舉區間時的優化，我們一般枚舉區間寫成：
for (int l = 0; l < N; l++):
for (int r = l; r < N; r++):
...
可以想成：
我們枚舉區間的左端點，當左端點固定在 l 時，將右端點從 l 開始向右移動（r++）來找此時的最佳解。
(1) 如果區間 [l, r] 不是左端點為 l 時的最佳解，那因為單調性，我們只需向右移動右端點，直到找到此時的最佳解為止
(2) 如果已知 [l, r] 是左端點為 l 時的最佳解，那 [l, r+] 不可能是答案了，
(3) 所以我們就可以枚舉下一個左端點，左端點變成 l+1。
(4) 此時會有兩種情況，
(4.1) 一種情況是 [l+1, r] （尚）不是左端點為 l+1 時的最佳解，那這就回到 (1) 了
(4.2) 另一種情況是 [l+1, r] 已經是左端點為 l+1 時的最佳解，那這就回到 (2)
前提是 (1), (2)，只要符合 (1), (2)，應該都可以應用爬行法。
以 poj 3061 為例：
單調性是指 sum([l, r]) >= sum([l+1, r])
(1) 如果 sum([l, r]) < S，因單調性，所以移動右端點，直到 sum >= S
(2) 如果 sum([l, r]) >= S，根據題意，則 [l, r+] 不會是答案，因 ((r+) - l + 1) > (r - l + 1)
這題只能說太扯了…誰想得到啊
這題給的數列有正有負，要解這題得利用前綴和 + 排序 + 爬行法
struct P {
int sum;
int postion;
};
P prefix[i] = P(A[0] + A[1] + ... + A[i], i)
S[] = sort(P[])
於是，這題從找一個區間，區間和的絕對值越接近 T 越好，
變成在 前綴和由小排到大 的前綴和數列中，
找出兩項（S[i], S[j], i ≠ j），他們差的絕對值越接近 T 越好，這可以用爬行法。
之後我們再看看 S[i], S[j] 是對應到原陣列中的哪個區間，P.position 就在記錄這個
至於爬行法的實作，這裡給出一種寫法，另一種跟書上類似的寫法可參這
#include <iostream>
#include <algorithm>
#include <queue>
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;
typedef pair<int, int> pii;
const int INF = 0x3f3f3f3f;
int N, K;
int data[100000 + 1];
pii S[100000 + 1];
int T;
int ans_start = -1, ans_end = -1, ans_sum = 0;
void solve() {
int l = 0, r = 1;
int min_diff = INF, sum = 0;
while (r <= N) {
sum = abs(S[r].first - S[l].first);
// printf("%d(%d, %d)\n", sum, l, r);
// update
if (abs(sum - T) < min_diff) {
min_diff = abs(sum - T);
ans_sum = sum;
// 還原在原數列中對應的區間
ans_start = min(S[l].second, S[r].second) + 1;
ans_end = max(S[l].second, S[r].second);
}
// move
if (sum < T || l == r - 1) // 防止使用同一項(發生在範測 4)
r++;
else
l++;
}
}
int main() {
while (scanf("%d %d", &N, &K)) {
if (N == 0 && K == 0) break;
for (int i = 1; i <= N; i++)
scanf("%d", &data[i]);
S[0] = pii(0, 0); // 補零，方便之後區間的計算，觀察看看範測 4
for (int i = 1; i <= N; i++) {
S[i].first = S[i-1].first + data[i];
S[i].second = i;
}
sort(S, S + N + 1);
while (K--) {
scanf("%d", &T);
solve();
printf("%d %d %d\n", ans_sum, ans_start, ans_end);
}
}
return 0;
}