记录编号	38445	评测结果	AAAAAAAA
题目名称	山海经	最终得分	100
用户昵称	王者自由	是否通过	通过
代码语言	C++	运行时间	0.666 s
提交时间	2012-04-18 22:08:17	内存使用	10.60 MiB

#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 100000 + 10;
struct node {
    int l, r, x;
    int sr, sl, sx;
    int lj, ri, xi, xj;
} f[3*N];
int n, m, l, r, s[N];
inline void Update(int i) {
    int j = 2*i;
    int a = f[j].x + f[j+1].sl;
    f[i].sl = f[j].sl, f[i].lj = f[j].lj;
    if(a > f[j].sl)
        f[i].sl = a, f[i].lj = f[j+1].lj;
    int b = f[j+1].x + f[j].sr;
    f[i].sr = f[j+1].sr, f[i].ri = f[j+1].ri;
    if(b >= f[j+1].sr)
        f[i].sr = b, f[i].ri = f[j].ri;
    a = f[j].sr + f[j+1].sl;
    f[i].sx = f[j].sx, f[i].xi = f[j].xi, f[i].xj = f[j].xj;
    if(a >= f[j].sx) {
        f[i].sx = a, f[i].xi = f[j].ri, f[i].xj = f[j+1].lj;
        if(a == f[j].sx && f[j].xi <= f[j].ri)
            f[i].sx = f[j].sx, f[i].xi = f[j].xi, f[i].xj = f[j].xj;
    }
    if(f[j+1].sx > f[i].sx)
        f[i].sx = f[j+1].sx, f[i].xi = f[j+1].xi, f[i].xj = f[j+1].xj;
}
inline node Union(const node &l, const node &r) {
    node k;
    int a = l.sr + r.sl;
    k.sx = l.sx, k.xi = l.xi, k.xj = l.xj;
    if(a >= l.sx) {
        k.sx = a, k.xi = l.ri, k.xj = r.lj;
        if(a == l.sx && l.xi <= l.ri)
            k.sx = l.sx, k.xi = l.xi, k.xj = l.xj;
    }
    if(r.sx > k.sx)
        k.sx = r.sx, k.xi = r.xi, k.xj = r.xj;
    a = l.x + r.sl;
    k.sl = l.sl, k.lj = l.lj;
    if(a > l.sl)
        k.sl = a, k.lj = r.lj;
    int b = r.x + l.sr;
    k.sr = r.sr, k.ri = r.ri;
    if(b >= r.sr)
        k.sr = b, k.ri = l.ri;
    return k;
}
void Build(int i, int l, int r) {
    f[i].l = l, f[i].r = r;
    if(l == r) {
        f[i].lj = f[i].ri = f[i].xi = f[i].xj = l;
        f[i].sl = f[i].sr = f[i].sx = f[i].x = s[l];
    } else {
        int j = 2*i, e = (l + r) / 2;
        Build(j, l, e);
        Build(j+1, e+1, r);
        f[i].x = f[j].x + f[j+1].x;
        Update(i);
    }
}
inline node Query(int i, int l, int r) {
    if(f[i].l == l && f[i].r == r)
        return f[i];
    int j = 2*i;
    int e = f[j].r;
    if(r <= e)
        return Query(j, l, r);
    else if(l > e)
        return Query(j+1, l, r);
    return Union(Query(j, l, e), Query(j+1, e+1, r));
}
int main() {
    freopen("hill.in", "r", stdin);
    freopen("hill.out", "w", stdout);
    scanf("%d %d", &n, &m);
    for(int i=1; i<=n; i++)
        scanf("%d", s+i);
    Build(1, 1, n);
    for(int i=0; i<m; i++) {
        scanf("%d %d", &l, &r);
        node k = Query(1, l, r);
        printf("%d %d %d\n", k.xi, k.xj, k.sx);
    }
    return 0;
}