CF1093G Multidimensional Queries

题目链接

思路：把题目中的绝对值式子拆开
那么答案就是
$max\{\sum _{i=1}^k{a}_i\ast Q_i+\sum _{i=1}^k{b}_i\ast Q_i,Q_i\in \{1,-1\left\}\right\}\because k\le 5$max{  i=1∑k​ai​∗Qi​+i=1∑k​bi​∗Qi​,Qi​∈{1,−1}  }∵k≤5
那么建 $2^k$2k个维护最大最小值的线段树即可。

细节见代码：

#include<bits/stdc++.h>
 
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define LL long long
#define pii pair<int,int>
#define SZ(x) (int)x.size()
#define all(x) x.begin(),x.end()
 
using namespace std;
 
LL gcd(LL a, LL b) {return b ? gcd(b, a % b) : a;}
LL lcm(LL a, LL b) {return a / gcd(a, b) * b;}
LL powmod(LL a, LL b, LL MOD) {LL ans = 1; while (b) {if (b % 2)ans = ans * a % MOD; a = a * a % MOD; b /= 2;} return ans;}
const int N = 2e5 + 3;
const LL mod = 1e9 + 7;
struct uzi{
    LL l,r;
}t[33][N<<2];
int m,q,n,k;
int a[N][10];
LL b[33][N];
#define mid (l+r>>1)
#define ls o<<1
#define rs o<<1|1
void ud(int o,int l,int r){
    for(int x=0;x<(1<<k);x++){
        t[x][o].l=min(t[x][ls].l,t[x][rs].l);
        t[x][o].r=max(t[x][ls].r,t[x][rs].r);
    }
}
void build(int o,int l,int r){
    if(l==r){
        for(int i=0;i<(1<<k);i++){
            for(int j=0;j<k;j++){
                LL res=a[l][j+1];
                if(i&(1<<j)){
                    res*=-1;
                }
                b[i][l]+=res;
            }
            t[i][o].l=t[i][o].r=b[i][l];
        }
        return ;
    }
    build(ls,l,mid);
    build(rs,mid+1,r);
    ud(o,l,r);
}
int Q[10];
void update(int o,int l,int r,int pos){
    if(l==r){
        for(int i=0;i<(1<<k);i++)b[i][l]=0;
        for(int i=0;i<(1<<k);i++){
            for(int j=0;j<k;j++){
                LL res=Q[j+1];
                if(i&(1<<j))res*=-1;
                b[i][l]+=res;
            }
            t[i][o].l=t[i][o].r=b[i][l];
        }
        return ;
    }
    if(pos<=mid)update(ls,l,mid,pos);
    else update(rs,mid+1,r,pos);
    ud(o,l,r);
}
LL MAX,MIN;
void get(int x,int o,int l,int r,int Q,int P){
    if(Q<=l&&P>=r){
        MAX=max(MAX,t[x][o].r);
        MIN=min(MIN,t[x][o].l);
        return ;
    }
    if(Q<=mid)get(x,ls,l,mid,Q,P);
    if(P>mid)get(x,rs,mid+1,r,Q,P);
}
int main() {
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=k;j++)scanf("%d",&a[i][j]);
    }
    build(1,1,n);
    scanf("%d",&q);
    for(int i=1;i<=q;i++){
        int sta;
        scanf("%d",&sta);
        if(sta==1){
            int x;
            scanf("%d",&x);
            for(int j=1;j<=k;j++)scanf("%d",&Q[j]);
            update(1,1,n,x);
        }else{
            int l,r;
            MAX=LLONG_MIN,MIN=LLONG_MAX;
            scanf("%d%d",&l,&r);
            LL ans=0;
            for(int G=0;G<(1<<k);G++)get(G,1,1,n,l,r),ans=max(ans,MAX-MIN),MAX=LLONG_MIN,MIN=LLONG_MAX;
            printf("%lld\n",ans);
        }
    }
	return 0;
}