recursion有一個整數序列a[n]。現在recursion有m次詢問，每次她想知道Max { A[i]+A[i+1]+...+A[j] ; x1 <= i <= y1 , x2 <= j <= y2 , x1 <= x2 , y1 <= y2 }。這么簡單的題，recursion當然會做啦，但是為了維持她的傲嬌屬性，她決定考考你。

Input
輸入的第一行為數據組數。對于每組數據，第一行包含一個正整數n和長度為n的序列a[n]。接下來一行有一個正整數m。下面m行分別描述m個詢問，每行包含四個整數x1,y1,x2,y2。

Output
對于每組數據輸出m行，分別表示m個詢問的答案

Sample Input
2
6 3 -2 1 -4 5 2
2
1 1 2 3
1 3 2 5
1 1
1
1 1 1 1
Sample Output
2
3
1

Hint
|A[i]|<=10000,1<=N<=10000,1<=M<=10000

思路：

首先用https://vjudge.net/problem/SPOJ-GSS3 這題的模板可以維護正常的區間詢問，單點修改的線段樹維護區間最大子段和問題。

然后對于題目的給定兩個區間中分別選一個l和r問題，

我們進行分類討論，我們看答案可能是哪種情況。

首先，如果x2>y1 那么答案就是 ( x1~y1 )中最大后綴數值+ ( y1~x2 ) 區間的數值sum和+ ( x2 + y2 中區間的最大前綴和 )

否則 兩個區間就一定有交叉的分布

即 數值的從小到大的順序是這樣： x1，x2，y1 , y2

那么答案可能是以下三種情況：

1、x2~y1 中的最大子段和。

2、l在 x1~x2 之間，y在x2~y2區間

3、l在x1~y1 之間，y在y1~y2 區間，

這三種情況就包含了所有可能。

細節見代碼：

#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <cmath> #include <queue> #include <stack> #include <map> #include <set> #include <vector> #include <iomanip> #define ALL(x) (x).begin(), (x).end() #define sz(a) int(a.size()) #define all(a) a.begin(), a.end() #define rep(i,x,n) for(int i=x;i<n;i++) #define repd(i,x,n) for(int i=x;i<=n;i++) #define pii pair<int,int> #define pll pair<long long ,long long> #define gbtb ios::sync_with_stdio(false),cin.tie(0),cout.tie(0) #define MS0(X) memset((X), 0, sizeof((X))) #define MSC0(X) memset((X), '\0', sizeof((X))) #define pb push_back #define mp make_pair #define fi first #define se second #define eps 1e-6 #define gg(x) getInt(&x) #define chu(x) cout<<"["<<#x<<" "<<(x)<<"]"<<endl using namespace std; typedef long long ll; ll gcd(ll a, ll b) {return b ? gcd(b, a % b) : a;} ll lcm(ll a, ll b) {return a / gcd(a, b) * b;} ll powmod(ll a, ll b, ll MOD) {ll ans = 1; while (b) {if (b % 2) { ans = ans * a % MOD; } a = a * a % MOD; b /= 2;} return ans;} inline void getInt(int *p); const int maxn = 50000 + 7; const int inf = 0x3f3f3f3f; /*** TEMPLATE CODE * * STARTS HERE ***/ struct node {int l;int r;ll num;ll lm;ll sum;ll rm; } segment_tree[maxn << 2]; int n; void pushup(int rt) {segment_tree[rt].sum = segment_tree[rt << 1].sum + segment_tree[rt << 1 | 1].sum;segment_tree[rt].lm = max(segment_tree[rt << 1].lm, segment_tree[rt << 1].sum + segment_tree[rt << 1 | 1].lm);segment_tree[rt].rm = max(segment_tree[rt << 1 | 1].rm, segment_tree[rt << 1 | 1].sum + segment_tree[rt << 1].rm);segment_tree[rt].num = max(segment_tree[rt << 1].num, segment_tree[rt << 1 | 1].num);segment_tree[rt].num = max(segment_tree[rt].num, segment_tree[rt << 1].rm + segment_tree[rt << 1 | 1].lm); }void build(int rt, int l, int r) {segment_tree[rt].l = l;segment_tree[rt].r = r;if (l == r) {scanf("%lld", &segment_tree[rt].num);segment_tree[rt].lm = segment_tree[rt].rm = segment_tree[rt].num;segment_tree[rt].sum = segment_tree[rt].num;return ;}int mid = (l + r) >> 1;build(rt << 1, l, mid);build(rt << 1 | 1, mid + 1, r);pushup(rt); }node ask(int rt, int l, int r) {if (l > r) {return node{0, 0, 0, 0, 0, 0};}if (segment_tree[rt].l == l && segment_tree[rt].r == r) {return segment_tree[rt];}int mid = (segment_tree[rt].r + segment_tree[rt].l) >> 1;if (l > mid) {return ask(rt << 1 | 1, l, r);} else if (r <= mid) {return ask(rt << 1, l, r);} else {node res1 = ask(rt << 1, l, mid);node res2 = ask(rt << 1 | 1, mid + 1, r);node res;res.sum = res1.sum + res2.sum;res.lm = max(res1.lm, res1.sum + res2.lm);res.rm = max(res2.rm, res2.sum + res1.rm);res.num = max(res1.num, res2.num);res.num = max(res.num, res1.rm + res2.lm);return res;} } void update(int rt, int x, int val) {if (segment_tree[rt].l == x && segment_tree[rt].r == x) {segment_tree[rt].num = val;segment_tree[rt].lm = val;segment_tree[rt].rm = val;segment_tree[rt].sum = val;return ;}int mid = (segment_tree[rt].l + segment_tree[rt].r) >> 1;if (x <= mid) {update(rt << 1, x, val);} else {update(rt << 1 | 1, x, val);}pushup(rt); } ll solve(int x1, int y1, int x2, int y2) {if (y1 < x2) {ll res = ask(1, x1, y1).rm;res += ask(1, y1 + 1, x2 - 1).sum;res += ask(1, x2, y2).lm;return res;} else {ll res = ask(1, x2, y1).num;res = max(res, ask(1, x1, x2).rm + ask(1, x2, y2).lm - ask(1, x2, x2).sum);res = max(res, ask(1, x1, y1).rm + ask(1, y1, y2).lm - ask(1, y1, y1).sum);return res;} } int main() {//freopen("D:\\code\\text\\input.txt","r",stdin);//freopen("D:\\code\\text\\output.txt","w",stdout);int t;scanf("%d", &t);while (t--) {scanf("%d", &n);build(1, 1, n);int m;scanf("%d", &m);while (m--) {int x1, x2, y1, y2;scanf("%d %d %d %d", &x1, &y1, &x2, &y2);printf("%lld\n", solve(x1, y1, x2, y2));}}return 0; }inline void getInt(int *p) {char ch;do {ch = getchar();} while (ch == ' ' || ch == '\n');if (ch == '-') {*p = -(getchar() - '0');while ((ch = getchar()) >= '0' && ch <= '9') {*p = *p * 10 - ch + '0';}} else {*p = ch - '0';while ((ch = getchar()) >= '0' && ch <= '9') {*p = *p * 10 + ch - '0';}} }

轉載于:https://www.cnblogs.com/qieqiemin/p/11447506.html

總結

以上是生活随笔為你收集整理的Can you answer these queries V SPOJ - GSS5 （分类讨论+线段树维护区间最大子段和）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。