哈哈，原来题意看错了，但有多个解的时候，输出起点靠前的，如果起点一样，则输出终点靠前的，修改后AC的代码如下：
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std; const int MAXN = ; typedef long long int64; int dish[MAXN];
int64 dish_sum[MAXN]; int64 get_sum(int L, int R) {
return dish_sum[R] - dish_sum[L - ];
} class SegNode {
public:
int L, R;
int L_end, R_beg;
int beg, end;
int64 LR_sum() { return get_sum(L, R); }
int64 L_sum() { return get_sum(L, L_end); }
int64 R_sum() { return get_sum(R_beg, R); }
int64 sum() { return get_sum(beg, end); }
void log() {
printf("[%d %d]: (%d %d), (%d %d), (%d %d).\n",
L, R, L, L_end, R_beg, R, beg, end);
}
} node[ * MAXN]; class SegTree {
public:
void build(int r, int L, int R) {
node[r].L = L;
node[r].R = R;
if (L == R) {
// leaf
node[r].L_end = R;
node[r].R_beg = L;
node[r].beg = L;
node[r].end = R;
} else {
// non leaf
int M = (L + R) / ;
build( * r, L, M);
build( * r + , M + , R); // left
node[r].L_end = node[ * r].L_end;
if (node[ * r].LR_sum() + node[ * r + ].L_sum() > node[ * r].L_sum()) {
node[r].L_end = node[ * r + ].L_end;
} // right
node[r].R_beg = node[ * r + ].R_beg;
if (node[ * r + ].LR_sum() + node[ * r].R_sum() >= node[ * r + ].R_sum()) {
node[r].R_beg = node[ * r].R_beg;
} // mid
if (node[ * r].sum() >= node[ * r + ].sum()) {
node[r].beg = node[ * r].beg;
node[r].end = node[ * r].end;
} else {
node[r].beg = node[ * r + ].beg;
node[r].end = node[ * r + ].end;
}
if (node[ * r].R_sum() + node[ * r + ].L_sum() > node[r].sum() ||
(node[ * r].R_sum() + node[ * r + ].L_sum() == node[r].sum() && node[ * r].R_beg < node[r].beg)) {
node[r].beg = node[ * r].R_beg;
node[r].end = node[ * r + ].L_end;
}
}
//node[r].log();
}
void query(int r, int L, int R, int& left, int& right, int k) {
if (L <= node[r].L && node[r].R <= R) {
if (k == ) { left = node[r].L; right = node[r].L_end; }
else if (k == ) { left = node[r].R_beg; right = node[r].R; }
else { left = node[r].beg; right = node[r].end; }
} else {
if (R <= node[ * r].R) {
query( * r, L, R, left, right, k);
} else if (L >= node[ * r + ].L) {
query( * r + , L, R, left, right, k);
} else {
int left_beg, left_end, right_beg, right_end;
query( * r, L, R, left_beg, left_end, k);
query( * r + , L, R, right_beg, right_end, k);
if (k == ) {
left = left_beg;
right = left_end;
if (get_sum(left_beg, right_end) > get_sum(left, right)) {
left = left_beg;
right = right_end;
}
} else if (k == ) {
left = right_beg;
right = right_end;
if (get_sum(left_beg, right_end) >= get_sum(left, right)) {
left = left_beg;
right = right_end;
}
} else {
if (get_sum(left_beg, left_end) >= get_sum(right_beg, right_end)) {
left = left_beg;
right = left_end;
} else {
left = right_beg;
right = right_end;
}
int m_l, m_r, x;
query( * r, L, R, m_l, x, );
query( * r + , L, R, x, m_r, );
if (get_sum(m_l, m_r) > get_sum(left, right) ||
(get_sum(m_l, m_r) == get_sum(left, right) && m_l < left)) {
left = m_l;
right = m_r;
}
}
}
}
}
} tree; int main() {
int n, m, c = ;
while (scanf("%d%d", &n, &m) != EOF) {
dish_sum[] = ;
for (int i = ; i <= n; i++) {
scanf("%d", &dish[i]);
dish_sum[i] = dish_sum[i - ] + dish[i];
}
tree.build(, , n);
printf("Case %d:\n", ++c);
for (int i = ; i < m; i++) {
int l, r, left, right;
scanf("%d%d", &l, &r);
if (l > r) swap(l, r);
l = max(, l);
r = min(n, r);
tree.query(, l, r, left, right, );
printf("%d %d\n", left, right);
}
}
}