Description:

$N$ 个数， $Q$ 个询问，求最大子段和，相同的数只算一次。

$1\le N,Q\le 100000$

Solution:

只有询问，则询问可以离线，相同的数只算一次，则一个数有作用的范围是 $[pre[A[i]]+1,i]$ ， $i$ 从 $1$ 到 $N$ 循环，线段树维护从这个节点开始的最大前缀和，用 $pre\text_max$ 表示从这个节点到当前指针的最大子段和， $cur\text_max$ 表示从这个节点到当前指针的总和，每到一个点，就给 $[pre[A[i]]+1,i]$ 打一个 $A[i]$ 的标记，如果 $cur\text_max+cur\text_tag\ge pre\text_max$ ，即之后能形成一个和更大的前缀，就更新 $pre\text_max$ ，发现这实际上就是一个线段树维护区间历史最大值，于是还要有一个 $pre\text_tag$ 表示区间历史最大标记，防止标记在 $pushdown$ 时被推没。

查询时发现实际上就是查询从 $[l,r]$ 节点开始的最大前缀和，所以只要在线段树中对 $pre\text_max$ 取 $max$ 即可。

Code:

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

int n;

#define MAXN 100010

int a[MAXN];

int m;

struct query

{

	int l,r,id,ans;

}q[MAXN];

int pre[MAXN << 1];

#define p(k) pre[k + MAXN]

bool cmp_r(query a,query b){return a.r < b.r;}

bool cmp_id(query a,query b){return a.id < b.id;}

struct node

{

	int lc,rc;

	int pre_tag,pre_max,cur_tag,cur_max;

	node(){lc = rc = pre_tag = pre_max = cur_tag = cur_max = 0;}

}t[MAXN << 1];

int ptr = 0;

int newnode(){return ++ptr;}

int root;

void build(int rt,int l,int r)

{

	if(l == r)return;

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

	build(t[rt].lc = newnode(),l,mid);

	build(t[rt].rc = newnode(),mid + 1,r);

	return;

}

void merge(int rt)

{

	int lc = t[rt].lc,rc = t[rt].rc;

	t[rt].pre_max = max(t[lc].pre_max,t[rc].pre_max);

	t[rt].cur_max = max(t[lc].cur_max,t[rc].cur_max); 

	return;

}

void pushdown(int rt)

{

	if(t[rt].pre_tag == 0 && t[rt].cur_tag == 0)return;

	int lc = t[rt].lc,rc = t[rt].rc;

	t[lc].pre_max = max(t[lc].pre_max,t[lc].cur_max + t[rt].pre_tag);

	t[rc].pre_max = max(t[rc].pre_max,t[rc].cur_max + t[rt].pre_tag);

	t[lc].pre_tag = max(t[lc].pre_tag,t[lc].cur_tag + t[rt].pre_tag);

	t[rc].pre_tag = max(t[rc].pre_tag,t[rc].cur_tag + t[rt].pre_tag);

	t[lc].cur_tag += t[rt].cur_tag;

	t[rc].cur_tag += t[rt].cur_tag;

	t[lc].cur_max += t[rt].cur_tag;

	t[rc].cur_max += t[rt].cur_tag;

	t[rt].pre_tag = t[rt].cur_tag = 0;

	return;

}

void updata(int rt,int L,int R,int k,int l,int r)

{

	if(L <= l && r <= R)

	{

		t[rt].cur_tag += k;

		t[rt].cur_max += k;

		t[rt].pre_tag = max(t[rt].pre_tag,t[rt].cur_tag);

		t[rt].pre_max = max(t[rt].pre_max,t[rt].cur_max);

		return;

	}

	pushdown(rt);

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

	if(L <= mid)updata(t[rt].lc,L,R,k,l,mid);

	if(R >= mid + 1)updata(t[rt].rc,L,R,k,mid + 1,r);

	merge(rt);

	return;

}

int query(int rt,int L,int R,int l,int r)

{

	if(L <= l && r <= R)

	{

		return t[rt].pre_max;

	}

	pushdown(rt);

	int res = 0;

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

	if(L <= mid)res = max(res,query(t[rt].lc,L,R,l,mid));

	if(R >= mid + 1)res = max(res,query(t[rt].rc,L,R,mid + 1,r));

	return res;

}

int main()

{

	scanf("%d",&n);

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

	{

		scanf("%d",&a[i]);

	}

	scanf("%d",&m);

	for(int i = 1;i <= m;++i)

	{

		scanf("%d%d",&q[i].l,&q[i].r);

		q[i].id = i;

	}

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

	build(root = newnode(),1,n);

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

	{

		updata(root,p(a[i]) + 1,i,a[i],1,n);

		p(a[i]) = i;

		for(;q[j].r == i;++j)

		{

			q[j].ans = query(root,q[j].l,q[j].r,1,n);

		}

	}

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

	for(int i = 1;i <= m;++i)

	{

		printf("%d\n",q[i].ans);

	}

	return 0;

}