UVA-1400 Ray,Pass me the Dishes,LA 3938,セグメントツリー,区間クエリー

題意:一列数(n個)、m次クエリ区間[l,r]の最大連続区間[x,y](l<=x<=y<=r)を与える.(n,m<=500 000)
構想:ダイナミッククエリー区間最大連続区間;
最大連続区間とを求める場合:
セグメントツリーで最大連続とsum_を維持するsub、最大接頭辞、sum_prefix、最大接尾辞、sum_suffix.
root.sum_sub = max{l.sum_sub, r.sum_sub, (l.sum_suffix + r.sum_prefix) };
タイトル要求区間、類似:
最大連続区間max_を線分ツリーで維持するsub、最大接頭辞右端max_prefix、最大接尾辞左端max_suffix.
詳細は、コードを参照してください.

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

#define lc rt<<1
#define rc rt<<1|1

const int maxn = 500000 + 5;
typedef long long LL;
LL num[maxn], max_prefix[maxn<<2], max_suffix[maxn<<2];

struct node{
    int l, r;
    node(int ll=0, int rr=0):l(ll),r(rr){}
} max_sub[maxn<<2];

LL prefix_sum[maxn];
int  ql, qr;

LL sum(int l, int r){
    return prefix_sum[r] - prefix_sum[l-1];
}
LL sum(node a){
    return sum(a.l, a.r);
}
node better(node a, node b){
    if(sum(a) != sum(b)) return sum(a) > sum(b) ? a:b;
    return (a.l<b.l||(a.l==b.l&&a.r<b.r))? a:b;
}
void build(int rt, int l, int r){
    if(l==r){
        max_prefix[rt] = max_suffix[rt] = l;
        max_sub[rt] = node(l,l);
        return ;
    }

    int m = (l+r)>>1;
    build(lc, l, m);
    build(rc, m+1, r);
    LL v1 = sum(l, max_prefix[lc]);
    LL v2 = sum(l, max_prefix[rc]);
    if(v1 == v2) max_prefix[rt] = min(max_prefix[lc], max_prefix[rc]);
    else max_prefix[rt] = v1 > v2 ? max_prefix[lc] : max_prefix[rc];
    v1 = sum(max_suffix[lc], r);
    v2 = sum(max_suffix[rc], r);
    if(v1 == v2) max_suffix[rt] = min(max_suffix[lc], max_suffix[rc]);
    else max_suffix[rt] = v1 > v2 ? max_suffix[lc] : max_suffix[rc];
    max_sub[rt] = better(max_sub[lc], max_sub[rc]);
    max_sub[rt] = better(max_sub[rt], node(max_suffix[lc], max_prefix[rc]));
}

int query_prefix(int rt, int l, int r){
    if(qr >= max_prefix[rt]) return max_prefix[rt];
    int m = (l+r)>>1;
    //l<=qr<=m
    if(qr <= m) return query_prefix(lc, l, m);
    //m+1<=qr<=r
    int rr = query_prefix(rc, m+1, r);
    node ret = better(node(l,rr), node(l, max_prefix[lc]));
    return ret.r;
}

int query_suffix(int rt, int l, int r){
    if(ql <= max_suffix[rt]) return max_suffix[rt];
    int m = (l+r)>>1;
    //m+1<=ql<=r
    if(ql > m) return query_suffix(rc, m+1, r);
    //l<=ql<=m
    int ll = query_suffix(lc, l, m);
    node ret = better(node(ll, r), node(max_suffix[rc], r));
    return ret.l;
}

node query(int rt, int l, int r){
    if(ql <= l && r <= qr) return max_sub[rt];
    int m = (l+r)>>1;

    if(qr <= m) return query(lc, l, m);

    if(ql >  m) return query(rc, m+1, r);

    //ql <= m <= qr
    int ll = query_suffix(lc, l, m);  //l_max_suffix
    int rr = query_prefix(rc, m+1, r); //r_max_prefix
    node mid = node(ll, rr);
    node sub = better( query(lc, l, m), query(rc, m+1, r));
    return better( mid, sub);
}
int main()
{
    int n, m, i, cas = 1, l, r;
    while(~scanf("%d%d", &n, &m)){
        printf("Case %d:
", cas++);
        prefix_sum[0] = 0;
        for(i=1; i<=n; ++i) {
                scanf("%lld", &num[i]);
                prefix_sum[i] = prefix_sum[i-1] + num[i];
        }
        node v = node(1,3);
        build(1, 1, n);
        while(m--){
            scanf("%d%d", &l, &r);
            ql = l; qr = r;
            node ans = query(1, 1, n);
            printf("%d %d
", ans.l, ans.r);
        }
    }
    return 0;
}