[CF1093G]Multidimensional Queries 题解

前言

DennyQi太巨了!

定义一个点\(a\)，\(a_x\)表示\(a\)在第\(x\)维空间上的坐标值

题解

这题的思路珂以说非常巧妙(原谅我又用了这个"珂")，

我们知道曼哈顿距离是\(\sum|a_i-b_i|\)，\(|a_i-b_i|\)其实也珂以看作是\((a_i-b_i)\)和\((b_i-a_i)\)中较大的那个。

根据上面的分析曼哈顿距离珂以看作是\(\sum max(a_i-b_i,b_i-a_i)\)，

继续分析珂以得出，每个点在每一维度上要应用的无非只有两种情况\(a_i\)，\(-a_i\)。

由于区间内取两点求最小值要求每个点都是完整的(就是说一旦选取了该点那么必定会用到该点所有维度上的坐标)，那么也就意味着对于一个点，它最多可能(仅为可能)用到的状态会是\(2^k\)次方个。

本题坐标只有5维，电脑不是人脑，那么显然我们珂以枚举解决以上问题。

那么求曼哈顿距离的时候便利所有\(a_i\)的正负性，显然若\(a_i\)为正，\(b_i\)即负；\(a_i\)为负，\(b_i\)为正。

如果用一个二进制状态来压缩，1表示\(a_i\)为正，0表示\(a_i\)为负，显然任意一组关于\(a\)的状态，记为\(sta\)，

对应的\(b\)的装态表示为\((((2^k) - 1) - sta)\)也珂以记作\((((2^k) - 1)\ \textbf{xor}\ sta)\)。

那么用一个线段树维护，每一个节点表示对应的区间\([l,r]\)内的曼哈顿距离最大值。

上传标记非常简单就是暴力取两个子节点，然后取对于每一种正负性的珂能，都取max即可。

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]);

}

同理应用于合并query时的左右子树的结果。

例子

如果您没有看懂上面的文字，我们不妨来举一个例子。

若\(k=3\)时有两个点\(a,b\)坐标分别记为\((1,2,3),(-1,2,4)\)

那么对于点a来说有\(2^3=8\)种状态，

即\((1,2,3),(1,2,-3),(1,-2,3),(1,-2,-3),\)

\((-1,2,3),(-1,2,-3),(-1,-2,3),(-1,-2,-3)\)

同理b也有\(2^3=8\)种状态，对于这\(a,b\)的\(8\)种状态两两对应，也就是

\((1,2,3)\)对应\((-(-1),-2,-4)\dots\)这些互相对应的状态取max以后也就是 \(\sum|a_i-b_i|\)啦QAQ

代码

#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 题解

前言

题解

例子

代码

最新文章

热门文章