View Code
1 #include<iostream>
2 #include<cstdio>
3 #include<algorithm>
4 #include<
string.h>
5 #define LL long long
6 using std::sort;
7 const int N =
100005;
8 struct Order
9 {
10 int l,r,id;
11 bool operator <(
const Order & tmp)
const
12 {
13 return r<
tmp.r;
14 }
15 }order[N];
16 LL pmax[N<<
2],padd[N<<
2],add[N<<
2],sum[N<<
2],ans[N];
17 int pos[N<<
1],num[N];
18 LL Max(LL a,LL b)
19 {
20 return a>b?
a:b;
21 }
22 void PushUp(
int t)
23 {
24 int t1=t<<
1,t2=t1|
1;
25 sum[t]=
Max(sum[t1],sum[t2]);
26 pmax[t]=
Max(pmax[t1],pmax[t2]);
27 }
28 void PushDown(
int t)
29 {
30 if(add[t]||
padd[t])
31 {
32 int t1=t<<
1,t2=t1|
1;
33 padd[t1]=Max(padd[t1],add[t1]+
padd[t]);
34 pmax[t1]=Max(pmax[t1],sum[t1]+
padd[t]);
35 add[t1]+=add[t],sum[t1]+=
add[t];
36 padd[t2]=Max(padd[t2],add[t2]+
padd[t]);
37 pmax[t2]=Max(pmax[t2],sum[t2]+
padd[t]);
38 add[t2]+=add[t],sum[t2]+=
add[t];
39 add[t]=padd[t]=
0;
40 }
41 }
42 void update(
int t,
int l,
int r,
int L,
int R,
int val)
43 {
44 if(L<=l&&r<=
R)
45 {
46 padd[t]=Max(padd[t],add[t]+=
(LL)val);
47 pmax[t]=Max(pmax[t],sum[t]+=
(LL)val);
48 return ;
49 }
50 PushDown(t);
51 int m=(l+r)>>
1;
52 if(L<=m)update(t<<
1,l,m,L,R,val);
53 if(R>m)update(t<<
1|
1,m+
1,r,L,R,val);
54 PushUp(t);
55 }
56 LL query(
int t,
int l,
int r,
int L,
int R)
57 {
58 if(L<=l&&r<=R)
return pmax[t];
59 PushDown(t);
60 int m=(l+r)>>
1;
61 LL aa=
0;
62 if(L<=m)aa=Max(aa,query(t<<
1,l,m,L,R));
63 if(R>m)aa=Max(aa,query(t<<
1|
1,m+
1,r,L,R));
64 return aa;
65 }
66 void build(
int t,
int l,
int r)
67 {
68 pos[t]=sum[t]=pmax[t]=padd[t]=
0;
69 if(l==r)
return ;
70 int m=(r+l)>>
1;
71 build(t<<
1,l,m);
72 build(t<<
1|
1,m+
1,r);
73 }
74 int main()
75 {
76 int n,m;
77 while(~scanf(
"%d",&
n))
78 {
79 for(
int i=
1;i<=n;i++){scanf(
"%d",&num[i]);pos[num[i]+N]=
0;}
80 scanf(
"%d",&
m);
81 for(
int i=
1;i<=m;i++){scanf(
"%d%d",&order[i].l,&order[i].r),order[i].id=
i;}
82 sort(order+
1,order+m+
1);
83 build(
1,
1,n);
84 for(
int i=
1,j=
1;i<=n;i++
)
85 {
86 update(
1,
1,n,pos[num[i]+N]+
1,i,num[i]);
87 pos[num[i]+N]=
i;
88 while(i>=
order[j].r)
89 {
90 ans[order[j].id]=query(
1,
1,n,order[j].l,order[j].r);
91 j++
;
92 if(j>m)
break;
93 }
94 if(j>m)
break;
95 }
96 for(
int i=
1;i<=m;i++)printf(
"%lld\n",ans[i]);
97 }
98 return 0;
99 }
看到这道题目的时候，被之前turing tree完全误导了。。 看来以后做题目还是要仔细的分析题目啊。。。
这道题目的更新有点特殊，每个点记录的是从这个位置起到某个点所产生的最大连续和。
好比如：x1,x2,x3,x4
那么最大连续和就只可能是x1 x1+x2 x1+x2+x3 x1+x2+x3+x4
x2 x2+x3 x2+x3+x4
x3 x3+x4
x4
那么我们怎么去维护这样子一个值呢，需要四个标记pmax(区间最大连续和) sum(区间总和) padd(历史最大累加和) add(累加总和)。
转载于:https://www.cnblogs.com/nuoyan2010/archive/2012/11/22/2782986.html
相关资源：JAVA上百实例源码以及开源项目
