PROBLEM LINK:
Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4
Setter: Kerim Kochekov
Tester: Satyam, Utkarsh Gupta
Editorialist: Devendra Singh
DIFFICULTY:
To be calculated
PREREQUISITES:
Lazy Propagation, Segment tree
PROBLEM:
The princess of Shamakhi is trying to find the source of eternal youth so she can restore her lost beauty. It turns out that she needs to collect the tears of a thousand beautiful maidens. To do that, she will accomplish a serious mission with three Bogatyrs, more precisely, update one of their assigned arrays within Q queries, and after each update, she wants to know the power of the Bogatyrs.
More formally, there are three Bogatyrs, each with their own array of N integers — named A, B, and C respectively. The princess of Shamakhi has Q updates of the form (t, pos, val), whose details are as follows:
- If t=1, then assign A_{pos} = val
- If t=2, then assign B_{pos} = val
- If t=3, then assign C_{pos} = val
After every update, you need to find the power of the Bogatyrs (P), which is calculated as follows:
P = \max_{1\le L \le R \le N}(a(L-1)+b(L,R)+c(R+1))
Here, the functions a, b, and c are defined as:
- If 1\le x \le N, then a(x) = \sum^x_{i=1}A_i, otherwise a(x) = 0.
- if 1\le x \le y \le N, then b(x,y) = \sum^y_{i=x}B_i, otherwise b(x,y) = 0.
- if 1\le x \le N, then c(x) = \sum^N_{i=x}C_i, otherwise c(x) = 0.
Can you help the princess of Shamakhi to restore her lost beauty by finding the power P of the three Bogatyrs after each update?
EXPLANATION:
Let array P keep the prefix sums for array A, more specifically P_i =A_1+...+A_i, and array M keep the prefix sums for array B, more specifically M_i=B_1+...+B_i and array S keep the suffix sums for array C, more specifically S_i=C_i+...+C_N.
Then the power of the Bogatyrs is the maximum value of P_{l-1}+(M_{r}-M_{l-1})+S_{r+1} for some 1\leq l< r\leq N. Let us simplify the formula, P_{l-1}+(M_{r}-M_{l-1})+S_{r+1} = (P_{l-1}-M_{l-1})+(M_{r}+S_{r+1}).
Let us compute two new arrays D,\: E, where D_i = P_{i}-M_{i} for 1\leq i\leq N, E_i = M_i + S_{i+1} for 1\leq i\leq N. The problem now reduces to maximize the value of D_l+E_r for 1\leq l< r\leq N. This can be done with the help of segment tree, where each node of segment tree keeps the maximum possible value of D_l+E_r (satisfying l<r), maximum value of D array in the range, maximum value of E array in the range. Now it remains how to efficiently update these D,E arrays for each type of query.
Updating some position of A array influences the suffix of D. More specifically if we update A_{pos} with val then each value in the suffix D starting from pos is increased by val-A_{pos}(decreased if this value is negative).
Updating some position of B array influences the suffix of D and E array.
More specifically if we update B_{pos} with val then each value in the suffix D starting from pos is increased by B_{pos}-val (decreased if this value is negative) and suffix E starting from pos is increased by val-B_{pos} (decreased if this value is negative)
Updating some position of C array influences the prefix of E array. More specifically if we update C_{pos} with val then each value in the prefix of E ending at pos-1 is increased by val-C_{pos}(decreased if this value is negative).
As a result, we need to keep two separate lazy propagation arrays for D and E arrays to deal with range addition updates for D and E.
The answer after each query would be the maximum value of D_L+E_R stored in the root node of the segment tree
For details of implementation, please refer to the solutions attached.
TIME COMPLEXITY:
O((N+Q)\cdot\log(N)) or for each test case.
SOLUTION:
Setter's Solution
#include "bits/stdc++.h"
#define MAXN 100009
#define INF 1000000007
#define mp(x,y) make_pair(x,y)
#define all(v) v.begin(),v.end()
#define pb(x) push_back(x)
#define wr cout<<"----------------"<<endl;
#define ppb() pop_back()
#define tr(ii,c) for(__typeof((c).begin()) ii=(c).begin();ii!=(c).end();ii++)
#define ff first
#define ss second
#define my_little_dodge 46
#define debug(x) cerr<< #x <<" = "<< x<<endl;
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
template<class T>bool umin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
template<class T>bool umax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
int a[MAXN],b[MAXN],c[MAXN];
int n,q;
ll A[MAXN],B[MAXN],C[MAXN];
struct node{
ll ans;
ll max_d,max_e;
}st[MAXN<<2];
ll lazy_e[MAXN<<2],lazy_d[MAXN<<2];
node merge(node x,node y){
node z;
z.ans=max(x.ans,y.ans);
umax(z.ans,x.max_d+y.max_e);
z.max_d=max(x.max_d,y.max_d);
z.max_e=max(x.max_e,y.max_e);
return z;
}
void shift(int nd){
ll &ret=lazy_d[nd],&pet=lazy_e[nd];
st[nd<<1].ans+=ret+pet;
st[nd<<1|1].ans+=ret+pet;
st[nd<<1].max_d+=ret;
lazy_d[nd<<1]+=ret;
st[nd<<1|1].max_d+=ret;
lazy_d[nd<<1|1]+=ret;
st[nd<<1].max_e+=pet;
lazy_e[nd<<1]+=pet;
st[nd<<1|1].max_e+=pet;
lazy_e[nd<<1|1]+=pet;
ret=0;pet=0;
}
void inc(int l,int r,int t,int val,int nd=1,int x=0,int y=n){
if(l>y or x>r or l>r)return;
if(l<=x and y<=r){
if(!t)st[nd].max_d+=val,lazy_d[nd]+=val;
else st[nd].max_e+=val,lazy_e[nd]+=val;
st[nd].ans+=val;
return;
}
shift(nd);
int mid=(x+y)>>1;
inc(l,r,t,val,nd<<1,x,mid);
inc(l,r,t,val,nd<<1|1,mid+1,y);
st[nd]=merge(st[nd<<1],st[nd<<1|1]);
}
void build(int nd=1,int x=0,int y=n){
if(x==y){
st[nd].ans=0;
st[nd].max_d=A[x]-B[x];
st[nd].max_e=C[x+1]+B[x];
return;
}
int mid=(x+y)>>1;
build(nd<<1,x,mid);
build(nd<<1|1,mid+1,y);
st[nd]=merge(st[nd<<1],st[nd<<1|1]);
}
int main(){
//~ freopen("file.in","r",stdin);
scanf("%d%d",&n,&q);
for(int i=1;i<=n;i++)scanf("%d",a+i),A[i]=A[i-1]+a[i];
for(int i=1;i<=n;i++)scanf("%d",b+i),B[i]=B[i-1]+b[i];
for(int i=1;i<=n;i++)scanf("%d",c+i);
for(int i=n;i>=1;i--)C[i]=C[i+1]+c[i];
build();
while(q--){
int t,pos,val;
scanf("%d%d%d",&t,&pos,&val);
if(t==1)inc(pos,n,0,val-a[pos]),a[pos]=val;
if(t==2)inc(pos,n,0,b[pos]-val),inc(pos,n,1,val-b[pos]),b[pos]=val;
if(t==3)inc(1,pos-1,1,val-c[pos]),c[pos]=val;
printf("%lld\n",st[1].ans);
}
return 0;
}
Tester-1's Solution
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
#define ll long long
const ll INF_MUL=1e13;
const ll INF_ADD=1e18;
#define pb push_back
#define mp make_pair
#define nline "\n"
#define f first
#define s second
#define pll pair<ll,ll>
#define all(x) x.begin(),x.end()
#define vl vector<ll>
#define vvl vector<vector<ll>>
#define vvvl vector<vector<vector<ll>>>
#ifndef ONLINE_JUDGE
#define debug(x) cerr<<#x<<" "; _print(x); cerr<<nline;
#else
#define debug(x);
#endif
void _print(ll x){cerr<<x;}
void _print(char x){cerr<<x;}
void _print(string x){cerr<<x;}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
template<class T,class V> void _print(pair<T,V> p) {cerr<<"{"; _print(p.first);cerr<<","; _print(p.second);cerr<<"}";}
template<class T>void _print(vector<T> v) {cerr<<" [ "; for (T i:v){_print(i);cerr<<" ";}cerr<<"]";}
template<class T>void _print(set<T> v) {cerr<<" [ "; for (T i:v){_print(i); cerr<<" ";}cerr<<"]";}
template<class T>void _print(multiset<T> v) {cerr<< " [ "; for (T i:v){_print(i);cerr<<" ";}cerr<<"]";}
template<class T,class V>void _print(map<T, V> v) {cerr<<" [ "; for(auto i:v) {_print(i);cerr<<" ";} cerr<<"]";}
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
typedef tree<ll, null_type, less_equal<ll>, rb_tree_tag, tree_order_statistics_node_update> ordered_multiset;
typedef tree<pair<ll,ll>, null_type, less<pair<ll,ll>>, rb_tree_tag, tree_order_statistics_node_update> ordered_pset;
//--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
const ll MOD=1e9+7;
const ll MAX=100100;
ll n,q;
vector<vector<ll>> a(4,vector<ll>(MAX,0));
vector<vector<ll>> pref(4,vector<ll>(MAX,0));
vector<vector<ll>> prop(4*MAX,vector<ll>(4,0));
vector<vector<ll>> segt(4*MAX,vector<ll>(4,-INF_ADD));
vector<ll> combine(vector<ll> l,vector<ll> r){
vector<ll> now(4,-INF_ADD);
for(ll i=1;i<=3;i++){
now[i]=max({now[i],l[i],r[i]});
}
now[3]=max({now[3],l[1]+r[2]});
return now;
}
void build(ll v,ll l,ll r){
if(l>r){
return;
}
if(l==r){
segt[v][1]=pref[1][l]-pref[2][l];
segt[v][2]=pref[3][n+1]-pref[3][l]+pref[2][l];
return;
}
ll m=(l+r)/2;
build(2*v,l,m); build(2*v+1,m+1,r);
segt[v]=combine(segt[2*v],segt[2*v+1]);
}
void push(ll v){
ll l=2*v,r=2*v+1;
for(ll i=1;i<=3;i++){
for(ll j=1;j<=2;j++){
if(i&j){
segt[l][i]+=prop[v][j],prop[l][i]+=prop[v][j];
segt[r][i]+=prop[v][j],prop[r][i]+=prop[v][j];
}
}
}
prop[v][1]=prop[v][2]=0;
}
void update(ll v,ll tl,ll tr,ll l,ll r,ll delta,ll par){
if(l>r)
return;
if((l==tl)&&(r==tr)){
segt[v][par]+=delta,prop[v][par]+=delta,segt[v][3]+=delta;
}
else{
push(v); ll tm=(tl+tr)/2;
update(v*2,tl,tm,l,min(r,tm),delta,par);
update(v*2+1,tm+1,tr,max(l,tm+1),r,delta,par);
segt[v]=combine(segt[v*2],segt[v*2+1]);
}
return;
}
void solve(){
cin>>n>>q;
for(ll i=1;i<=3;i++){
for(ll j=1;j<=n;j++){
cin>>a[i][j]; pref[i][j]+=pref[i][j-1]+a[i][j];
}
pref[i][n+1]=pref[i][n];
}
build(1,0,n);
while(q--){
ll t,p,v; cin>>t>>p>>v;
if(t==1){
update(1,0,n,p,n,v-a[t][p],1);
}
else if(t==2){
update(1,0,n,p,n,a[t][p]-v,1),update(1,0,n,p,n,v-a[t][p],2);
}
else{
update(1,0,n,1,p-1,v-a[t][p],2);
}
a[t][p]=v;
cout<<segt[1][3]<<nline;
}
return;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
freopen("error.txt", "w", stderr);
#endif
ll test_cases=1;
//cin>>test_cases;
while(test_cases--){
solve();
}
cout<<fixed<<setprecision(10);
cerr<<"Time:"<<1000*((double)clock())/(double)CLOCKS_PER_SEC<<"ms\n";
}
Tester-2's Solution
//Utkarsh.25dec
#include <bits/stdc++.h>
#define ll long long int
#define pb push_back
#define mp make_pair
#define mod 1000000007
#define vl vector <ll>
#define all(c) (c).begin(),(c).end()
using namespace std;
ll power(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll modInverse(ll a){return power(a,mod-2);}
const int N=500023;
bool vis[N];
vector <int> adj[N];
long long readInt(long long l,long long r,char endd){
long long x=0;
int cnt=0;
int fi=-1;
bool is_neg=false;
while(true){
char g=getchar();
if(g=='-'){
assert(fi==-1);
is_neg=true;
continue;
}
if('0'<=g && g<='9'){
x*=10;
x+=g-'0';
if(cnt==0){
fi=g-'0';
}
cnt++;
assert(fi!=0 || cnt==1);
assert(fi!=0 || is_neg==false);
assert(!(cnt>19 || ( cnt==19 && fi>1) ));
} else if(g==endd){
if(is_neg){
x= -x;
}
if(!(l <= x && x <= r))
{
cerr << l << ' ' << r << ' ' << x << '\n';
assert(1 == 0);
}
return x;
} else {
assert(false);
}
}
}
string readString(int l,int r,char endd){
string ret="";
int cnt=0;
while(true){
char g=getchar();
assert(g!=-1);
if(g==endd){
break;
}
cnt++;
ret+=g;
}
assert(l<=cnt && cnt<=r);
return ret;
}
long long readIntSp(long long l,long long r){
return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
return readInt(l,r,'\n');
}
string readStringLn(int l,int r){
return readString(l,r,'\n');
}
string readStringSp(int l,int r){
return readString(l,r,' ');
}
ll P[N], Q[N];
ll maxiP[4*N];
ll lazyP[4*N];
ll maxiQ[4*N];
ll lazyQ[4*N];
ll lazyprefC[4*N];
ll opt[4*N];
ll lazyopt[4*N];
void build(int v,int tl,int tr)
{
if(tl>tr)
return;
if(tl==tr)
{
lazyP[v]=0;
lazyQ[v]=0;
lazyprefC[v]=0;
lazyopt[v]=0;
maxiP[v]=P[tl];
maxiQ[v]=Q[tl];
opt[v]=-1e18;
return;
}
ll mid=(tl+tr)/2;
build(2*v,tl,mid);
build(2*v+1,mid+1,tr);
maxiP[v]=max(maxiP[2*v],maxiP[2*v+1]);
lazyP[v]=0;
maxiQ[v]=max(maxiQ[2*v],maxiQ[2*v+1]);
lazyQ[v]=0;
lazyprefC[v]=0;
opt[v]=max({opt[2*v],opt[2*v+1],maxiP[2*v]+maxiQ[2*v+1]});
}
void push(int v)
{
lazyQ[2*v]+=lazyQ[v];
lazyQ[2*v+1]+=lazyQ[v];
maxiQ[v]+=lazyQ[v];
lazyQ[v]=0;
lazyP[2*v]+=lazyP[v];
lazyP[2*v+1]+=lazyP[v];
maxiP[v]+=lazyP[v];
lazyP[v]=0;
lazyopt[2*v]+=lazyopt[v];
lazyopt[2*v+1]+=lazyopt[v];
opt[v]+=lazyopt[v];
lazyopt[v]=0;
}
void updateopt(int v,int tl,int tr,int l,int r,int val,int type)
{
if(tl>tr)
return;
if(tl!=tr)
push(v);
maxiQ[v]+=lazyQ[v];
maxiP[v]+=lazyP[v];
if(tl!=tr)
opt[v]+=lazyopt[v];
lazyQ[v]=0;
lazyP[v]=0;
lazyopt[v]=0;
if(tl>r || tr<l)
return;
if(tl>=l && tr<=r)
{
if(type==1)
{
lazyP[v]+=val;
lazyopt[v]+=val;
}
else if(type==2)
{
lazyP[v]-=val;
lazyQ[v]+=val;
}
else
{
lazyQ[v]-=val;
lazyopt[v]-=val;
}
if(tl!=tr)
push(v);
maxiQ[v]+=lazyQ[v];
maxiP[v]+=lazyP[v];
if(tl!=tr)
opt[v]+=lazyopt[v];
lazyQ[v]=0;
lazyP[v]=0;
lazyopt[v]=0;
return;
}
ll mid=(tl+tr)/2;
updateopt(2*v,tl,mid,l,r,val,type);
updateopt(2*v+1,mid+1,tr,l,r,val,type);
maxiQ[v]=max(maxiQ[2*v],maxiQ[2*v+1]);
maxiP[v]=max(maxiP[2*v],maxiP[2*v+1]);
opt[v]=max({opt[2*v],opt[2*v+1],maxiP[2*v]+maxiQ[2*v+1]});
}
void solve()
{
int n,q;
n=readInt(1,100000,' ');
q=readInt(1,100000,'\n');
n++;
ll A[n+1]={0},B[n+1]={0},C[n+1]={0};
ll totalsumC=0;
for(int i=2;i<=n;i++)
{
if(i==n)
A[i]=readInt(1,1000000000,'\n');
else
A[i]=readInt(1,1000000000,' ');
}
for(int i=2;i<=n;i++)
{
if(i==n)
B[i]=readInt(1,1000000000,'\n');
else
B[i]=readInt(1,1000000000,' ');
}
for(int i=2;i<=n;i++)
{
if(i==n)
C[i]=readInt(1,1000000000,'\n');
else
C[i]=readInt(1,1000000000,' ');
}
ll prefA[n+1]={0},prefB[n+1]={0},prefC[n+1]={0};
for(int i=1;i<=n;i++)
{
prefA[i]=prefA[i-1]+A[i];
prefB[i]=prefB[i-1]+B[i];
prefC[i]=prefC[i-1]+C[i];
totalsumC+=C[i];
}
for(int i=1;i<=n;i++)
{
P[i]=prefA[i]-prefB[i];
Q[i]=prefB[i]-prefC[i];
}
build(1,1,n);
while(q--)
{
int t,pos,val;
t=readInt(1,3,' ');
pos=readInt(1,n,' ');
val=readInt(1,1000000000,'\n');
pos++;
if(t==1)
{
updateopt(1,1,n,pos,n,val-A[pos],1);
A[pos]=val;
}
else if(t==2)
{
updateopt(1,1,n,pos,n,val-B[pos],2);
B[pos]=val;
}
else
{
updateopt(1,1,n,pos,n,val-C[pos],3);
totalsumC+=(val-C[pos]);
C[pos]=val;
}
cout<<(opt[1]+totalsumC)<<'\n';
}
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
ios_base::sync_with_stdio(false);
cin.tie(NULL),cout.tie(NULL);
int T=1;
while(T--)
solve();
// assert(getchar()==-1);
cerr << "Time : " << 1000 * ((double)clock()) / (double)CLOCKS_PER_SEC << "ms\n";
}
Editorialist's Solution
#include "bits/stdc++.h"
using namespace std;
#define ll long long
#define pb push_back
#define all(_obj) _obj.begin(), _obj.end()
#define F first
#define S second
#define pll pair<ll, ll>
#define vll vector<ll>
ll INF = 1e18;
const int N = 1e5 + 11, mod = 1e9 + 7;
ll max(ll a, ll b) { return ((a > b) ? a : b); }
ll min(ll a, ll b) { return ((a > b) ? b : a); }
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
using namespace std;
int a[N], b[N], c[N];
ll P[N], M[N], S[N];
struct node
{
ll ans, max_d, max_e;
} st[N << 2];
ll lazy_e[N << 2], lazy_d[N << 2];
node combine(node left, node right)
{
node root;
root.ans = max(left.ans, right.ans);
root.ans = max(left.max_d + right.max_e, root.ans);
root.max_d = max(left.max_d, right.max_d);
root.max_e = max(left.max_e, right.max_e);
return root;
}
void shift(int nd)
{
ll &x = lazy_d[nd], &y = lazy_e[nd];
st[nd << 1].ans += x + y;
st[nd << 1 | 1].ans += x + y;
st[nd << 1].max_d += x;
lazy_d[nd << 1] += x;
st[nd << 1 | 1].max_d += x;
lazy_d[nd << 1 | 1] += x;
st[nd << 1].max_e += y;
lazy_e[nd << 1] += y;
st[nd << 1 | 1].max_e += y;
lazy_e[nd << 1 | 1] += y;
x = 0;
y = 0;
}
void update(int l, int r, int t, int val, int nd, int x, int y)
{
if (l > y or x > r or l > r)
return;
if (l <= x and y <= r)
{
if (!t)
st[nd].max_d += val, lazy_d[nd] += val;
else
st[nd].max_e += val, lazy_e[nd] += val;
st[nd].ans += val;
return;
}
shift(nd);
int mid = (x + y) >> 1;
update(l, r, t, val, nd << 1, x, mid);
update(l, r, t, val, nd << 1 | 1, mid + 1, y);
st[nd] = combine(st[nd << 1], st[nd << 1 | 1]);
}
void build(int nd, int x, int y)
{
if (x == y)
{
st[nd].ans = 0;
st[nd].max_d = P[x] - M[x]; // D array
st[nd].max_e = S[x + 1] + M[x]; // E array
return;
}
int mid = (x + y) >> 1;
build(nd << 1, x, mid);
build(nd << 1 | 1, mid + 1, y);
st[nd] = combine(st[nd << 1], st[nd << 1 | 1]);
}
void sol(void)
{
int n, q;
cin >> n >> q;
for (int i = 1; i <= n; i++)
cin >> a[i], P[i] = P[i - 1] + a[i];
for (int i = 1; i <= n; i++)
cin >> b[i], M[i] = M[i - 1] + b[i];
for (int i = 1; i <= n; i++)
cin >> c[i];
for (int i = n; i >= 1; i--)
S[i] = S[i + 1] + c[i];
build(1, 0, n);
while (q--)
{
int t, pos, val;
cin >> t >> pos >> val;
// 0 for array D and 1 for array E
if (t == 1)
update(pos, n, 0, val - a[pos], 1, 0, n), a[pos] = val;
if (t == 2)
update(pos, n, 0, b[pos] - val, 1, 0, n), update(pos, n, 1, val - b[pos], 1, 0, n), b[pos] = val;
if (t == 3)
update(1, pos - 1, 1, val - c[pos], 1, 0, n), c[pos] = val;
cout << st[1].ans << '\n';
}
return;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int test = 1;
// cin>>test;
while (test--)
sol();
}