首页 > 代码库 > SPOJ GSS系列 解题报告
SPOJ GSS系列 解题报告
这个系列总共有7道题，目前只做了3道，gss2比较难，gss4是暴力修改，树状数组维护，还没写，gss6和gss7还不在能力范围内。
题意：给定长度不超过5万的序列，M次查询(貌似没给大小？。。)，查询所给区间内的最大子段和。
做法：线段树。维护区间和sum，区间可以得到的最大值smax，从区间最左边开始的最大和lmax和右边开始的rmax，然后就可以了。具体更新还是看代码吧。比较巧妙的在于，把query函数的类型设为线段树的节点类型，这样就可以把它的子区间用update(即pushup)的操作来合并，否则query函数会很难写。
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 int n, m; 5 int a[50100]; 6 struct tree{ 7 int sum, lmax, rmax, smax; 8 } t[50010 << 2]; 9 10 int max(int a, int b)11 {12 return a>b?a:b;13 }14 void update(tree &x, tree lson, tree rson)15 {16 x.sum = lson.sum + rson.sum;17 x.lmax = max(lson.lmax, lson.sum+rson.lmax);18 x.rmax = max(rson.rmax, rson.sum+lson.rmax);19 int tmp = max(x.lmax, x.rmax);20 tmp = max(tmp, x.sum);21 tmp = max(tmp, lson.smax);22 tmp = max(tmp, rson.smax);23 tmp = max(tmp, lson.rmax+rson.lmax);24 x.smax = tmp;25 //x.smax = max(max(x.sum, max(x.lmax, x.rmax)), max(max((lson.smax, rson.smax), (lson.rmax+rson.lmax))));26 }27 void build(int x, int l, int r)28 {29 if (l == r){30 t[x].sum = t[x].lmax = t[x].rmax = t[x].smax = a[l];31 return;32 }33 int mid = l + r >> 1, lson = x<<1, rson = x<<1|1;34 build(lson, l, mid);35 build(rson, mid+1, r);36 update(t[x], t[lson], t[rson]);37 }38 tree query(int s, int e, int x, int l, int r)39 {40 if (s <= l && r <= e){41 //if (s <= l && r <= e){42 return t[x];43 }44 int mid = l + r >> 1;45 if (e <= mid) return query(s, e, x<<1, l, mid);46 if (s > mid) return query(s, e, x<<1|1, mid+1, r);47 tree p, q, ans;48 p = query(s, mid, x<<1, l, mid);49 q = query(mid+1, e, x<<1|1, mid+1, r);50 update(ans, p, q);51 return ans;52 }53 int main()54 {55 scanf("%d", &n);56 for (int i = 1; i <= n; i++)57 scanf("%d", &a[i]);58 build(1, 1, n);59 60 // for (int i = 1; i <= 10; i++)61 // printf("%d %d %d %d %d\n", i, t[i].sum, t[i].lmax, t[i].rmax, t[i].smax);62 63 scanf("%d", &m);64 int x, y;65 for (int i = 0; i < m; i++){66 scanf("%d %d", &x, &y);67 printf("%d\n", query(x, y, 1, 1, n).smax);68 }69 return 0;70 }
分析：相比gss1，多了一个单点修改的操作。
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 int n, m; 5 int a[50100]; 6 struct tree{ 7 int sum, lmax, rmax, smax; 8 } t[50010 << 2]; 9 10 int max(int a, int b)11 {12 return a>b?a:b;13 }14 void pushup(tree &x, tree lson, tree rson)15 {16 x.sum = lson.sum + rson.sum;17 x.lmax = max(lson.lmax, lson.sum+rson.lmax);18 x.rmax = max(rson.rmax, rson.sum+lson.rmax);19 /* int tmp = max(x.lmax, x.rmax);20 tmp = max(tmp, x.sum);21 tmp = max(tmp, lson.smax);22 tmp = max(tmp, rson.smax);23 */24 int tmp = max(lson.smax, rson.smax);25 tmp = max(tmp, lson.rmax+rson.lmax);26 x.smax = tmp;27 }28 void build(int x, int l, int r)29 {30 if (l == r){31 t[x].sum = t[x].lmax = t[x].rmax = t[x].smax = a[l];32 return;33 }34 int mid = l + r >> 1, lson = x<<1, rson = x<<1|1;35 build(lson, l, mid);36 build(rson, mid+1, r);37 pushup(t[x], t[lson], t[rson]);38 }39 void update(int x, int l, int r, int p, int d)40 {41 if (l == r){42 t[x].sum = t[x].lmax = t[x].rmax = t[x].smax = d;43 return;44 }45 int mid = l + r >> 1;46 if (p <= mid) update(x<<1, l, mid, p, d);47 if (p > mid) update(x<<1|1, mid+1, r, p, d);48 pushup(t[x], t[x<<1], t[x<<1|1]);49 }50 tree query(int s, int e, int x, int l, int r)51 {52 if (s <= l && r <= e){53 return t[x];54 }55 int mid = l + r >> 1;56 if (e <= mid) return query(s, e, x<<1, l, mid);57 if (s > mid) return query(s, e, x<<1|1, mid+1, r);58 tree p, q, ans;59 p = query(s, mid, x<<1, l, mid);60 q = query(mid+1, e, x<<1|1, mid+1, r);61 pushup(ans, p, q);62 return ans;63 }64 int main()65 {66 scanf("%d", &n);67 for (int i = 1; i <= n; i++)68 scanf("%d", &a[i]);69 build(1, 1, n);70 scanf("%d", &m);71 int q, x, y;72 for (int i = 0; i < m; i++){73 scanf("%d %d %d", &q, &x, &y);74 if (q == 1)75 printf("%d\n", query(x, y, 1, 1, n).smax);76 else77 update(1, 1, n, x, y);78 }79 return 0;80 }
分析：相比gss1，查询变成对左端点和右端点的不同区间限制，耐心地分类讨论就可以了。
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 int n, m; 5 int a[10100], sum[10100]; 6 struct tree{ 7 int sum, lmax, rmax, smax; 8 } t[10100 << 2]; 9 10 int max(int a, int b)11 {12 return a>b?a:b;13 }14 void update(tree &x, tree lson, tree rson)15 {16 x.sum = lson.sum + rson.sum;17 x.lmax = max(lson.lmax, lson.sum+rson.lmax);18 x.rmax = max(rson.rmax, rson.sum+lson.rmax);19 int tmp = max(lson.smax, rson.smax);20 tmp = max(tmp, lson.rmax+rson.lmax);21 x.smax = tmp;22 }23 void build(int x, int l, int r)24 {25 if (l == r){26 t[x].sum = t[x].lmax = t[x].rmax = t[x].smax = a[l];27 return;28 }29 int mid = l + r >> 1, lson = x<<1, rson = x<<1|1;30 build(lson, l, mid);31 build(rson, mid+1, r);32 update(t[x], t[lson], t[rson]);33 }34 tree query(int s, int e, int x, int l, int r)35 {36 if (s <= l && r <= e){37 return t[x];38 }39 int mid = l + r >> 1;40 if (e <= mid) return query(s, e, x<<1, l, mid);41 if (s > mid) return query(s, e, x<<1|1, mid+1, r);42 tree p, q, ans;43 p = query(s, mid, x<<1, l, mid);44 q = query(mid+1, e, x<<1|1, mid+1, r);45 update(ans, p, q);46 return ans;47 }48 int main()49 {50 int T;51 scanf("%d", &T);52 while(T--)53 {54 scanf("%d", &n);55 for (int i = 1; i <= n; i++)56 scanf("%d", &a[i]);57 sum[0] = 0;58 for (int i = 1; i <= n; i++)59 sum[i] = sum[i-1] + a[i];60 build(1, 1, n);61 scanf("%d", &m);62 int x1, y1, x2, y2;63 for (int i = 0; i < m; i++){64 scanf("%d %d %d %d", &x1, &y1, &x2, &y2);65 int ans = 0;66 if (y1 == x2){67 // ans = a[y1];68 // int tmp1 = 0, tmp2 = 0;69 // if (x1 <= y1-1) tmp1 = max(query(x1, y1-1, 1, 1, n).rmax, 0);70 // if (x2+1 <= y2) tmp2 = max(query(x2+1, y2, 1, 1, n).lmax, 0);71 // ans += tmp1 + tmp2;72 ans = query(x1, y1, 1, 1, n).rmax + query(x2, y2, 1, 1, n).lmax - a[y1];73 }74 else if (y1 < x2){75 ans = sum[x2-1] - sum[y1];76 ans += query(x1, y1, 1, 1, n).rmax + query(x2, y2, 1, 1, n).lmax;77 }78 else{79 int tmp = query(x2, y1, 1, 1, n).smax;80 ans = tmp;81 82 tmp = sum[y1-1] - sum[x2];83 tmp += query(x1, x2, 1, 1, n).rmax + query(y1, y2, 1, 1, n).lmax;84 ans = max(tmp, ans);85 86 tmp = query(x1, x2, 1, 1, n).rmax + query(x2, y1, 1, 1, n).lmax - a[x2];87 ans = max(tmp, ans);88 89 tmp = query(x2, y1, 1, 1, n).rmax + query(y1, y2, 1, 1, n).lmax - a[y1];90 ans = max(tmp, ans);91 92 }93 printf("%d\n", ans); 94 }95 }96 return 0;97 }
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。