Steven_MengのBlog

感觉这题自己也讲不清,还是搬运洛谷的一篇题解吧。。。

作者: duyi

在Ta的博客查看


观察这题与GSS1的最主要差别是需要去重。

这样的问题有一个比较套路化的技巧(主要看个人经验)。就是可以离线做。我们将所有询问按r从小到大排序。

我们一次从11

如:

叶子结点1:a[1]+a[2]+...+a[i]a[1] + a[2] + … + a[i]

叶子结点2:a[2]+a[3]+...+a[i]a[2] + a[3] + … + a[i]

叶子结点i:a[i]a[i]

我们顺次扫过整个序列,在更新ii

更新后:

叶子结点1:a[1]+a[2]+...+a[i1]a[1] + a[2] + … + a[i-1]

叶子结点2:a[2]+a[3]+...+a[i1]a[2] + a[3] + … + a[i-1]

叶子结点j:a[j]+a[j+1]+...+a[i1]a[j] + a[j+1] + … + a[i-1]

叶子结点j+1:a[j+1]+a[j+2]+...+a[i1]+a[i]a[j+1] + a[j+2] + … + a[i-1] + a[i]

叶子结点i-1:a[i1]+a[i]a[i-1] + a[i]

叶子结点i:a[i]a[i]

考虑下一次更新。如果不考虑pre[i+1]pre[i+1]

此时叶子结点1变为:a[1]+a[2]+...+a[i1]a[1] + a[2] + … + a[i-1]

叶子结点2变为:a[2]+a[3]+...+a[i1]a[2] + a[3] + … + a[i-1]

叶子结点j:a[j]+a[j+1]+...+a[i1]a[j] + a[j+1] + … + a[i-1]

叶子结点j+1:a[j+1]+a[j+2]+...+a[i1]+a[i]a[j+1] + a[j+2] + … + a[i-1] + a[i]

叶子结点i-1:a[i1]+a[i]a[i-1] + a[i]

叶子结点i:a[i]a[i]

我们发现,我们的操作实际上是对序列进行了自动去重。我们之所以能实现这样的去重,实质上是两步操作的结果:

  1. ii

  2. 在第i+1i+1

如此一来,当我们更新到位置kk

这样,当扫描到的k等于当前询问的r时,我们就可以去线段树里找答案了。然而,以r结尾的子序列并不一定是最优的,因此我们对于线段树里的每个节点还要维护一个Max。表示在扫描整个序列的过程中,在该节点所管辖的范围内所出现过的最大的Sum值

现在,每个叶子节点都对应了一段子序列的和。我们要高效地求出所有这些和中最大的一个,于是问题就转化为了用线段树求区间最大值。由于在扫描整个序列的过程中,我们需要不断地对线段树进行更新,为了高效地维护Sum和Max,我们引入懒标记LazySum和LazyMax。

当我们用 a[i] 更新当前整个区间时:

  • Sum += a[i]

  • Max = max(Sum, Max)

  • LazySum += a[i]

  • LazyMax = max(LazySum, LazyMax)

当我们下放懒标记时

  • son.Max = max(son.Max,son.sum+fa.LazyMax)

  • son.Sum += fa.LazySum

  • son.LazyMax = max(son.LazyMax,son.LazySum+fa.LazyMax)

  • son.LazySum += fa.LazySum

那么对于区间[l,r][l,r]

参考代码:

(我的代码)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
#include <bits/stdc++.h>
#define MAXN 100005
#define INF 0x7fffffff
using namespace std;
inline int read(){
int x=0,f=1;
char ch=getchar();
while (ch<'0'||ch>'9'){
if (ch=='-') f=-1;
ch=getchar();
}
while (ch>='0'&&ch<='9'){
x=(x<<3)+(x<<1)+(ch^'0');
ch=getchar();
}
return x*f;
}
namespace SegmentTree{
struct node{
int l,r;
int sum,maxn;//maxn:sum历史最大值
int sumtag,maxtag;
}tree[MAXN<<2];
#define lc i<<1
#define rc i<<1|1
inline void pushup(int i){
tree[i].sum=max(tree[lc].sum,tree[rc].sum);
tree[i].maxn=max(tree[lc].maxn,tree[rc].maxn);
}
inline void Change(int s,int i){
tree[s].maxn=max(tree[s].maxn,tree[s].sum+tree[i].maxtag);
tree[s].sum+=tree[i].sumtag;
tree[s].maxtag=max(tree[s].maxtag,tree[s].sumtag+tree[i].maxtag);
tree[s].sumtag+=tree[i].sumtag;
}
inline void pushdown(int i){
Change(lc,i),Change(rc,i);
tree[i].maxtag=tree[i].sumtag=0;
}
void Build(int i,int l,int r){
tree[i].l=l,tree[i].r=r;
if (l==r) return ;
int mid=(l+r)>>1;
Build(lc,l,mid);
Build(rc,mid+1,r);
}
void Update(int i,int L,int R,int val){
if (L<=tree[i].l&&tree[i].r<=R){
tree[i].sum+=val;
tree[i].maxn=max(tree[i].sum,tree[i].maxn);
tree[i].sumtag+=val;
tree[i].maxtag=max(tree[i].maxtag,tree[i].sumtag);
return ;
}
pushdown(i);
int mid=(tree[i].l+tree[i].r)>>1;
if (L<=mid) Update(lc,L,R,val);
if (mid<R) Update(rc,L,R,val);
pushup(i);
}
int Query(int i,int L,int R){
if (L<=tree[i].l&&tree[i].r<=R){
return tree[i].maxn;
}
pushdown(i);
int mid=(tree[i].l+tree[i].r)>>1,ans=-INF;
if (L<=mid) ans=max(ans,Query(lc,L,R));
if (mid<R) ans=max(ans,Query(rc,L,R));
return ans;
}
}
using namespace SegmentTree;
int pre[MAXN*2],last[MAXN*2];//求出a[i]前使a[j]=a[i]最大的j,类似于链表
int a[MAXN];
#define NUM 100005
struct Qry{
int l,r;
int id;
}Q[MAXN];
bool operator < (const Qry &A,const Qry &B){
return A.r<B.r;
}
int ans[MAXN];
int main(){
int n=read();
for (register int i=1;i<=n;++i){
a[i]=read();
pre[i]=last[a[i]+NUM];
last[a[i]+NUM]=i;
}
int q=read();
for (register int i=1;i<=q;++i){
Q[i].l=read(),Q[i].r=read();
Q[i].id=i;
}
Build(1,1,n);
sort(Q+1,Q+1+q);
register int pos=1;
for (register int i=1;i<=n;++i){
Update(1,pre[i]+1,i,a[i]);
for (;pos<=q;++pos){
if (Q[pos].r>i){
break;
}
ans[Q[pos].id]=Query(1,Q[pos].l,Q[pos].r);
}
}
for (register int i=1;i<=q;++i){
printf("%d\n",ans[i]);
}
}

不知道为什么格式乱了

 评论