首页 > 代码库 > Spoj 2916 Can you answer these queries V 线段树 求任意重叠区间的最大子段和
Spoj 2916 Can you answer these queries V 线段树 求任意重叠区间的最大子段和
题目链接:点击打开链接
题意:
T个测试数据
n个数字
q个询问
每个询问 : [x1, y1] [x2, y2]
问:
int ans = -inf; for(int i = x1; i <= y1; i++) for(int j = max(x2, i); j <= y2; j++) ans = max(ans, query(i, j));
思路:
query_L(int l, int r) 求的是在区间[l,r]内 ,左端点为l的最大子段和。
其他和GSS3差不多。
分类讨论一下给定的区间[x1, y1] [x2, y2]
1、若两个区间分离( y1 < x2 ) 则 (y1 , x2) 部分必选,其他部分就尽量拓展
2、若 y1 == x2,则中间这个点必选,其他两边要么不选要么尽量拓展。
3、区间重合时,则类似讨论即可,把区间分成: [x1, y1), [y1,x2] , (x2, y2] ,那么【i,j】落在这3个区间的情况有4种。
在两边区间的情况就和1一样,都在中间区间的情况就是GSS3的问题。
另外2种情况就和2类似。
#include <cstdio> #include <iostream> #include <algorithm> #include <string.h> #include <math.h> #include <vector> #include <map> using namespace std; #define N 10005 #define Lson(x) tree[x].l #define Rson(x) tree[x].r #define L(x) (x<<1) #define R(x) (x<<1|1) #define Sum(x) tree[x].sum #define Max(x) tree[x].max #define Lmax(x) tree[x].lmax #define Rmax(x) tree[x].rmax struct node{ int l, r; int mid(){return (l+r)>>1;} int lmax, rmax, max, sum; }tree[N<<2]; int n, a[N], Q; int query_sum(int l, int r, int id){ if(l == Lson(id) && Rson(id) == r)return Sum(id); int mid = tree[id].mid(); if(mid < l) return query_sum(l, r, R(id)); else if(r<=mid) return query_sum(l, r, L(id)); else return query_sum(l, mid, L(id)) + query_sum(mid+1, r, R(id)); } void push_up(int id){ Lmax(id) = max(Lmax(L(id)), Sum(L(id)) + Lmax(R(id))); Rmax(id) = max(Rmax(R(id)), Sum(R(id)) + Rmax(L(id))); Sum(id) = Sum(L(id)) + Sum(R(id)); Max(id) = max(max(Max(L(id)), Max(R(id))), Rmax(L(id)) + Lmax(R(id))); } void updata_point(int val, int id){Lmax(id) = Rmax(id) = Max(id) = Sum(id) = val;} void build(int l, int r, int id){ Lson(id) = l; Rson(id) = r; if(l == r) { updata_point(a[l], id); return; } int mid = tree[id].mid(); build(l, mid, L(id)); build(mid+1, r, R(id)); push_up(id); } int query_l(int l, int r, int id){ if(l == Lson(id) && Rson(id) == r) return Lmax(id); int mid = tree[id].mid(); if(mid < l) return query_l(l, r, R(id)); else if(r <= mid) return query_l(l, r, L(id)); int lans = query_l(l, mid, L(id)), rans = query_l(mid+1, r, R(id)); return max(lans, Sum(L(id)) + rans); } int query_r(int l, int r, int id){ if(l == Lson(id) && Rson(id) == r) return Rmax(id); int mid = tree[id].mid(); if(mid < l) return query_r(l, r, R(id)); else if(r <= mid) return query_r(l, r, L(id)); int lans = query_r(l, mid, L(id)), rans = query_r(mid+1, r, R(id)); return max(rans, Sum(R(id)) + lans); } int query_L(int l, int r, int id){ if(l == Lson(id) && Rson(id) == r) return Lmax(id); int mid = tree[id].mid(); if(mid < l) return query_L(l, r, R(id)); else if(r <= mid) return query_L(l, r, L(id)); int lans = query_L(l, mid, L(id)), rans = query_L(mid+1, r, R(id)); return max(lans, query_sum(l, mid, id) + rans); } int query_R(int l, int r, int id){ if(l == Lson(id) && Rson(id) == r) return Rmax(id); int mid = tree[id].mid(); if(mid < l) return query_R(l, r, R(id)); else if(r <= mid) return query_R(l, r, L(id)); int lans = query_R(l, mid, L(id)), rans = query_R(mid+1, r, R(id)); return max(rans, query_sum(mid+1, r, id) + lans); } int query(int l, int r, int id){ if(l == Lson(id) && Rson(id) == r)return Max(id); int mid = tree[id].mid(); if(mid < l) return query(l, r, R(id)); else if(r<=mid) return query(l, r, L(id)); int lans = query(l, mid, L(id)), rans = query(mid+1, r, R(id)); int ans = max(lans, rans); return max(ans, query_r(l, mid, L(id)) + query_l(mid+1, r, R(id))); } void solve(){ scanf("%d",&n); for(int i = 1; i <= n; i++)scanf("%d",&a[i]); build(1, n, 1); scanf("%d",&Q); while(Q--){ int x1, x2, y1, y2, ans; scanf("%d %d %d %d", &x1, &y1, &x2, &y2); if(y1<x2) { ans = query_R(x1, y1, 1) + query_L(x2, y2, 1); if(y1+1 <= x2-1) ans += query_sum(y1+1, x2-1, 1); } else if(y1 == x2){ ans = query_sum(y1, x2, 1); if(x1 <= y1-1) ans += max(0, query_R(x1, y1-1, 1)); if(x2+1 <= y2) ans += max(0, query_L(x2+1, y2, 1)); } else { ans = query(x2, y1, 1);// i,j都在中间 int tmp = query_R(x1, x2, 1) + query_L(y1, y2, 1);// i,j都在2边 if(x2+1 <= y1-1) tmp += query_sum(x2+1, y1-1, 1); ans = max(ans, tmp); tmp = query_L(x2, y2, 1); if(x1 <= x2-1) tmp += query_R(x1, x2-1, 1); ans = max(ans, tmp); tmp = query_R(x1, y1, 1); if(y1+1 <= y2) tmp += query_L(y1+1, y2, 1); ans = max(ans, tmp); } printf("%d\n",ans); } } int main(){ int T;scanf("%d",&T); while(T--) solve(); return 0; }
Spoj 2916 Can you answer these queries V 线段树 求任意重叠区间的最大子段和
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。