【SP2916】Can you answer these queries V

题面

You are given a sequence \(a_1,a_2,...,a_n\). (\(|A[i]| \leq 10000 , 1 \leq N \leq 10000\)). A query is defined as follows: Query(x1,y1,x2,y2) = \(Max{a_i+a_{i+1}+...+a_j;x_1 \leq i \leq y_1 , x_2 \leq j \leq y_2}\) and \(x_1 \leq x_2 , y_1 \leq y_2\). Given \(m\) queries (\(1 \leq M \leq 10000\)), your program must output the results of these queries.

题意

求所有左右端点分别在区间 \([x_1,y_1]\) 与 \([x_2,y_2]\) 的区间的最大连续子段和的最大值

思路

１° 两个区间不相交

答案显然是左边区间的 rmax+中间不重叠部分的 sum+右边区间的 lmax，即：\([x_1,y_1].rmax+[y_1,x_2].sum+[x_2,y_2].lmax\)

２° 两个区间相交

答案就会有三种情况

·① 答案区间为区间相交部分，即：\([x_2,y_1].max\)

·② 答案区间的左端点在相交部分左部，取相交部分左边的 rmax 和剩下区间的 lmax，再减掉加了两次的左边相交节点

即：\([x_1,x_2].rmax+[x_2,y_2].lmax-a_{x_2}\)

·③ 答案区间的右端点在相交部分右部，取相交部分右边的 lmax 和剩下区间的 rmax，再减掉加了两次的右边相交节点

即：\([y_1,y_2].lmax+[x_1,y_1].rmax-a_{y_1}\)

代码

/************************************************

*Author        :  lrj124

*Created Time  :  2019.09.27.21:55

*Mail          :  1584634848@qq.com

*Problem       :  spoj2916

************************************************/

#include <algorithm>

#include <cstring>

#include <cstdio>

using namespace std;

const int maxn = 10000 + 10;

struct seg { int l,r,sum,max; } tree[maxn<<2];

int T,n,q,a[maxn];

inline void pushup(int root) {

	tree[root].sum = tree[root<<1].sum+tree[root<<1|1].sum;

	tree[root].l = max(tree[root<<1].l,tree[root<<1|1].l+tree[root<<1].sum);

	tree[root].r = max(tree[root<<1|1].r,tree[root<<1].r+tree[root<<1|1].sum);

	tree[root].max = max(tree[root<<1].r+tree[root<<1|1].l,max(tree[root<<1].max,tree[root<<1|1].max));

}

inline void build(int l,int r,int root) {

	if (l == r) {

		tree[root] = { a[l],a[l],a[l],a[l] };

		return;

	}

	int mid = l+r>>1;

	build(l,mid,root<<1);

	build(mid+1,r,root<<1|1);

	pushup(root);

}

inline seg query(int l,int r,int ql,int qr,int root) {

	if (ql > qr) return {0,0,0,0};

	if (ql <= l && r <= qr) return tree[root];

	int mid = l+r>>1;

	if (mid >= qr) return query(l,mid,ql,qr,root<<1);

	if (ql > mid) return query(mid+1,r,ql,qr,root<<1|1);

	seg lson = query(l,mid,ql,qr,root<<1),rson = query(mid+1,r,ql,qr,root<<1|1),ans;

	ans = { max(lson.l,rson.l+lson.sum),max(rson.r,lson.r+rson.sum),rson.sum+lson.sum,max(lson.r+rson.l,max(lson.max,rson.max)) };

	return ans;

}

inline int solve(int l1,int r1,int l2,int r2) {

	if (r1 < l2) return query(1,n,l1,r1,1).r+query(1,n,r1+1,l2-1,1).sum+query(1,n,l2,r2,1).l;

	int ans = query(1,n,l2,r1,1).max;

	if (l1 < l2) ans = max(ans,query(1,n,l1,l2,1).r+query(1,n,l2,r2,1).l-a[l2]);

	if (r2 > r1) ans = max(ans,query(1,n,l1,r1,1).r+query(1,n,r1,r2,1).l-a[r1]);

	return ans;

}

int main() {

	for (scanf("%d",&T);T--;) {

		memset(tree,0,sizeof(tree));

		scanf("%d",&n);

		for (int i = 1;i <= n;i++) scanf("%d",&a[i]);

		build(1,n,1);

		for (scanf("%d",&q);q--;) {

			int l1,r1,l2,r2; scanf("%d%d%d%d",&l1,&r1,&l2,&r2);

			printf("%d\n",solve(l1,r1,l2,r2));

		}

	}

	return 0;

}

巴特西

【SP2916】Can you answer these queries V - 线段树

题面

题意

思路

１° 两个区间不相交

２° 两个区间相交

代码

最新文章

热门文章