Codeforces 1093G Multidimensional Queries

题目链接https://codeforces.com/problemset/problem/1093/G

题意k维空间上有n个点,要求支持单点修改坐标,区间查询最远曼哈顿距离。

思路:由这个https://www.cnblogs.com/mochenmochen/p/5156919.html我们可以知道拿线段树维护每一种状态下的最大值就好了。

#include <bits/stdc++.h>
#define MP make_pair
#define PB emplace_back
using namespace std;
typedef long long ll;
template<typename T>
inline T read(T&x){
    x=0;int f=0;char ch=getchar();
    while (ch<'0' || ch>'9') f|=(ch=='-'),ch=getchar();
    while (ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();
    return x=f?-x:x;
}
const int N=32;
const int M=2e5+10;
const int INF=2000000000;
int n,m,K,q,i,op,x,y,S,ans,mx[M<<2][N],tmp[N],f[N];
#define lson root<<1,l,mid
#define rson root<<1|1,mid+1,r
void Set(int x){
    for (i=0;i<m;++i) read(f[i]);
    for (S=0;S<=K;++S){
        mx[x][S]=0;
        for (i=0;i<m;++i) mx[x][S]+=(S&(1<<i))?f[i]:-f[i];
    }
}
void pushup(int a[],int b[],int c[]){
    for (i=0;i<=K;++i) a[i]=max(b[i],c[i]);
}
void build(int root,int l,int r){
    if (l==r){
        Set(root);
        return;
    }
    int mid=l+((r-l)>>1);
    build(lson);
    build(rson);
    pushup(mx[root],mx[root<<1],mx[root<<1|1]);
}
void update(int root,int l,int r,int pos){
    if (l==r){
        Set(root);
        return;
    }
    int mid=l+((r-l)>>1);
    if (pos<=mid) update(lson,pos);
    else update(rson,pos);
    pushup(mx[root],mx[root<<1],mx[root<<1|1]);
}
void query(int root,int l,int r,int L,int R){
    if (L<=l && r<=R){
        pushup(tmp,tmp,mx[root]);
        return;
    }
    int mid=l+((r-l)>>1);
    if (L<=mid) query(lson,L,R);
    if (mid<R) query(rson,L,R);
}
int main(){
    read(n),read(m);
    K=(1<<m)-1;
    build(1,1,n);
    for (read(q);q--;){
        read(op),read(x);
        if (op==1) update(1,1,n,x);
        else{
            read(y);
            for (i=0;i<=K;++i) tmp[i]=-INF;
            query(1,1,n,x,y);
            ans=-INF;
            for (i=0;i<=K;++i) ans=max(ans,tmp[i]+tmp[i^K]);
            printf("%d\n",ans);
        }
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注