You are given the following queries over n elements:
Query No.1: Increase elements between a and b with value c (it's possible that c is negative).
Query No.2: Get maximal value of all elements (e.g. max(a[i]) 1<=i<=n)
#include<bits/stdc++.h>
using namespace std;
int lazy[1000],mx[1000],idx[1000];
struct node{
int ll,rr,id;
node(int L,int R,int X){
ll=L;
rr=R;
id=X;
lazy_update();
}
node left(){
return node(ll,(ll+rr)/2,id*2);
}
node right(){
return node((ll+rr)/2+1,rr,id*2+1);
}
void lazy_update(){
if(lazy[id]==0)return;
mx[id]+=lazy[id];
if(ll!=rr){
lazy[id*2]+=lazy[id];
lazy[id*2+1]+=lazy[id];
}
lazy[id]=0;
}
void assign_range(int l,int r,int x){
lazy_update();
if(ll>r||l>rr)return;
if(ll==rr){
idx[id]=ll;
}
if(l<=ll&&rr<=r){
lazy[id]+=x;
lazy_update();
return;
}
left().assign_range(l,r,x);
right().assign_range(l,r,x);
if(mx[id*2]>mx[id*2+1]){
mx[id]=mx[id*2];
idx[id]=idx[id*2];
}
else{
mx[id]=mx[id*2+1];
idx[id]=idx[id*2+1];
}
}
int max_range(int l,int r){
if(ll>r||l>rr)return -1e9;
lazy_update();
if(l<=ll&&rr<=r){
return mx[id];
}
int mx1=left().max_range(l,r);
int mx2=right().max_range(l,r);
return max(mx1,mx2);
}
};
int main(){
node root(1,6,1);
int m;
cin>>m;
for(int i=1;i<=m;i++){
int a,b,c;
cin>>a>>b>>c;
root.assign_range(a,b,c);
cout<<root.max_range(1,6)<<"\n";
}
}
I managed to make a solution with segment trees using kien_coi_1997 style, but it doesn't work properly. My idea is the following: when a interval (ll,rr) fits in the query interval, increase the maximum with c and update all nodes of the tree up to the root. I'm not sure when I need to put lazy_update and therefore i got WA on the following test case. In the code above after each query of the first type I output the maximal among all elements.
12
1 1 1
2 2 2
3 3 3
4 4 4
5 5 5
6 6 6
1 3 4
3 6 -2
1 2 -2
3 3 -2
2 5 3
2 4 -2
If you write on a sheet of paper the above test, you will see that after the last query my program outputs 5 but the answer is 6. Any help will be highly appreciated :").
P.S. If you are wondering why my code looks a bit "strange", that's because it's a part of the following task. It is really interesting and I could explain a solution to everyone who wants to hear it.
UPD. The task was solved. The code above was updated.
