哈理工OJ1684——最大连续和

给出一段序列，要求任意区间内最大连续和所在的区间，首先肯定是要用线段树去解决，并不是要求直接输出和，这样一来就要麻烦一点，如果不要求输出下标，那么一段区间的最大连续和可能来自三部分，左半部分的最大连续和，右半部分的最大连续和，左半部分从最右端开始的和的最大值和右半部分从最左端开始的和的最大值的和，所以，需要每个节点需要记录本节点的最大连续和，左端开始的最大连续和，右端开始的最大连续和，而要得到父节点的左端开始的最大连续和，还需要子节点整个区间的和，所以还要记录节点整个区间的和，现在要求输出下标，那么就要记录每一个和的起始位置，在合并选择的时候就可以直接得到了，所以一个节点需要记录10项，合并的时候还要注意题目要求必须保证多解时选x较小的，再有多解时选y较小的，所以要注意合并的顺序：

View Code

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 using namespace std;
  5 #define N 500005
  6 #define INF 0x80000001
  7 #define L(x) x<<1
  8 #define R(x) x<<1|1
  9 #define max(a,b) ((a)>(b)?(a):(b))
 10 #define min(a,b) ((a)<(b)?(a):(b))
 11 int val[N];
 12 int all[N];
 13 struct node
 14 {
 15     int l,r;
 16     int lval,rval;//左侧开始和最大值，rval类似
 17     int lid,rid;//左侧开始最大和值所对应下标
 18     int x,y;//最大子段和对应下标
 19     int Ms;//最大子段和
 20     int sum;//整段和
 21 };
 22 node tree[4 * N];
 23 node getans(node ans1,node ans2)
 24 {
 25     node ans;
 26     ans.sum = ans1.sum + ans2.sum;
 27     if(ans1.lval >= ans1.sum + ans2.lval)
 28     {
 29         ans.lval = ans1.lval;
 30         ans.lid = ans1.lid;
 31     }
 32     else
 33     {
 34         ans.lval = ans1.sum + ans2.lval;
 35         ans.lid = ans2.lid;
 36     }
 37     if(ans2.rval > ans2.sum + ans1.rval)
 38     {
 39         ans.rval = ans2.rval;
 40         ans.rid = ans2.rid;
 41     }
 42     else
 43     {
 44         ans.rval = ans2.sum + ans1.rval;
 45         ans.rid = ans1.rid;
 46     }
 47     if(ans1.Ms > ans1.rval + ans2.lval)
 48     {
 49         ans.Ms = ans1.Ms;
 50         ans.x = ans1.x;
 51         ans.y = ans1.y;
 52     }
 53     else
 54     {
 55         if(ans1.Ms == ans1.rval + ans2.lval)
 56         {    
 57             ans.Ms = ans1.Ms; 
 58             if(ans1.x <= ans1.rid)
 59             {
 60                 ans.x = ans1.x;
 61                 ans.y = ans1.y;
 62             }
 63             else
 64             {
 65                 ans.x = ans1.rid;
 66                 ans.y = ans2.lid;
 67             }
 68         }
 69         else
 70         {
 71             ans.Ms = ans1.rval + ans2.lval;
 72             ans.x = ans1.rid;
 73             ans.y = ans2.lid;
 74         }
 75     }
 76     if(ans2.Ms > ans.Ms)
 77     {
 78         ans.Ms = ans2.Ms;
 79         ans.x = ans2.x;
 80         ans.y = ans2.y;
 81     }
 82     return ans;
 83 }
 84 void build(int l,int r,int i)
 85 {
 86     tree[i].l = l;
 87     tree[i].r = r;
 88     tree[i].Ms = 0;
 89     if(l == r)
 90     {
 91         tree[i].lval = tree[i].rval = tree[i].Ms = tree[i].sum = val[l];
 92         tree[i].x = tree[i].y = tree[i].lid = tree[i].rid = l;
 93         return;
 94     }
 95     int mid = (l + r) >> 1;
 96     int li = L(i),ri = R(i);
 97     build(l,mid,li);
 98     build(mid + 1,r,ri);
 99     tree[i] = getans(tree[li],tree[ri]);
100     tree[i].l = l;
101     tree[i].r = r;
102 }
103 node query(int l,int r,int i)
104 {
105     node ans;
106     if(tree[i].l == l && tree[i].r == r)
107     {
108         ans = tree[i];
109         return ans;
110     }
111     node ans1,ans2,ans3;
112     ans1.Ms = ans2.Ms = ans3.Ms = INF;
113     int li = L(i), ri = R(i);
114     int mid = (tree[i].l + tree[i].r) >> 1;
115     if(r <= mid)
116         ans1 = query(l,r,li);
117     else if(l > mid)
118         ans2 = query(l,r,ri);
119     else
120     {
121         ans1 = query(l,mid,li);
122         ans2 = query(mid + 1, r, ri);
123     }
124     if(ans1.Ms == INF)
125         return ans2;
126     else if(ans2.Ms == INF)
127         return ans1;
128     else
129         ans = getans(ans1,ans2);
130     return ans;
131 }
132 int main()
133 {
134     int n,m,i,j;
135     int a,b;
136     int tcase;
137     scanf("%d",&tcase);
138     node ans;
139     while(tcase--)
140     {
141         scanf("%d%d",&n,&m);
142         for(i = 1; i <= n; i++)
143             scanf("%d",&val[i]);
144         build(1,n,1);
145         while(m--)
146         {
147             scanf("%d%d",&a,&b);
148             ans = query(a,b,1);
149             printf("%d %d\n",ans.x,ans.y);
150         }
151     }
152     return 0;
153 }