hello.

题解 CF1093G 【Multidimensional Queries】

2018-12-18 20:13:55


首发于 个人博客

思路

$i,j$ 之间的曼哈顿距离被定义为 $\sum |a_{i,k}-a_{j,k}|$。我们可以把式子拆开,每一维上 $a_i$ 和 $a_j$ 取值的正负性一定是相反的。

考虑到 $k$ 比较小,我们可以枚举每个点的第 $i$ 维在距离计算公式中的正负性。

具体地,我们用集合 $S$ 表示一个点每个维度的正负性。用线段树维护区间内每种可能集合 $S$ 的最大值。也就是说,我们分别计算每个点对不同的集合 $S$ 的贡献。合法答案是所有互补集合对贡献和的最大值。

代码

#include <bits/stdc++.h>
#define ll long long
#define ls (p<<1)
#define rs (p<<1|1)
#define maxn 800010
using namespace std;
inline int read(){
    int x=0,flag=1;
    char ch=getchar();
    while(!isdigit(ch)&&ch!='-') ch=getchar();
    if (ch=='-') flag=-1,ch=getchar();
    while(isdigit(ch)) x=(x<<3)+(x<<1)+(ch-'0'),ch=getchar();
    return x*flag;
}
struct Seg{
    int t[maxn];
    inline void update(int l,int r,int x,int v,int p){
        if (l==r) {t[p]=v;return;}
        int mid=((l+r)>>1);
        if (mid>=x) update(l,mid,x,v,ls);
        else update(mid+1,r,x,v,rs);
        t[p]=max(t[ls],t[rs]);
    }
    inline int query(int l,int r,int L,int R,int p){
        if (L<=l&&r<=R) return t[p];
        int mid=((l+r)>>1);
        if (R<=mid) return query(l,mid,L,R,ls);
        if (L>=mid+1) return query(mid+1,r,L,R,rs);
        return max(query(l,mid,L,R,ls),query(mid+1,r,L,R,rs));
    }
}mk[32];
int n,k,m,a[6],b[32];
inline void update(int pos){
    for (int j=1;j<=k;++j)
            a[j]=read();
    for (int S=0;S<1<<k;++S){
        int sum=0;
        for (int j=1;j<=k;++j)
            if ((S>>(j-1))&1) sum-=a[j];
            else sum+=a[j];
        mk[S].update(1,n,pos,sum,1);
    }
}
inline void query(int l,int r){
    int res=-INT_MAX;
    for (int S=0;S<1<<k;++S)
        b[S]=mk[S].query(1,n,l,r,1);
    for (int S=0;S<1<<k;++S)
        res=max(res,b[S]+b[((1<<k)-1)-S]);
    printf("%d\n",res);
}
int main(){
    n=read(),k=read();
    for (int S=0;S<1<<k;++S)
        memset(mk[S].t,0x3f,sizeof(mk[S].t));
    for (int i=1;i<=n;++i) update(i);
    m=read();
    for (int i=1,op,pos,l,r;i<=m;++i){
        op=read();
        if (op==1) pos=read(),update(pos);
        if (op==2) l=read(),r=read(),query(l,r);
    }
}