MAXBTY - Editorial

PROBLEM LINK:

Practice
Div-2 Contest
Div-1 Contest

Author: Anik Sarker
Tester: Raja Vardhan Reddy
Editorialist: William Lin

DIFFICULTY:

Easy

PREREQUISITES:

Prefix sums, Segment tree

PROBLEM:

You are given an array B of length N and Q queries of two types:

  1. Given x and y, find the maximum sum of B[l, r] such that l\le x \le y \le r.
  2. Given x and v, update B_x to v.

QUICK EXPLANATION:

Maintain a segment tree of prefix sums and another segment tree of negative prefix sums. Query 1 is the range max of a suffix of the first segment tree added to the range max of a prefix of the second segment tree. Query 2 is a range add update on the suffix of both segment trees.

EXPLANATION:

Let C_i be the sum of the first i elements of B (the prefix sum array of B). Whenever we process query 2, all C_i such that i \ge x increase by v-B_x (since all prefixes with at least x elements will contain the x-th element of B and be updated), so we can maintain all C_i by using a data structure which supports range add updates, such as a segment tree.

The sum of B[l, r] is equivalent to C_r-C_{l-1}. So, we want to find the maximum value of C_r-C_{l-1} given that l \le r, l \le x, and y \le r. Notice that x\le y, so we can ignore the condition l \le r. Now, l and r are independent, so we can focus on maximizing C_r and -C_{l-1} independently.

Finding the maximum value of C_r given that r \ge y equivalent to a range maximum query on C[y, n], which we can perform efficiently with a segment tree. Finding the maximum value of -C_{l-1} is not much different: we will have another segment tree maintaining the negative prefix sums, and to answer queries of type 1, we just need to perform a range maximum query on -C[0, x-1].

SOLUTIONS:

Setter's Solution
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
const int maxn = 100005;
 
namespace SegmentTree{
    #define Left (node*2)
    #define Right (node*2+1)
    #define mid ((lo+hi)/2)
 
    ll lazy[maxn*5];
    ll minTree[maxn*5];
    ll maxTree[maxn*5];
 
    void build(int node, int lo, int hi){
        minTree[node] = maxTree[node] = lazy[node] = 0;
        if(lo == hi) return;
        build(Left, lo, mid);
        build(Right, mid+1, hi);
    }
 
    void lazyPropagation(int node, int lo, int hi){
        minTree[node] += lazy[node]; maxTree[node] += lazy[node];
        if(lo != hi) {lazy[Left] += lazy[node]; lazy[Right] += lazy[node];}
        lazy[node] = 0;
    }
 
    void updateRange(int node, int lo, int hi, int i, int j, ll val){
        lazyPropagation(node,lo,hi);
        if(lo>hi || lo>j || hi<i) return;
        if(lo>=i && hi<=j) {lazy[node] += val; lazyPropagation(node,lo,hi); return;}
        updateRange(Left,lo,mid,i,j,val);
        updateRange(Right,mid+1,hi,i,j,val);
        minTree[node] = min(minTree[Left], minTree[Right]);
        maxTree[node] = max(maxTree[Left], maxTree[Right]);
    }
 
    ll queryMax(int node, int lo, int hi, int i, int j){
        if(lo>hi || lo>j || hi<i) return LLONG_MIN;
        lazyPropagation(node,lo,hi);
        if(lo>=i && hi<=j) return maxTree[node];
        ll p1 = queryMax(Left, lo, mid,i,j);
        ll p2 = queryMax(Right,mid+1,hi,i,j);
        return max(p1, p2);
    }
 
    ll queryMin(int node, int lo, int hi, int i, int j){
        if(lo>hi || lo>j || hi<i) return 0;
        lazyPropagation(node,lo,hi);
        if(lo>=i && hi<=j) return minTree[node];
        ll p1 = queryMin(Left, lo, mid,i,j);
        ll p2 = queryMin(Right,mid+1,hi,i,j);
        return min(p1, p2);
    }
}
using namespace SegmentTree;
 
ll a[maxn];
int main(){
    int t;
    scanf("%d", &t);
 
    for(int cs=1; cs<=t; cs++){
        int n, q;
        scanf("%d %d", &n, &q);
        
        build(1, 1, n);
        for(int i=1; i<=n; i++){
            scanf("%lld", &a[i]);
            updateRange(1, 1, n, i, n, a[i]);
        }
 
        for(int i=1; i<=q; i++){
            char cmd;
            scanf(" %c", &cmd);
 
            if(cmd == 'U'){
                int x; ll y;
                scanf("%d %lld",&x, &y);
                updateRange(1, 1, n, x, n, y - a[x]);
                a[x] = y;
            }
            else{
                int l, r;
                scanf("%d %d",&l, &r);
                ll ret = queryMax(1, 1, n, r, n);
                ret -= queryMin(1, 1, n, 1, l-1);
                printf("%lld\n", ret);
            }
        }
    }
}
Tester's Solution
//raja1999
 
//#pragma comment(linker, "/stack:200000000")
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2")
 
#include <bits/stdc++.h>
#include <vector>
#include <set>
#include <map>
#include <string> 
#include <cstdio>
#include <cstdlib>
#include <climits>
#include <utility>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <iomanip> 
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp> 
//setbase - cout << setbase (16)a; cout << 100 << endl; Prints 64
//setfill -   cout << setfill ('x') << setw (5); cout << 77 <<endl;prints xxx77
//setprecision - cout << setprecision (14) << f << endl; Prints x.xxxx
//cout.precision(x)  cout<<fixed<<val;  // prints x digits after decimal in val
 
using namespace std;
using namespace __gnu_pbds;
#define f(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) f(i,0,n)
#define fd(i,a,b) for(i=a;i>=b;i--)
#define pb push_back
#define mp make_pair
#define vi vector< int >
#define vl vector< ll >
#define ss second
#define ff first
#define ll long long
#define pii pair< int,int >
#define pll pair< ll,ll >
#define sz(a) a.size()
#define inf (1000*1000*1000+5)
#define all(a) a.begin(),a.end()
#define tri pair<int,pii>
#define vii vector<pii>
#define vll vector<pll>
#define viii vector<tri>
#define mod (1000*1000*1000+7)
#define pqueue priority_queue< int >
#define pdqueue priority_queue< int,vi ,greater< int > >
#define int ll
 
typedef tree<
int,
null_type,
less<int>,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;
 
 
//std::ios::sync_with_stdio(false);
int iinf;
int lazy[512345],st[512345][2];
int a[112345],b[112345];
 
int build(int s,int e,int node){
	lazy[node]=0;
	if(s==e){
		st[node][0]=b[s];
		st[node][1]=b[s];
		return 0;
	}
	int mid=(s+e)/2;
	build(s,mid,2*node);
	build(mid+1,e,2*node+1);
	st[node][0]=max(st[2*node][0],st[2*node+1][0]);
	st[node][1]=min(st[2*node][1],st[2*node+1][1]);
	return 0;
}
int update(int s,int e,int node,int l,int r,int val){
	if(lazy[node]){
		st[node][0]+=lazy[node];
		st[node][1]+=lazy[node];
		if(s!=e){
			lazy[2*node]+=lazy[node];
			lazy[2*node+1]+=lazy[node];
		}
		lazy[node]=0;
	}
	if(s>r||e<l){
		return 0;
	}
	if(s>=l&&r>=e){
		st[node][0]+=val;
		st[node][1]+=val;
		if(s!=e){
			lazy[2*node]+=val;
			lazy[2*node+1]+=val;
		}
		return 0;
	}
	int mid=(s+e)/2;
	update(s,mid,2*node,l,r,val);
	update(mid+1,e,2*node+1,l,r,val);
	st[node][0]=max(st[2*node][0],st[2*node+1][0]);
	st[node][1]=min(st[2*node][1],st[2*node+1][1]);
	return 0;
}
 
int query(int s,int e,int node,int l,int r,int fl){
	if(lazy[node]){
		st[node][0]+=lazy[node];
		st[node][1]+=lazy[node];
		if(s!=e){
			lazy[2*node]+=lazy[node];
			lazy[2*node+1]+=lazy[node];
		}
		lazy[node]=0;
	}
	if(s>r||e<l){
		if(fl){
			return -1LL*iinf;
		}
		else{
			return iinf;
		}
	}
	if(s>=l&&e<=r){
		if(fl){
			return st[node][0];
		}
		else{
			return st[node][1];
		}
	}
	int mid=(s+e)/2;
	if(fl){
		return max(query(s,mid,2*node,l,r,fl),query(mid+1,e,2*node+1,l,r,fl));
	}
	else{
		return min(query(s,mid,2*node,l,r,fl),query(mid+1,e,2*node+1,l,r,fl));
	}
 
}
 
main(){
	std::ios::sync_with_stdio(false); cin.tie(NULL);
	int t;
	cin>>t;
	//t=1;
	while(t--){
		int n,q,i,x,y,val;
		char ch;
		iinf=inf;
		iinf*=inf;
		cin>>n>>q;
		rep(i,n){
			cin>>a[i];
			b[i]=i>0?b[i-1]+a[i]:a[i];
		}
		build(0,n-1,1);
		rep(i,q){
			cin>>ch>>x>>y;
			if(ch=='Q'){
				x--;
				y--;
				val=query(0,n-1,1,y,n-1,1);
				if(x!=0)
					val-=min(query(0,n-1,1,0,x-1,0),0LL);
				cout<<val<<endl;
			}
			else{
				x--;
				update(0,n-1,1,x,n-1,y-a[x]);
				a[x]=y;
			}
		}
	}
	return 0;
}
Editorialist's Solution
#include <bits/stdc++.h>
using namespace std;

#define ll long long

const int mxN=1e5;
int n, q, b[mxN];

struct segtree {
	ll a[1<<18]={}, b[1<<18]={};
	void app(int i, ll x) {
		a[i]+=x;
		b[i]+=x;
	}
	void psh(int i) {
		app(2*i, b[i]);
		app(2*i+1, b[i]);
		b[i]=0;
	}
	void upd(int l1, int r1, ll x, int i=1, int l2=0, int r2=n) {
		if(l1<=l2&&r2<=r1) {
			app(i, x);
			return;
		}
		int m2=(l2+r2)/2;
		psh(i);
		if(l1<=m2)
			upd(l1, r1, x, 2*i, l2, m2);
		if(m2<r1)
			upd(l1, r1, x, 2*i+1, m2+1, r2);
		a[i]=max(a[2*i], a[2*i+1]);
	}
	ll qry(int l1, int r1, int i=1, int l2=0, int r2=n) {
		if(l1<=l2&&r2<=r1)
			return a[i];
		int m2=(l2+r2)/2;
		psh(i);
		return max(l1<=m2?qry(l1, r1, 2*i, l2, m2):-1e18, m2<r1?qry(l1, r1, 2*i+1, m2+1, r2):-1e18);
	}
};

void solve() {
	//input
	cin >> n >> q;
	for(int i=0; i<n; ++i)
		cin >> b[i];

	segtree sr, sl;
	//init segtrees
	for(int i=0; i<n; ++i) {
		sr.upd(i+1, n, b[i]);
		sl.upd(i+1, n, -b[i]);
	}

	//queries
	for(int x, y; q--; ) {
		char qt;
		cin >> qt >> x >> y;
		if(qt=='Q') {
			//max suffix - min prefix
			cout << sr.qry(y, n)+sl.qry(0, x-1) << "\n";
		} else {
			sr.upd(x, n, y-b[x-1]);
			sl.upd(x, n, b[x-1]-y);
			b[x-1]=y;
		}
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int t;
	cin >> t;
	while(t--)
		solve();
}

Please give me suggestions if anything is unclear so that I can improve. Thanks :slight_smile:

21 Likes
#include<bits/stdc++.h>
#include<unordered_map>
#define M 1000000007
#define T 998244353
#define PI 3.142
#define ll long long
#define MAXN 100001


using namespace std;
ll tx[4*MAXN], tn[4*MAXN], lx[4*MAXN], ln[4*MAXN];
ll maxi(ll a, ll b)
{
    return (a>b)?a:b;
}
ll mini(ll a, ll b)
{
    return (a<b)?a:b;
}
void buildx(ll pre[], ll v, ll tl, ll tr)
{
    if(tl==tr){
        tx[v] = pre[tl];
    }
    else {
        ll tm = (tl+tr)/2;
        buildx(pre, 2*v, tl, tm);
        buildx(pre, 2*v+1, tm+1, tr);
        tx[v] = maxi(tx[2*v], tx[2*v+1]);
    }
}
void buildn(ll pre[], ll v, ll tl, ll tr)
{
    if(tl==tr){
        tn[v] = pre[tl];
    }
    else {
        ll tm = (tl+tr)/2;
        buildn(pre, 2*v, tl, tm);
        buildn(pre, 2*v+1, tm+1, tr);
        tn[v] = mini(tn[2*v], tn[2*v+1]);
    }
}
void pushx(ll v)
{
    tx[2*v] += lx[v];
    lx[2*v] += lx[v];
    tx[2*v+1] += lx[v];
    lx[2*v+1] += lx[v];
    lx[v]=0;
}
void pushn(ll v)
{
    tn[2*v] += ln[v];
    ln[2*v] += ln[v];
    tn[2*v+1] += ln[v];
    ln[2*v+1] += ln[v];
    ln[v]=0;
}
void updatex(ll v, ll tl, ll tr, ll l, ll r, ll add){
    if(l>r){
        return;
    }
    if(l==tl && tr==r){
        tx[v] += add;
        lx[v] += add;
    }
    else {
        pushx(v);
        ll tm = (tl+tr)/2;
        updatex(2*v, tl, tm, l, mini(r, tm), add);
        updatex(2*v+1, tm+1, tr, maxi(l, tm+1), r, add);
        tx[v] = maxi(tx[2*v], tx[2*v+1]);
    }
}
void updaten(ll v, ll tl, ll tr, ll l, ll r, ll add){
    if(l>r){
        return;
    }
    if(l==tl && tr==r){
        tn[v] += add;
        ln[v] += add;
    }
    else {
        pushn(v);
        ll tm = (tl+tr)/2;
        updaten(2*v, tl, tm, l, mini(r, tm), add);
        updaten(2*v+1, tm+1, tr, maxi(l, tm+1), r, add);
        tn[v] = mini(tn[2*v], tn[2*v+1]);
    }
}
ll qux(ll v, ll tl, ll tr, ll l, ll r)
{
    if(l>r){
        return INT64_MIN;
    }
    if(l==tl && r==tr){
        return tx[v];
    }
    pushx(v);
    ll tm = (tl+tr)/2;
    return maxi(qux(2*v, tl, tm, l, mini(r, tm)), qux(2*v+1, tm+1, tr, maxi(l, tm+1), r));
}
ll qun(ll v, ll tl, ll tr, ll l, ll r)
{
    if(l>r){
        return INT64_MAX;
    }
    if(l==tl && r==tr){
        return tn[v];
    }
    pushn(v);
    ll tm = (tl+tr)/2;
    return mini(qun(2*v, tl, tm, l, mini(r, tm)), qun(2*v+1, tm+1, tr, maxi(l, tm+1), r));
}
void solve()
{
    ll n, q, i, x, y, ans1, ans2, v, dif;
    cin >> n >> q;
    ll b[n], pre[n];
    for(i=0; i<n; i++){
        cin >> b[i];
    }
    pre[0]=b[0];
    for(i=1; i<n; i++){
        pre[i] = pre[i-1]+b[i];
    }
    buildx(pre, 1, 0, n-1);
    buildn(pre, 1, 0, n-1);
    for(i=0; i<q; i++){
        char ch;
        cin >> ch;
        if(ch=='Q'){
            cin >> x >> y;
            x--;
            y--;
            ans1 = qux(1, 0, n-1, y, n-1);
            ans2 = qun(1, 0, n-1, 0, x-1);
            if(ans2>0){
                ans2 = 0;
            }
            cout << ans1 - ans2 << "\n";
        }
        else {
            cin >> x >> v;
            x--;
            dif = v - b[x];
            b[x]=v;
            updatex(1, 0, n-1, x, n-1, dif);
            updaten(1, 0, n-1, x, n-1, dif);
        }
    }
}
signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif

    int _t;cin >> _t; while(_t--)
    solve();

    return 0;
}

The approach is just like the setter’s solution. I tried this code against my custom tests and it gives the correct answer yet I am getting WA. It seems I am missing an edge case. Please help me find out the mistake. And sorry if I have broken any guidelines it’s my first time on discuss.

Can Someone please help me out on this.
I’m not sure if my approach is wrong or i did some mistake in writing code. The Code seems clear and understandable for everyone. So please give it a look .
Link : https://www.codechef.com/viewsolution/30669623

Just set lazy arrays to zero for each test case.

2 Likes

Thanks got AC now. I feel stupid

can we do this question without segment tree i have used dp in this program but it give me tle

Hello,my code with ID 30677920 for MAXBTY is showig wrong ,can anyone help me find where I am
going wrong?

@tmwilliamlin Write down this kind of editorial for mysara question as well of march cookoff 2020 please

Can We use Fenwick trees for this problem?
I have some doubts in Update —>
U x v: Chef reevaluates the beauty of the letter from the x-th fan. The new value of Bx becomes v.

according to this statement: after U 1 1 result for query Q 2 4 must be 5

we have to replace current value of given array with v, right? in Fenwick tree at index x value will be updated as:

update(int *binaryIndexedTree,int value,int index,int n) //here x=index and v=value and value is passed as value=v-arr[x]; { while(index<=n) { binaryIndexedTree[index]+=value;
index+=index&(-index); }

1 Like

I tried solving this with Binary Indexed Tree. If someone has solved this using BIT then please let me know.

This question is quite similar to this problem. If one carefully notes
problem link:GSS1 spoj
Tutorial link:- A classical segment tree problem
Classical segment tree for maximum sum in a range.

My code for which I solved the MAXBTY problem:-
https://www.codechef.com/viewsolution/30686539

5 Likes

Core Idea is to use x=maximum suffix subarray sum in range 1 to x-1
and y=maximum prefix subarray sum in range y+1 to n and
z=sum of subarray x to y
by using these three values
output max(z,x+z,y+z,x+y+z) as answer.
For obtaining this value use segment tree nodes.

1 Like

https://www.codechef.com/viewsolution/30680648 Hey can anyone tell me what I am doing wrong. My approach is same as given in editorial maintaining two segment trees for positive and negative prefix sums . It really means a lot if anyone can help. Thanks for your time.

https://www.codechef.com/viewsolution/30687934
Can anyone help me with it?
My logic is same as tester’s soltution the only difference is 0based and 1 based index

https://www.codechef.com/viewsolution/30687418

Can someone tell me what is wrong with this solution?
I’m unable to figure it out.

can we do this question with help of binary indexed tree ( used in LAZER of March 2020 long challenge) instead of segment tree?

link of LAZER : https://www.codechef.com/MARCH20B/problems/LAZER

Definitely you can if you preserve prefix suffix and sum in a range as per above shared article by me.
In-fact The second question of div1 of previous cook off can also be done the same way. This cook offs and previous cook offs second question were almost similar quickly check both the questions.

1 Like

@jprm2 Can you explain lines 106-109?

LIne 106 :-node y1=query(1,0,n-1,0,l-2);
Querying range 1 to x-1 and getting a node.
Line 107: - node y2=query(1,0,n-1,r,n-1);
Querying range y+1 to n and getting a node
in each node y , y1 and y2 we have maximum prefix subarray sum , maximum suffix subarray sum , total sum of subarray
thus now we got all the things for all the three ranges that is 1 to x-1 x to y and y+1 to n
now

x=maximum suffix subarray sum in range 1 to x-1 obtain this from node y1
and y=maximum prefix subarray sum in range y+1 to n and obtain this from node y2
z=sum of subarray x to y and obtain this from node y
by using these three values
output max(z,x+z,y+z,x+y+z) as answer.