Can you answer these queries V SPOJ - GSS5 （分类讨论+线段树维护区间最大子段和）

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';

        }

    }

}

巴特西

Can you answer these queries V SPOJ - GSS5 （分类讨论+线段树维护区间最大子段和）

最新文章

热门文章