Dashboard – 2021 ICPC Southeastern Europe Regional Contest – Codeforces

题意：有 $k$ 个长为 $n$ 的序列，并且定义序列 $b_i$ 表示把 $k$ 个序列的对应位置加起来之后得到的序列。

现在每次可以把某一行的某个区间全部加上一个数，或者某一行的某个区间全部赋值成一个数，或者询问某个区间中 $b_i$ 的最小值，要求可持久化。

$k \le 4$

本题核心思想实际上只有一个，就是把区间赋值操作看成区间清空再加上对应的数，这样就转化成了区间加。

至于区间清空实际上是不需要支持的，可以维护一个这一行始终全 $0$ 的线段树，需要清空的时候就接上全 $0$ 线段树的对应结点。题目已经要求可持久化了，所以直接开 $2^k$ 个线段树来维护每行是否全 $0$ 就行了。

区间加区间查询最值是可以用标记永久化实现的，但是要注意一个问题：因为存在把一棵树接到另一棵树上的操作，所以在接上去的时候要把标记减掉两棵树祖先标记总和的差值，这样才能让最后累加之后的标记等于新树上应该等于的值。

#include <bits/stdc++.h>

using namespace std;

constexpr int maxn = 250005, maxm = (maxn * 2 + 20000 * 19 * 2) * 17;

int lc[maxm], rc[maxm], seg_cnt;
long long val[maxm], tag[maxm];

int copied(int x) {
	int o = ++seg_cnt;

	lc[o] = lc[x];
	rc[o] = rc[x];
	val[o] = val[x];
	tag[o] = tag[x];

	return o;
}

int a[maxn][4];

int root[20005][16], p;

void build(int l, int r, int &o, int mask) {
	o = ++seg_cnt;
	
	if (l == r) {
		for (int i = 0; i < p; i++)
			if (mask >> i & 1)
				val[o] += a[l][i];
		
		return;
	}

	int mid = (l + r) / 2;

	build(l, mid, lc[o], mask);
	build(mid + 1, r, rc[o], mask);

	val[o] = min(val[lc[o]], val[rc[o]])/* + tag[o]*/;
}

int s, t, d;

void modify_add(int l, int r, int &o, int u) {
	o = copied(u);

	if (s <= l && t >= r) {
		val[o] += d;
		tag[o] += d;
		
		return;
	}

	int mid = (l + r) / 2;

	if (s <= mid)
		modify_add(l, mid, lc[o], lc[u]);
	if (t > mid)
		modify_add(mid + 1, r, rc[o], rc[u]);
	
	val[o] = min(val[lc[o]], val[rc[o]]) + tag[o];
}

void modify_set(int l, int r, int &o, int u, int v, long long tmp = 0) {
	if (s <= l && t >= r) {
		o = copied(v);

		val[o] += d - tmp;
		tag[o] += d - tmp;

		return;
	}

	tmp += tag[u] - tag[v];
	o = copied(u);
	int mid = (l + r) / 2;

	if (s <= mid)
		modify_set(l, mid, lc[o], lc[u], lc[v], tmp);
	if (t > mid)
		modify_set(mid + 1, r, rc[o], rc[u], rc[v], tmp);
	
	val[o] = min(val[lc[o]], val[rc[o]]) + tag[o];
}

long long query(int l, int r, int o) {
	if (s <= l && t >= r)
		return val[o];
	
	int mid = (l + r) / 2;
	long long ans = 0x3f3f3f3f3f3f3f3fll;

	if (s <= mid)
		ans = min(ans, query(l, mid, lc[o]));
	if (t > mid)
		ans = min(ans, query(mid + 1, r, rc[o]));
	
	return ans + tag[o];
}

int main() {

	int n, m;
	scanf("%d%d%d", &p, &n, &m);

	for (int k = 0; k < p; k++)
		for (int i = 1; i <= n; i++)
			scanf("%d", &a[i][k]);
	
	for (int mask = 0; mask < (1 << p); mask++)
		build(1, n, root[0][mask], mask);

	for (int i = 1; i <= m; i++) {
		int op, v;
		scanf("%d%d", &op, &v);

		if (op == 1) {
			int k;
			scanf("%d%d%d%d", &k, &s, &t, &d);
			k--;

			for (int mask = 0; mask < (1 << p); mask++) {
				if (mask >> k & 1)
					modify_add(1, n, root[i][mask], root[v][mask]);
				else
					root[i][mask] = root[v][mask];
			}
		}
		else if (op == 2) {
			int k;
			scanf("%d%d%d%d", &k, &s, &t, &d);
			k--;

			for (int mask = 0; mask < (1 << p); mask++) {
				if (mask >> k & 1)
					modify_set(1, n, root[i][mask], root[v][mask], root[v][mask ^ (1 << k)]);
				else
					root[i][mask] = root[v][mask];
			}

		}
		else if (op == 3) {
			scanf("%d%d", &s, &t);

			printf("%d\n", (int)query(1, n, root[v][(1 << p) - 1]));
		}
	}

	return 0;
}