【BZOJ2482】[Spoj1557] Can you answer these queries II

Description

给定n个元素的序列。
给出m个询问：求l[i]~r[i]的最大子段和（可选空子段）。
这个最大子段和有点特殊：一个数字在一段中出现了两次只算一次。
比如：1，2，3，2，2，2出现了3次，但只算一次，于是这个序列的和是1+2+3=6。

Input

第一行一个数n。
第二行n个数，为给定的序列，这些数的绝对值小于等于100000。
第三行一个数m。
接下来m行，每行两个数，l[i]，r[i]。

Output

M行，每行一个数，为每个询问的答案。

Sample Input

9
4 -2 -2 3 -1 -4 2 2 -6
3
1 2
1 5
4 9

Sample Output

4
5
3

HINT

【数据说明】
30%：1 <= n, m <= 100
100%：1 <= n, m <= 100000

题解：还是考虑这点：每个子串都是某个前缀的后缀，所以我们依旧枚举每个前缀，用线段树维护它的所有后缀。

出现两次只算一次怎么办？只需要在扫到一个数的时候将它上一个出现的位置变成0即可，这样就会改边很多后缀的值，用线段树去维护。

但是本题求的是最大连续子段和啊，其实只需要维护每个后缀的历史最大值就可以了。

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

#define lson x<<1

#define rson x<<1|1

using namespace std;

const int maxn=100010;

typedef long long ll;

int n,m;

int last[maxn<<1],pre[maxn],v[maxn];

ll ans[maxn];

struct node

{

	ll t,ht,s,hs;

}s[maxn<<2];

struct QUERY

{

	int l,r,org;

}q[maxn];

inline void phd(int x,int y)

{

	if(y>0)	s[x].hs=max(s[x].hs,s[x].s+y),s[x].ht=max(s[x].ht,s[x].t+y);

}

inline void pd(int x,int y)

{

	s[x].s+=y,s[x].t+=y;

	if(y>0)	s[x].hs=max(s[x].hs,s[x].s),s[x].ht=max(s[x].ht,s[x].t);

}

inline void pushdown(int x)

{

	if(s[x].ht)	phd(lson,s[x].ht),phd(rson,s[x].ht),s[x].ht=0;

	if(s[x].t)	pd(lson,s[x].t),pd(rson,s[x].t),s[x].t=0;

}

inline void pushup(int x)

{

	s[x].s=max(s[lson].s,s[rson].s),s[x].hs=max(s[lson].hs,s[rson].hs);

}

void updata(int l,int r,int x,int a,int b,int c)

{

	if(a<=l&&r<=b)

	{

		pd(x,c);

		return ;

	}

	pushdown(x);

	int mid=(l+r)>>1;

	if(a<=mid)	updata(l,mid,lson,a,b,c);

	if(b>mid)	updata(mid+1,r,rson,a,b,c);

	pushup(x);

}

ll query(int l,int r,int x,int a,int b)

{

	if(a<=l&&r<=b)	return s[x].hs;

	pushdown(x);

	int mid=(l+r)>>1;

	if(b<=mid)	return query(l,mid,lson,a,b);

	if(a>mid)	return query(mid+1,r,rson,a,b);

	return max(query(l,mid,lson,a,b),query(mid+1,r,rson,a,b));

}

bool cmp(const QUERY &a,const QUERY &b)

{

	return a.r<b.r;

}

inline int rd()

{

	int ret=0,f=1;	char gc=getchar();

	while(gc<'0'||gc>'9')	{if(gc=='-')f=-f;	gc=getchar();}

	while(gc>='0'&&gc<='9')	ret=ret*10+gc-'0',gc=getchar();

	return ret*f;

}

int main()

{

	n=rd();

	int i,j;

	for(i=1;i<=n;i++)	v[i]=rd(),pre[i]=last[v[i]+100000],last[v[i]+100000]=i;

	m=rd();

	for(i=1;i<=m;i++)	q[i].l=rd(),q[i].r=rd(),q[i].org=i;

	sort(q+1,q+m+1,cmp);

	for(i=j=1;i<=n;i++)

	{

		updata(1,n,1,pre[i]+1,i,v[i]);

		for(;q[j].r==i;j++)	ans[q[j].org]=query(1,n,1,q[j].l,i);

	}

	for(i=1;i<=m;i++)	printf("%lld\n",ans[i]);

	return 0;

}

巴特西

【BZOJ2482】[Spoj1557] Can you answer these queries II 线段树