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:
- Given x and y, find the maximum sum of B[l, r] such that l\le x \le y \le r.
- 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 