[SPOJ] 1043 Can you answer these queries I [GSS1]

Pro 

　　给你一个序列{A[1], A[2], ..., A[N]}.( |A[i]| ≤ 15007 , 1 ≤ N ≤ 50000 )      

　　给定“查询”操作的定义如下：          

　　　　Query(x,y) = Max { a[i]+a[i+1]+...+a[j] ; x ≤ i ≤ j ≤ y }.     

　　给出M个查询，你的程序需要输出这些查询的结果。

Input

     输入文件的第一行包含一个整数n，表示给出的数的个数；     

　　在第二行，给出N个数字，表示A[1]到A[n]；     

　　第三行包含整数M，表示询问的个数;     

　　接下来M行，每行包含两个数x和y.

Output

         你的程序应该输出M个查询的结果，每个查询结果占一行。

Sample Input

3    

-1 2 3   

1   

1 2

Sample Output

2

Solution

这是一道比较基础的线段树的练习题，即询问区间最大字段和， 我们可以用线段树维护4个值，

分别是当前区间从最左端开始的最大子段lmax， 从最右端开始的最大子段rmax，当前区间的最大子段和smax以及当前区间的和sum。

对于每一个询问，我们可以在自底向上（zkw）的过程中维护3个值，

分别是 当前左区间从最右端开始的最大子段lrans，当前有区间从最左端开始的最大子段rlans，

还有当前左区间和右区间中的最大子段和subans，最后在lrans + rlans和subans中取 最大值输出就可以了。

Source

#include 
#include 
const int nmax = 50000;int lmax[(1 << 17) + 18], rmax[(1 << 17) + 18], sum[(1 << 17) + 18], smax[(1 << 17) + 18];
int n, m, l, r, M = 1;
int i, lrans, rlans, subans;int max (int a, int b)
{return a > b ? a : b;
}int query (int l, int r)
{subans = lrans = rlans = -nmax;for (l += M - 1, r += M + 1; l ^ r ^ 1; l >>= 1, r >>= 1){if (~l & 1){subans = max (subans, max (smax[l ^ 1], lrans + lmax[l ^ 1]));lrans = max (rmax[l ^ 1], lrans + sum[l ^ 1]);}if ( r & 1){subans = max (subans, max (smax[r ^ 1], rlans + rmax[r ^ 1]));rlans = max (lmax[r ^ 1], rlans + sum[r ^ 1]);}}return max (subans, lrans + rlans);
}int main ()
{freopen ("GSS1.in", "r", stdin);freopen ("GSS1.out", "w", stdout);scanf ("%d", &n);memset (lmax, 0xEF, sizeof (lmax));memset (rmax, 0xEF, sizeof (rmax));memset (sum, 0xEF, sizeof (sum));memset (smax, 0xEF, sizeof (smax));while (M < n) M <<= 1;for (i = 1; i <= n; ++i)scanf ("%d", &lmax[i + M]), sum[i + M] = rmax[i + M] = smax[i + M] = lmax[i + M];for (i = M - 1; i; --i){lmax[i] = max (lmax[i << 1], sum[i << 1] + lmax[(i << 1) + 1]);rmax[i] = max (rmax[(i << 1) + 1], rmax[i << 1] + sum[(i << 1) + 1]);sum[i] = sum[i << 1] + sum[(i << 1) + 1];smax[i] = max (max (smax[i << 1], smax[(i << 1) + 1]), rmax[i << 1] + lmax[(i << 1) + 1]);}scanf ("%d", &m);for (i = 1; i <= m; ++i)scanf ("%d%d", &l, &r), printf ("%d\n", query (l, r));return 0;
}

转载于:https://www.cnblogs.com/Neroysq/archive/2011/05/24/2056019.html

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！