1093G - Multidimensional Queries - CodeForces Solution

/* in the name of allah */
#include<bits/stdc++.h>
using namespace std;

#define endl '\n'
#define pb push_back
#define F first
#define S second
#define mk make_pair
#define ln (e-s+1)
#define md ((s+e)/2)
#define lc (id*2)
#define rc (id*2+1)
typedef long long ll;

const int N=2e5+7;
int n,k,seg[4*N][1<<5],a[N][5],mx[1<<5];

void build(int id=1,int s=1,int e=n){
	if(ln==1){
		for(int i=0;i<(1<<k);i++){
			for(int j=0;j<k;j++){
				if(i>>j&1)seg[id][i]+=a[s][j];
				else seg[id][i]-=a[s][j];
			}
		}
		return;
	}
	build(lc,s,md);
	build(rc,md+1,e);
	for(int i=0;i<(1<<k);i++){
		seg[id][i]=max(seg[lc][i],seg[rc][i]);
	}
}

void upd(int ind,int id=1,int s=1,int e=n){
	if(ln==1){
		for(int i=0;i<(1<<k);i++){
			seg[id][i]=0;
			for(int j=0;j<k;j++){
				if(i>>j&1)seg[id][i]+=a[s][j];
				else seg[id][i]-=a[s][j];
			}
		}
		return;
	}
	if(ind<=md)upd(ind,lc,s,md);
	else upd(ind,rc,md+1,e);
	for(int i=0;i<(1<<k);i++){
		seg[id][i]=max(seg[lc][i],seg[rc][i]);
	}
}

void get(int l,int r,int id=1,int s=1,int e=n){
	if(s>r || e<l)return;
	if(s>=l && e<=r){
		if(s==l){
			for(int i=0;i<(1<<k);i++)mx[i]=seg[id][i];
		}
		else{
			for(int i=0;i<(1<<k);i++)mx[i]=max(mx[i],seg[id][i]);
		}
		return;
	}
	get(l,r,lc,s,md);
	get(l,r,rc,md+1,e);
}

int main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>n>>k;
	for(int i=1;i<=n;i++){
		for(int j=0;j<k;j++){
			cin>>a[i][j];
		}
	}
	build();
	int q;
	cin>>q;
	while(q--){
		int t,l,r,x;
		cin>>t;
		if(t==1){
			cin>>x;
			for(int i=0;i<k;i++){
				cin>>a[x][i];
			}
			upd(x);
		}
		else{
			cin>>l>>r;
			get(l,r);
			int ans=0;
			for(int i=0;i<(1<<k);i++){
				ans=max(ans,mx[i]+mx[(1<<k)-1-i]);
				//cout<<i<<" "<<mx[i]<<endl;
			}
			cout<<ans<<endl;
		}
	}
}