[GSS5] Can you answer these queries V

大力讨论。

luogu上交spoj的题卡的一比...

难受

wa了好几次，原因大概首先求的是非空区间，不能乱和0取max，第二点是求无相交的解时，在两段求lmx和rmx的时候可以取max(0)。

区间相交的有四种讨论，大概就是讨论一下左右端点在左/右/公共区间即可。

#include <cstdio>

#include <cstring>

#include <iostream>

using namespace std;

const int N=10005;

int n,q,a[N];

struct Segtree {

	int lmx,rmx,mx,sum;

	Segtree() {lmx=rmx=mx=sum=0;}

} t[N<<2];

Segtree pushup(Segtree x,Segtree y) {

	Segtree ans;

	ans.sum=x.sum+y.sum;

	ans.lmx=max(x.sum+y.lmx,x.lmx);

	ans.rmx=max(y.sum+x.rmx,y.rmx);

	ans.mx=max(x.mx,max(y.mx,x.rmx+y.lmx));

	return ans;

}

void build(int cur,int l,int r) {

	if(l==r) {

		t[cur].sum=t[cur].rmx=t[cur].lmx=t[cur].mx=a[l];

		return;

	}

	int mid=l+r>>1;

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

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

	t[cur]=pushup(t[cur<<1],t[cur<<1|1]);

}

Segtree query(int ql,int qr,int l,int r,int cur) {

	if(ql>qr) {	Segtree x;return x;}

	if(ql<=l&&r<=qr) return t[cur];

	int mid=l+r>>1;

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

	else if(qr<=mid) return query(ql,qr,l,mid,cur<<1);

	else return pushup(query(ql,qr,l,mid,cur<<1),query(ql,qr,mid+1,r,cur<<1|1));

}

int T;

int main() {

	scanf("%d",&T);

	while(T--) {

		scanf("%d",&n);

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

		build(1,1,n);

		scanf("%d",&q);

		int xa,xb,ya,yb;

		while(q--) {

			scanf("%d%d%d%d",&xa,&ya,&xb,&yb);

			int ans=0;

			if(ya<xb) {

				ans+=query(ya,xb,1,n,1).sum;

				ans+=max(0,query(xa,ya-1,1,n,1).rmx);

				ans+=max(0,query(xb+1,yb,1,n,1).lmx);

			} else {

				Segtree res1,res2,res3;

				res1=query(xa,xb-1,1,n,1);

				res2=query(xb,ya,1,n,1);

				res3=query(ya+1,yb,1,n,1);

				ans=max(max(res2.mx,res1.rmx+res2.lmx),max(res2.rmx+res3.lmx,res1.rmx+res2.sum+res3.lmx));

			}

			printf("%d\n",ans);

		}

	}

	return 0;

}

巴特西

[GSS5] Can you answer these queries V

最新文章

热门文章