[CF1093G]Multidimensional Queries 题解

前言

DennyQi太巨了

题解

代码

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

struct Pos{
    int f[32];
} seg[800005];

int n, k, max_sta;

inline void pushUp(int pos){
    for (int i = 0; i < max_sta; ++i)
        seg[pos].f[i] = max(seg[pos << 1].f[i], seg[pos << 1 | 1].f[i]);
}

int tmppos[5];

void build(int pos, int l, int r){
    if (l == r){
        for (int i = 0; i < k; ++i) scanf("%d", &tmppos[i]);
        for (int i = 0; i < max_sta; ++i){
            seg[pos].f[i] = 0;
            for (int j = 0; j < k; ++j)
                if (i & (1 << j))
                    seg[pos].f[i] += tmppos[j];
                else
                    seg[pos].f[i] -= tmppos[j];
        }
        return ;
    }
    int mid = (l + r) >> 1;
    build(pos << 1, l, mid), build(pos << 1 | 1, mid + 1, r);
    pushUp(pos);
}

inline void mrg(Pos &a, Pos b){
    for (int i = 0; i < max_sta; ++i)
        a.f[i] = max(a.f[i], b.f[i]);
}

Pos query(int pos, int l, int r, int x, int y){
    if (x <= l && r <= y) return seg[pos];
    int mid = (l + r) >> 1;
    Pos res;
    if (x <= mid)
        res = query(pos << 1, l, mid, x, y);
    if (y > mid){
        if (x <= mid)
            mrg(res, query(pos << 1 | 1, mid + 1, r, x, y));
        else
            res = query(pos << 1 | 1, mid + 1, r, x, y);
    }
    return res;
}

void modify(int pos, int l, int r, int x){
    if (l == r){
        for (int i = 0; i < max_sta; ++i){
            seg[pos].f[i] = 0;
            for (int j = 0; j < k; ++j)
                if (i & (1 << j))
                    seg[pos].f[i] += tmppos[j];
                else
                    seg[pos].f[i] -= tmppos[j];
        }
        return ;
    }
    int mid = (l + r) >> 1;
    if (x <= mid) modify(pos << 1, l, mid, x);
    else modify(pos << 1 | 1, mid + 1, r, x);
    pushUp(pos);
}

int main(){
    scanf("%d %d", &n, &k); max_sta = 1 << k;
    build(1, 1, n);
    int q; scanf("%d", &q);
    while (q--){
        int op; scanf("%d", &op);
        int i;
        if (op == 1){
            scanf("%d", &i);
            for (int j = 0; j < k; ++j)
                scanf("%d", &tmppos[j]);
            modify(1, 1, n, i);
        }
        else if (op == 2){
            int l, r; scanf("%d %d", &l, &r);
            Pos res = query(1, 1, n, l, r);
            int ans = 0;
            for (int i = 0; i < (1 << (k - 1)); ++i)
                ans = max(ans, res.f[i] + res.f[(max_sta - 1) ^ i]);
            printf("%d\n", ans);
        }
    }
    return 0;
}

[CF1093G]Multidimensional Queries 题解

原文：https://www.cnblogs.com/linzhengmin/p/11351470.html