题意：给出一列数（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 
  
   
#include 
   
     #include 
    
      #include 
     
       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
      
       >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:\n", 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\n", ans.l, ans.r); } } return 0; }