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
| //NAME:- ANUHAR TRIPATHI
//COLLEGE:- JAYPEE UNIVERSITY OF ENGINEERING & TECHNOLOGY, GUNA
//EMAIL:- anuhartripathi15@gmail.com
//SPOJ Problem:- GSS3 - Can you answer these queries III
#include<bits/stdc++.h>
#define ll long long
using namespace std;
class node
{
public:
ll suf,pre,result,sum;
}tree[131080];
ll a[131080];
void build(ll l, ll r, ll pos)
{
if(l==r)
{
tree[pos].sum=tree[pos].pre=tree[pos].suf=tree[pos].result=a[l];
return;
}
ll mid=(l+r)/2;
build(l,mid,pos*2); build(mid+1,r,pos*2+1);
tree[pos].sum=tree[pos*2].sum+tree[pos*2+1].sum;
tree[pos].pre=max(tree[pos*2].pre, tree[pos*2+1].pre+tree[pos*2].sum);
tree[pos].suf=max(tree[pos*2].suf+tree[pos*2+1].sum, tree[pos*2+1].suf);
tree[pos].result=max( max(tree[pos*2].result,tree[pos*2+1].result), tree[pos*2].suf+tree[pos*2+1].pre);
return;
}
void update(ll pos)
{
while(pos!=0)
{
tree[pos].sum=tree[pos*2].sum+tree[pos*2+1].sum;
tree[pos].pre=max(tree[pos*2].pre, tree[pos*2+1].pre+tree[pos*2].sum);
tree[pos].suf=max(tree[pos*2].suf+tree[pos*2+1].sum, tree[pos*2+1].suf);
tree[pos].result=max( max(tree[pos*2].result,tree[pos*2+1].result), tree[pos*2].suf+tree[pos*2+1].pre);
pos/=2;
}
return;
}
node query(ll q1,ll q2,ll l,ll r,ll pos)
{
if(r<q1||l>q2)return tree[0];
if(l>=q1&&r<=q2)
return tree[pos];
ll mid=(l+r)/2; node w,x,z;
w=query(q1,q2,l,mid,pos*2);
x=query(q1,q2,mid+1,r,pos*2+1);
z.sum=w.sum+x.sum;
z.suf=max(w.suf+x.sum, x.suf);
z.pre=max(w.pre, x.pre+w.sum);
z.result=max( max(w.result,x.result), w.suf+x.pre);
return z;
}
int main()
{
ll n; cin>>n;
ll i,j,m;
for(i=0;i<n;i++) cin>>a[i];
build(0,n-1,1);
tree[0].sum=tree[0].pre=tree[0].suf=tree[0].result=INT_MIN;
cin>>m;
bool q; ll x,y,z;
for(i=0;i<m;i++)
{
cin>>q;
if(q==0)
{
cin>>x>>y; x--;
a[x]=y;
y=1;ll ss,ee,mid;ss=0;ee=n-1;
while(ss!=ee)
{
mid=(ss+ee)/2;
if(x<=mid) {y*=2;ee=mid;}
else {ss=mid+1;y=y*2+1;}
}
tree[y].sum=tree[y].pre=tree[y].suf=tree[y].result=a[x];
update(y/2);
}
else
{
cin>>x>>y; x--; y--;
node cc=query(x,y,0,n-1,1);
cout<<cc.result<<"\n";
}
}
return 0;
}
|
Comments
Post a Comment